Opened 6 years ago
Closed 6 years ago
#17408 closed enhancement (fixed)
Faster transitive_reduction (=> faster Poset creation)
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.5 
Component:  graph theory  Keywords:  poset 
Cc:  chapoton, jmantysalo  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  ade98aa (Commits)  Commit:  ade98aa90d2954a59a6fad342b92d23f01803308 
Dependencies:  Stopgaps: 
Description (last modified by )
As reported on #17361, the call to transitive_reduction
represents a nonnegligible part of Poset creation.
This branch reimplements it for acyclic graphs.
sage: g = posets.BooleanLattice(5).hasse_diagram().transitive_closure(); g = g.cartesian_product(g) sage: %timeit g.transitive_reduction() 1 loops, best of 3: 1.02 s per loop sage: %timeit g.transitive_reduction(acyclic=True) 10 loops, best of 3: 28.9 ms per loop
Now the critical part in the creation of a Poset
is triggered by UniqueRepresentation
. As soon as you create a Poset
it is being compared with those that already exists... That is actually precomputing the equality relationships between all existing posets even if you never asked for it, and I personally see it as wasted time (especially since I cannot disable it).
Nathann
Change History (30)
comment:1 Changed 6 years ago by
 Description modified (diff)
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
 Branch set to u/ncohen/17408
comment:3 Changed 6 years ago by
 Commit set to ce577a909e3ac2835f975cc9515b54459174e8ca
comment:4 Changed 6 years ago by
 Keywords poset added
comment:5 Changed 6 years ago by
 Description modified (diff)
comment:6 Changed 6 years ago by
"That is actually precomputing the equality relationships between all existing posets even if you never asked for it, and I personally see it as wasted time (especially since I cannot disable it)."
What happens with key= parameter? If you put a different one in every poset, I think it should not try to compare to posets with different key.
comment:7 followup: ↓ 8 Changed 6 years ago by
Indeed, but then the poset equality is broken. And I have no control the posets built by subfunctions like the poset constructors, the products, etc ...
comment:8 in reply to: ↑ 7 Changed 6 years ago by
Replying to ncohen:
Indeed, but then the poset equality is broken. And I have no control the posets built by subfunctions like the poset constructors, the products, etc ...
True. Should there be a global setting for it? Or an option in every poset function for this?
comment:9 Changed 6 years ago by
True. Should there be a global setting for it? Or an option in every poset function for this?
Truth is that I do not know. This feature is a class inheritance from UniqueRepresentation
, so you cannot really "flag" that.
Yep. Complicated. Don't know how to make both work easily _
Nathann
comment:10 followup: ↓ 11 Changed 6 years ago by
Objects produced in an inner loop should not be UniqueRepresentation
. Parent are designed to be heavy objects. You should be creating them at least one or two orders less frequently than your most frequently created objects (unless your computations aren't bound by creation of objects). If you're finding that you're creating posets frequently, then you should make a "lightweight" version of poset that's not carrying around all the parent baggage.
If you're finding that those "lightweight" posets need to be turned into fullfledged parents every now and again, then consider making it possible to create a fullscale poset from a lightweight one.
comment:11 in reply to: ↑ 10 Changed 6 years ago by
Replying to nbruin:
If you're finding that you're creating posets frequently, then you should make a "lightweight" version of poset that's not carrying around all the parent baggage.
Maybe we already have this: it is called Hasse diagram?
I mean, can we have a code generating only hasse diagrams and using functions from hasse_diagram.py
? I have been computing quite many calculations of format "Generate posets of size n
. Remove those that have property p
. For remaining compute f(P)
and then find smallest/biggest value among results."
comment:12 followup: ↓ 14 Changed 6 years ago by
If you're finding that you're creating posets frequently, then you should make a "lightweight" version of poset that's not carrying around all the parent baggage.
Well, Jori wants to implement a way to enumerate all posets of a given size, so in this case we will have to pay a high tribute to parents. But how do you think that it should be implemented ? Jori is right that Hasse Diagrams have a lot of features already, but that is only... Well, a Hasse Diagram. No comparisons of elements, none of the products defined in the posets directly, well.
What we would need as you say is a class exactly like Poset without the parent infrastructure, but how could we implement that with the smallest amount of copy/paste ?
Nathann
comment:13 Changed 6 years ago by
sage: g = posets.BooleanLattice(5).hasse_diagram().transitive_closure(); 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
comment:14 in reply to: ↑ 12 Changed 6 years ago by
Replying to ncohen:
What we would need as you say is a class exactly like Poset without the parent infrastructure, but how could we implement that with the smallest amount of copy/paste ?
It would require some thought and some major refactoring. The natural structure to me would seem to have a base class that does not inherit from UniqueRepresentation? that implements all the basic stuff and then (hopefully) use multiple inheritance to equip this with the requisite parent stuff for the "full Parent POSet". If there are things that are incompatible between a usable "fast POSet" and a "full parent POSet" then the useful thing should probably inherit separately from the common base class.
The "full parent poset" init would probably require some trickery to allow instantiation of a full parent from a fast poset (if that's required). Quite possibly, you'd be better off with a UniqueFactory there, so that you have better control over what the construction is keyed under.
comment:15 followup: ↓ 16 Changed 6 years ago by
What is the rationale behind current implementation? I mean, there must be some example where UniqueRepresentation
makes things faster.
I understand the logic for, say, finite ring, but not for posets.
comment:16 in reply to: ↑ 15 ; followups: ↓ 17 ↓ 18 ↓ 21 Changed 6 years ago by
Replying to jmantysalo:
What is the rationale behind current implementation? I mean, there must be some example where
UniqueRepresentation
makes things faster.
I suspect it was done out of dogma: "Parents are supposed to be unique" in sage. That statement by itself is not correct: not all parents need to be unique. However, equalbutnonidentical parents can cause some minor problems in the coercion framework.
The real catch is if you're building a parent that can serve as base for other parents that ARE unique representation. Because cache keys there are looked up by equality and not identity, you can really confuse the coercion framework to the point of getting buggy behaviour. See http://trac.sagemath.org/ticket/15248#comment:2 for an explanation of a classic example.
There is always a solution to this: do not inherit from UniqueRepresentation or UniqueFactory but do inherit from WithEqualityById (or implement that by yourself). It gives you a very cheap but mathematically not terribly useful equality test. However, there's something to say for it: The two posets A={1,2,3}
and B={1,2,3}
with trivial relation (ie. x<=y iff x==y) are isomorphic, but not uniquely so. So unless we're explicitly saying by what isomorphism A,B
are to be identified, perhaps we should treat them as not equal. After all, C={a,b,c}
(with empty relation) is also isomorphic to A
and B
and there noone would be tempted to say C is equal to A and B.
However, such strict equality might be too hard to swallow for people who want their computer algebra system to cater a little more to intuitive, human reasoning. In that case you can just make your parent nonunique, but still define equality to be by some looser equivalence relation. You should just document that your class is not appropriate for use as a base for another UniqueRepesentation
parent.
comment:17 in reply to: ↑ 16 ; followup: ↓ 19 Changed 6 years ago by
Yooooo !
I suspect it was done out of dogma: "Parents are supposed to be unique" in sage.
HMmmm... I am afraid that if I follow the mains lines of what you say, I have no clue how it is to be implemented in practice. I believe that the combinat guys use posets as exponents of polynomials, and that this is why they need a fast equality test. It would be cool if we could remove this UniqueRepresentation
dependency from Posets, while letting them have a way to add it afterwards if they need it in their computations.
We just can't give up enumerating posets up to isomorphism because of this cached equality test. And lose seconds like in the ticket's description.
Nathann
P.S. : What this ticket does is totally orthogonal to that, though, and still in needs_review
:P
comment:18 in reply to: ↑ 16 Changed 6 years ago by
By the way I wonder if I should add a "if self.is_directed_acyclic()" in th function. I am not sure that those who use this transitive_reduction
thing will think of looking at the doc, and is_directed_acyclic
is rather cheap. What would you think of running it when acyclic=False
, just in case ?
Nathann
comment:19 in reply to: ↑ 17 ; followup: ↓ 20 Changed 6 years ago by
Replying to ncohen:
HMmmm... I am afraid that if I follow the mains lines of what you say, I have no clue how it is to be implemented in practice. I believe that the combinat guys use posets as exponents of polynomials, and that this is why they need a fast equality test. It would be cool if we could remove this
UniqueRepresentation
dependency from Posets, while letting them have a way to add it afterwards if they need it in their computations.
For one thing, that use wouldn't require posets to be *parents* then.
[possibly offtopic example] This happens in number theory too: fractional ideals are Zsubmodules of a number field, so they have elements. That would qualify them to be "parents", but nobody in their right mind would implement them like that if you're going to do ideal arithmetic: then they're just represented as matrices or tuples of generating elements. Equality is taken care of by putting generators in normal form, which can be fairly expensive the first time around, but equality testing afterwards is pretty quick.
If you want to make POsets faster you should seriously consider splitting POsetsasparents and POsetsasobjects. Both usage scenarios you describe seem to fall in the latter scenario, by the way, so perhaps POsetsasparents aren't really needed beyond checking a box for which parents are available in sage.
comment:20 in reply to: ↑ 19 Changed 6 years ago by
If you want to make POsets faster you should seriously consider splitting POsetsasparents and POsetsasobjects. Both usage scenarios you describe seem to fall in the latter scenario, by the way, so perhaps POsetsasparents aren't really needed beyond checking a box for which parents are available in sage.
Well, perhaps we could return "Posetasparents" when the user asks for a nonfacade poset, and nonparent posets otherwise.
Sigh. I'll write to the sagedevel and the combinat guys...
Nathann
comment:21 in reply to: ↑ 16 Changed 6 years ago by
Replying to nbruin:
What is the rationale behind current implementation? I mean, there must be some example where
UniqueRepresentation
makes things faster.
However, there's something to say for it: The two posets
A={1,2,3}
andB={1,2,3}
with trivial relation (ie. x<=y iff x==y) are isomorphic, but not uniquely so. So unless we're explicitly saying by what isomorphismA,B
are to be identified, perhaps we should treat them as not equal. After all,C={a,b,c}
(with empty relation) is also isomorphic toA
andB
and there noone would be tempted to say C is equal to A and B.
Thank you for very good explanation!
Generating all posets of size 7 up to isomorphism takes 18,5 second  this is not a bottle neck then. But with #14110 the time drops to 2,5 seconds. And when generating just Hasse diagrams instead of posets it took 0,3 second. In the code I was asked to write this is the turning point: now slowest part is doing something with posets, not generating them.
Maybe this is so specialized case that we should let posets to be like they are now. A user might then optimize by directly playing with Hasse diagrams.
This optimization does not mean that you can do things with posets of size 2n
 it means that that you can use posets of size n+2
.
comment:22 Changed 6 years ago by
(beyond the poset discussion, this ticket is still needing a review) :P
comment:23 Changed 6 years ago by
 Commit changed from ce577a909e3ac2835f975cc9515b54459174e8ca to 253fc21867d070748a2c6391fbddd960e98c1aaa
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
253fc21  trac #17408: Faster transitive_reduction (=> faster Poset creation)

comment:24 Changed 6 years ago by
I removed the "acyclic" flag that nobody would have seen and added an automatic detection of acyclic graphs. This has a small cost, but as I believe that nobody ever calls this function except on acyclic graphs I would say that it is a win (really, nobody would have seen the optional flag).
Nathann
comment:25 followup: ↓ 26 Changed 6 years ago by
 Branch changed from u/ncohen/17408 to public/ticket/17408
 Commit changed from 253fc21867d070748a2c6391fbddd960e98c1aaa to 858d7a9197144ee878bbe1c5b9687c4b12662143
There was a failing doctest, because undirected graphs do not have a is_directed_acyclic method.
I have also made a few pep8 changes.
Looks good to me. You can set a positive review if you agree with my changes.
New commits:
858d7a9  trac #17408 reviewer commit, pep8 and other details

comment:26 in reply to: ↑ 25 Changed 6 years ago by
 Reviewers set to Frédéric Chapoton
 Status changed from needs_review to positive_review
Helloooooo !
There was a failing doctest, because undirected graphs do not have a is_directed_acyclic method.
Oh, I see. Thanks ! ;)
I have also made a few pep8 changes.
You should see a doctor about that :P
Looks good to me. You can set a positive review if you agree with my changes.
Thanks again ! :)
Nathann
comment:28 Changed 6 years ago by
 Commit changed from 858d7a9197144ee878bbe1c5b9687c4b12662143 to ade98aa90d2954a59a6fad342b92d23f01803308
Branch pushed to git repo; I updated commit sha1. New commits:
ade98aa  trac #17408: Broken doctests

comment:29 Changed 6 years ago by
 Status changed from needs_work to positive_review
comment:30 Changed 6 years ago by
 Branch changed from public/ticket/17408 to ade98aa90d2954a59a6fad342b92d23f01803308
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #17408: Faster transitive_reduction (=> faster Poset creation)