Re: [sage-devel] Re: Slow Poset creation and UniqueRepresentation
On Mon, 1 Dec 2014, Nils Bruin wrote: The easy solution for Nathann and Jori for now is just to write their high-performance code in terms of primitives: a tuple consisting of the base set and some suitable description of the PO I can use plain Hasse diagram. A simple example of timings: If I create posets with Posets(7) it takes about half a minute. If I use #14110 I can create posets of size 8 with about same amount of time --- this is where UniqueRepresentation comes to bottleneck. And if I use #14110 and create Hasse diagrams instead of posets it takes about half a minute to generate posets of size 9 --- now bottleneck is on using posets, not creating them. -- Jori Mäntysalo
Re: [sage-devel] Re: Slow Poset creation and UniqueRepresentation
Hello ! Nils mentionned in #17408 [1] that we may *not* need Posets to be parents. The facade Posets (i.e. the default ones) are parents, and it seems that this is the reason why they have been made UniqueRepresentation. Could anybody confirm that ? Also, would anybody know how to make it change ? The goal would be to remove the dependency of facade FinitePoset objects on UniqueRepresentation. The non-facade posets returned by the Poset function could then inherit from both Poset and UniqueRepresentation. The problem here is that inheriting from UniqueRepresentation wastes a *LOT* of time on some computations [2], and is actually the most costly part of the creation of some posets. Also, the current behaviour makes it impossible for Jori to enumerate posets up to isomorphism (because of the memory cost). I am personally stuck, my psychoanalist advised me to not touch Parent/Category code ever again. Nathann [1] http://trac.sagemath.org/ticket/17408 [2] http://trac.sagemath.org/ticket/17408#comment:13 -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Slow Poset creation and UniqueRepresentation
Hi Nathann, On 2014-12-01, Nathann Cohen nathann.co...@gmail.com wrote: The problem here is that inheriting from UniqueRepresentation wastes a *LOT* of time on some computations [2], and is actually the most costly part of the creation of some posets. Also, the current behaviour makes it impossible for Jori to enumerate posets up to isomorphism (because of the memory cost). Is it clear why their not freed, even though UniqueRepresentation only puts a *weak* reference to them (it uses a weak value dictionary)? In any case, it is possible to explicitly clear the cache of a UniqueRepresentation. But this would only help if there is a strong reference pointing from the dictionary key to the corresponding item. Best regards, SImon -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Slow Poset creation and UniqueRepresentation
Hello ! Is it clear why their not freed, even though UniqueRepresentation only puts a *weak* reference to them (it uses a weak value dictionary)? I have no idea, nor guess, on the matter O_o Nathann -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Slow Poset creation and UniqueRepresentation
On Monday, December 1, 2014 10:44:44 AM UTC-8, Simon King wrote: Is it clear why their not freed, even though UniqueRepresentation only puts a *weak* reference to them (it uses a weak value dictionary)? I don't think it's a memory *leaking* issue this time. My impression is that they're running into POSets being slow for the same reason why computations with polynomials over ZZ would be slow if they were UniqueRepresentation. They are not using POSets as parents--they are using them as elements. So all the parent-specific stuff is wasted time and I don't think it's surprising that this ends up being measurable. Parent creation should be happen a couple of orders of magnitude less frequently than your inner loop computations. In any case, it is possible to explicitly clear the cache of a UniqueRepresentation. But this would only help if there is a strong reference pointing from the dictionary key to the corresponding item. Yes it is possible but it should absolutely not be recommended! You're clearing a global cache, so you could be ruining other code that already created an object of the type for which you cleared the cache, and it might be expecting to get a link to the identical object by recreating it with equal parameters. By clearing the cache you might have ruined that. As a last resort in application code you could do it, but it's absolutely not acceptable in library code. Nathann and Jori are working on a ticket, so I think they're aiming to have their code included in the library at some point. -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Slow Poset creation and UniqueRepresentation
Hi Nils, On 2014-12-01, Nils Bruin nbr...@sfu.ca wrote: I don't think it's a memory *leaking* issue this time. Good tidings :) They are not using POSets as parents--they are using them as elements. Aha! That's interesting. I think I have discussed it with Nicolas at some point. In fact, it seems that the whole parent-element-category stuff is not designed for a situation where you have parent structures that at the same time serve as elements of another parent structure. For starters, element_class and parent_class give rise to confusion if a parent is supposed to inherit from both. Anyway, elements shouldn't be unique representation, except when there are only few elements (as in small finite fields). In principle, it is possible to work around the cache. For example, if Foo is a parent structure that in *some* (not all) applications should be used as an element and thus shouldn't be cached, one could implement some `__classcall__` or `__classcall_private__` that takes an optional argument cache=True (that should be the default, I guess), so that the cached `__classcall__` of UniqueRepresentation is not called when cache=False. Mind, though, that it would still inherit comparison by identity. So, it should perhaps better use CachedRepresentation, not UniqueRepresentation (the former does *not* do comparison by identity). Hmm. Sounds like a mess. But I do think one should have a general mechanism (UniqueRepresentationOptional or so) with which one can choose by an optional argument whether caching and comparison by identity should be used or not. In any case, it is possible to explicitly clear the cache of a UniqueRepresentation. But this would only help if there is a strong reference pointing from the dictionary key to the corresponding item. Yes it is possible but it should absolutely not be recommended! Right, sorry, I forgot about the side effects. Cheers, Simon -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Slow Poset creation and UniqueRepresentation
On Monday, December 1, 2014 12:49:27 PM UTC-8, Simon King wrote: Hmm. Sounds like a mess. But I do think one should have a general mechanism (UniqueRepresentationOptional or so) with which one can choose by an optional argument whether caching and comparison by identity should be used or not. I'm not so sure about that. UniqueRepresentation isn't so much a caching tool as it is a semantic one. It's the WithEqualityById that's the important ingredient, and to make that palatable one provides cached construction based on hashingequality of the construction parameters (leading to the CachedRepresentation part). Being able to change behaviour of an object as fundamental as its hashing and equality with a simple flag seems like a bad idea to me. It should be very easy to distinguish what kind of version of the object you're facing. I'd expect to be able to tell this from the type. So I think the design challenge here is to come up with a workable architecture where you can have a fast POset as an element of the *parent* posets over/of type (qualified so that equality/isomorphy testing can be defined properly) as well as a full-scale parent for heavy-duty computation in a fixed poset (is there such a thing?), with full support of coercing elements between different posets (again do people actually need that?), and a way to construct the second out of the first (and possibly the other way around too). In algebraic number theory this comes up with, say, fractional ideals. They are submodules of a number field, so in that respect can be considered full parents. But if you're doing ideal arithmetic you wouldn't want to treat them that way: they're elements of the ideal group, and you represent them by matrices or tuples of generators. Anything heavier than that is waste of resources. In fact, in that setting there's hardly any demand for having ideals as full parents. You may want to check if an element lies in an ideal, but you can support in on things that aren't parents. You probably do want to be ably to construct quotients by integral ideals and localizations etc. (probably as full parents), but again for that you don't need *ideals* to be parents. The easy solution for Nathann and Jori for now is just to write their high-performance code in terms of primitives: a tuple consisting of the base set and some suitable description of the PO (a set of generating a=b pair or so?). Such a thing would be as light as possible. and can trivially be wrapped in a fancier interface should that ever be necessary. The obvious answer to the complaint this data structure is too heavy for me is don't use it then. It might just be that they are discovering the current POset is too heavy to be useful in many settings, in which case a lighter alternative might be nice to have. And since this sounds like a likely scenario in many contexts, it would be nice to have some design ideas that help in accomplishing this. -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Slow Poset creation and UniqueRepresentation
Hi Nathann, On 2014-11-28, Nathann Cohen nathann.co...@gmail.com wrote: sage: g = posets.BooleanLattice(5).hasse_diagram().transitive_closure(); sage: g = g.cartesian_product(g) sage: %time Poset(g) CPU times: user 284 ms, sys: 32 ms, total: 316 ms Wall time: 278 ms Finite poset containing 1024 elements sage: %time Poset(g) CPU times: user 1.63 s, sys: 44 ms, total: 1.68 s Wall time: 1.61 s Finite poset containing 1024 elements Even without my optimisations you see this effect, and I am pretty sure that the huge time penalty here is because Poset inherits from UniqueRepresentation. Profiling shows that most of the time is spent testing equality of posets, which is part of the UniqueRepresentation initialization. You mean the comparison of g with itself takes so much time? Hard to believe, but it really seems to be the case: sage: g = posets.BooleanLattice(5).hasse_diagram().transitive_closure() sage: g = g.cartesian_product(g) sage: %timeit g==g 1 loops, best of 3: 10.3 s per loop How can that be? Isn't generally the test by == first checking whether the two arguments are identical, before calling `.__eq__`? If python does not do it automatically, then at least in your example it would be good to make g.__eq__ use the self is other test, before doing anything expensive. Probably the problem would also be solved by implementing rich comparison via __richcmp__ (not sure though). In any case, if there is a reason to have unique representation, then ideally the defining data should be easy to compare. Evidently, a dictionary lookup has to be involved for any kind of unique represenation. Best regards, Simon -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Slow Poset creation and UniqueRepresentation
Hello ! How can that be? Isn't generally the test by == first checking whether the two arguments are identical, before calling `.__eq__`? If python does not do it automatically, then at least in your example it would be good to make g.__eq__ use the self is other test, before doing anything expensive. Probably the problem would also be solved by implementing rich comparison via __richcmp__ (not sure though). DiGraph comparison is slower than it should be for sure. I already have plans to change that, even though I fear the messy code as I will have to deal with the usual multiedges/edge labels/loops subcases (and their combinations). I should also add the self is other test, but that would not change this example: the code computes a Hasse Diagram from g, and this second digraph is used as a parameter of Poset. Thus a comparison will be necessary anyway (g is not even immutable). In any case, if there is a reason to have unique representation, then ideally the defining data should be easy to compare. Evidently, a dictionary lookup has to be involved for any kind of unique represenation. I agree. I think that I can make DiGraph equality faster [1], but it will not be magic either. Testing equality of graphs will never be free, and I do think that there should be a way to not pay it if you see no need to. Nathann [1] especially in the very very very specific case of the digraphs used by posets -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
