Sage: Ticket #17408: Faster transitive_reduction (=> faster Poset creation)
https://trac.sagemath.org/ticket/17408
<p>
As reported on <a class="closed ticket" href="https://trac.sagemath.org/ticket/17361" title="enhancement: Poset: Add ordinal_product (closed: fixed)">#17361</a>, the call to <code>transitive_reduction</code> represents a non-negligible part of Poset creation.
</p>
<p>
This branch re-implements it for acyclic graphs.
</p>
<pre class="wiki">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
</pre><p>
Now the critical part in the creation of a <code>Poset</code> is triggered by <code>UniqueRepresentation</code>. As soon as you create a <code>Poset</code> it is being compared with those that already exists... That is actually pre-computing 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).
</p>
<p>
Nathann
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/17408
Trac 1.1.6ncohenThu, 27 Nov 2014 14:19:06 GMTstatus, description changed
https://trac.sagemath.org/ticket/17408#comment:1
https://trac.sagemath.org/ticket/17408#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/17408?action=diff&version=1">diff</a>)
</li>
</ul>
TicketncohenThu, 27 Nov 2014 14:19:24 GMTbranch set
https://trac.sagemath.org/ticket/17408#comment:2
https://trac.sagemath.org/ticket/17408#comment:2
<ul>
<li><strong>branch</strong>
set to <em>u/ncohen/17408</em>
</li>
</ul>
TicketgitThu, 27 Nov 2014 14:19:45 GMTcommit set
https://trac.sagemath.org/ticket/17408#comment:3
https://trac.sagemath.org/ticket/17408#comment:3
<ul>
<li><strong>commit</strong>
set to <em>ce577a909e3ac2835f975cc9515b54459174e8ca</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ce577a909e3ac2835f975cc9515b54459174e8ca"><span class="icon"></span>ce577a9</a></td><td><code>trac #17408: Faster transitive_reduction (=> faster Poset creation)</code>
</td></tr></table>
TicketchapotonThu, 27 Nov 2014 21:17:47 GMTkeywords set
https://trac.sagemath.org/ticket/17408#comment:4
https://trac.sagemath.org/ticket/17408#comment:4
<ul>
<li><strong>keywords</strong>
<em>poset</em> added
</li>
</ul>
TicketncohenFri, 28 Nov 2014 06:19:59 GMTdescription changed
https://trac.sagemath.org/ticket/17408#comment:5
https://trac.sagemath.org/ticket/17408#comment:5
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/17408?action=diff&version=5">diff</a>)
</li>
</ul>
TicketjmantysaloFri, 28 Nov 2014 06:52:16 GMT
https://trac.sagemath.org/ticket/17408#comment:6
https://trac.sagemath.org/ticket/17408#comment:6
<p>
"That is actually pre-computing 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)."
</p>
<p>
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.
</p>
TicketncohenFri, 28 Nov 2014 06:56:17 GMT
https://trac.sagemath.org/ticket/17408#comment:7
https://trac.sagemath.org/ticket/17408#comment:7
<p>
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 ...
</p>
TicketjmantysaloFri, 28 Nov 2014 07:03:04 GMT
https://trac.sagemath.org/ticket/17408#comment:8
https://trac.sagemath.org/ticket/17408#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17408#comment:7" title="Comment 7">ncohen</a>:
</p>
<blockquote class="citation">
<p>
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 ...
</p>
</blockquote>
<p>
True. Should there be a global setting for it? Or an option in every poset function for this?
</p>
TicketncohenFri, 28 Nov 2014 07:13:00 GMT
https://trac.sagemath.org/ticket/17408#comment:9
https://trac.sagemath.org/ticket/17408#comment:9
<blockquote class="citation">
<p>
True. Should there be a global setting for it? Or an option in every poset function for this?
</p>
</blockquote>
<p>
Truth is that I do not know. This feature is a class inheritance from <code>UniqueRepresentation</code>, so you cannot really "flag" that.
</p>
<p>
Yep. Complicated. Don't know how to make both work easily <code>-_-</code>
</p>
<p>
Nathann
</p>
TicketnbruinFri, 28 Nov 2014 08:37:28 GMT
https://trac.sagemath.org/ticket/17408#comment:10
https://trac.sagemath.org/ticket/17408#comment:10
<p>
Objects produced in an inner loop should not be <code>UniqueRepresentation</code>. Parent are <em>designed</em> 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.
</p>
<p>
If you're finding that those "lightweight" posets need to be turned into full-fledged parents every now and again, then consider making it possible to create a full-scale poset from a lightweight one.
</p>
<p>
See <a class="ext-link" href="http://trac.sagemath.org/ticket/14356#comment:6"><span class="icon"></span>http://trac.sagemath.org/ticket/14356#comment:6</a>
</p>
TicketjmantysaloFri, 28 Nov 2014 08:53:47 GMT
https://trac.sagemath.org/ticket/17408#comment:11
https://trac.sagemath.org/ticket/17408#comment:11
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17408#comment:10" title="Comment 10">nbruin</a>:
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
Maybe we already have this: it is called Hasse diagram?
</p>
<p>
I mean, can we have a code generating only hasse diagrams and using functions from <code>hasse_diagram.py</code>? I have been computing quite many calculations of format "Generate posets of size <code>n</code>. Remove those that have property <code>p</code>. For remaining compute <code>f(P)</code> and then find smallest/biggest value among results."
</p>
TicketncohenFri, 28 Nov 2014 09:10:59 GMT
https://trac.sagemath.org/ticket/17408#comment:12
https://trac.sagemath.org/ticket/17408#comment:12
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
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.
</p>
<p>
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 ?
</p>
<p>
Nathann
</p>
TicketncohenFri, 28 Nov 2014 09:16:07 GMT
https://trac.sagemath.org/ticket/17408#comment:13
https://trac.sagemath.org/ticket/17408#comment:13
<pre class="wiki">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
</pre>
TicketnbruinFri, 28 Nov 2014 17:50:00 GMT
https://trac.sagemath.org/ticket/17408#comment:14
https://trac.sagemath.org/ticket/17408#comment:14
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17408#comment:12" title="Comment 12">ncohen</a>:
</p>
<blockquote class="citation">
<p>
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 ?
</p>
</blockquote>
<p>
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 <a class="missing wiki">UniqueRepresentation?</a> 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.
</p>
<p>
The "full parent poset" <span class="underline">init</span> 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.
</p>
TicketjmantysaloMon, 01 Dec 2014 07:24:46 GMT
https://trac.sagemath.org/ticket/17408#comment:15
https://trac.sagemath.org/ticket/17408#comment:15
<p>
What is the rationale behind current implementation? I mean, there must be some example where <code>UniqueRepresentation</code> makes things faster.
</p>
<p>
I understand the logic for, say, finite ring, but not for posets.
</p>
TicketnbruinMon, 01 Dec 2014 17:26:14 GMT
https://trac.sagemath.org/ticket/17408#comment:16
https://trac.sagemath.org/ticket/17408#comment:16
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17408#comment:15" title="Comment 15">jmantysalo</a>:
</p>
<blockquote class="citation">
<p>
What is the rationale behind current implementation? I mean, there must be some example where <code>UniqueRepresentation</code> makes things faster.
</p>
</blockquote>
<p>
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, equal-but-non-identical parents can cause some minor problems in the coercion framework.
</p>
<p>
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 <a class="ext-link" href="http://trac.sagemath.org/ticket/15248#comment:2"><span class="icon"></span>http://trac.sagemath.org/ticket/15248#comment:2</a> for an explanation of a classic example.
</p>
<p>
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 <code>A={1,2,3}</code> and <code>B={1,2,3}</code> with trivial relation (ie. x<=y iff x==y) are isomorphic, but not uniquely so. So unless we're explicitly saying by what isomorphism <code>A,B</code> are to be identified, perhaps we should treat them as not equal. After all, <code>C={a,b,c}</code> (with empty relation) is also isomorphic to <code>A</code> and <code>B</code> and there no-one would be tempted to say C is equal to A and B.
</p>
<p>
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 non-unique, 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 <code>UniqueRepesentation</code> parent.
</p>
TicketncohenMon, 01 Dec 2014 17:37:51 GMT
https://trac.sagemath.org/ticket/17408#comment:17
https://trac.sagemath.org/ticket/17408#comment:17
<p>
Yooooo !
</p>
<blockquote class="citation">
<p>
I suspect it was done out of dogma: "Parents are supposed to be unique" in sage.
</p>
</blockquote>
<p>
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 <code>UniqueRepresentation</code> dependency from Posets, while letting them have a way to add it afterwards if they need it in their computations.
</p>
<p>
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.
</p>
<p>
Nathann
</p>
<p>
P.S. : What this ticket does is totally orthogonal to that, though, and still in <code>needs_review</code> <code>:-P</code>
</p>
TicketncohenMon, 01 Dec 2014 17:44:37 GMT
https://trac.sagemath.org/ticket/17408#comment:18
https://trac.sagemath.org/ticket/17408#comment:18
<p>
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 <code>transitive_reduction</code> thing will think of looking at the doc, and <code>is_directed_acyclic</code> is rather cheap. What would you think of running it when <code>acyclic=False</code>, just in case ?
</p>
<p>
Nathann
</p>
TicketnbruinMon, 01 Dec 2014 17:52:30 GMT
https://trac.sagemath.org/ticket/17408#comment:19
https://trac.sagemath.org/ticket/17408#comment:19
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17408#comment:17" title="Comment 17">ncohen</a>:
</p>
<blockquote class="citation">
<p>
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 <code>UniqueRepresentation</code> dependency from Posets, while letting them have a way to add it afterwards if they need it in their computations.
</p>
</blockquote>
<p>
For one thing, that use wouldn't require posets to be *parents* then.
</p>
<p>
[possibly off-topic example]
This happens in number theory too: fractional ideals are Z-submodules 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.
</p>
<p>
If you want to make POsets faster you should seriously consider splitting POsets-as-parents and POsets-as-objects. Both usage scenarios you describe seem to fall in the latter scenario, by the way, so perhaps POsets-as-parents aren't really needed beyond checking a box for which parents are available in sage.
</p>
TicketncohenMon, 01 Dec 2014 17:55:57 GMT
https://trac.sagemath.org/ticket/17408#comment:20
https://trac.sagemath.org/ticket/17408#comment:20
<blockquote class="citation">
<p>
If you want to make POsets faster you should seriously consider splitting POsets-as-parents and POsets-as-objects. Both usage scenarios you describe seem to fall in the latter scenario, by the way, so perhaps POsets-as-parents aren't really needed beyond checking a box for which parents are available in sage.
</p>
</blockquote>
<p>
Well, perhaps we could return "Poset-as-parents" when the user asks for a non-facade poset, and non-parent posets otherwise.
</p>
<p>
Sigh. I'll write to the sage-devel and the combinat guys...
</p>
<p>
Nathann
</p>
TicketjmantysaloTue, 02 Dec 2014 07:49:32 GMT
https://trac.sagemath.org/ticket/17408#comment:21
https://trac.sagemath.org/ticket/17408#comment:21
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17408#comment:16" title="Comment 16">nbruin</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
What is the rationale behind current implementation? I mean, there must be some example where <code>UniqueRepresentation</code> makes things faster.
</p>
</blockquote>
</blockquote>
<blockquote class="citation">
<p>
However, there's something to say for it: The two posets <code>A={1,2,3}</code> and <code>B={1,2,3}</code> with trivial relation (ie. x<=y iff x==y) are isomorphic, but not uniquely so. So unless we're explicitly saying by what isomorphism <code>A,B</code> are to be identified, perhaps we should treat them as not equal. After all, <code>C={a,b,c}</code> (with empty relation) is also isomorphic to <code>A</code> and <code>B</code> and there no-one would be tempted to say C is equal to A and B.
</p>
</blockquote>
<p>
Thank you for very good explanation!
</p>
<p>
Generating all posets of size 7 up to isomorphism takes 18,5 second --- this is not a bottle neck then. But with <a class="new ticket" href="https://trac.sagemath.org/ticket/14110" title="enhancement: Speed Up Poset Generation (new)">#14110</a> 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.
</p>
<p>
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.
</p>
<p>
This optimization does not mean that you can do things with posets of size <code>2n</code> --- it means that that you can use posets of size <code>n+2</code>.
</p>
TicketncohenFri, 05 Dec 2014 06:54:18 GMT
https://trac.sagemath.org/ticket/17408#comment:22
https://trac.sagemath.org/ticket/17408#comment:22
<p>
(beyond the poset discussion, this ticket is still needing a review) <code>:-P</code>
</p>
TicketgitFri, 05 Dec 2014 07:37:24 GMTcommit changed
https://trac.sagemath.org/ticket/17408#comment:23
https://trac.sagemath.org/ticket/17408#comment:23
<ul>
<li><strong>commit</strong>
changed from <em>ce577a909e3ac2835f975cc9515b54459174e8ca</em> to <em>253fc21867d070748a2c6391fbddd960e98c1aaa</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=253fc21867d070748a2c6391fbddd960e98c1aaa"><span class="icon"></span>253fc21</a></td><td><code>trac #17408: Faster transitive_reduction (=> faster Poset creation)</code>
</td></tr></table>
TicketncohenFri, 05 Dec 2014 13:44:19 GMT
https://trac.sagemath.org/ticket/17408#comment:24
https://trac.sagemath.org/ticket/17408#comment:24
<p>
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).
</p>
<p>
Nathann
</p>
TicketchapotonSat, 06 Dec 2014 20:47:41 GMTcommit, branch changed
https://trac.sagemath.org/ticket/17408#comment:25
https://trac.sagemath.org/ticket/17408#comment:25
<ul>
<li><strong>commit</strong>
changed from <em>253fc21867d070748a2c6391fbddd960e98c1aaa</em> to <em>858d7a9197144ee878bbe1c5b9687c4b12662143</em>
</li>
<li><strong>branch</strong>
changed from <em>u/ncohen/17408</em> to <em>public/ticket/17408</em>
</li>
</ul>
<p>
There was a failing doctest, because undirected graphs do not have a is_directed_acyclic method.
</p>
<p>
I have also made a few pep8 changes.
</p>
<p>
Looks good to me. You can set a positive review if you agree with my changes.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=858d7a9197144ee878bbe1c5b9687c4b12662143"><span class="icon"></span>858d7a9</a></td><td><code>trac #17408 reviewer commit, pep8 and other details</code>
</td></tr></table>
TicketncohenMon, 08 Dec 2014 06:53:42 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/17408#comment:26
https://trac.sagemath.org/ticket/17408#comment:26
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Frédéric Chapoton</em>
</li>
</ul>
<p>
Helloooooo !
</p>
<blockquote class="citation">
<p>
There was a failing doctest, because undirected graphs do not have a is_directed_acyclic method.
</p>
</blockquote>
<p>
Oh, I see. Thanks ! <code>;-)</code>
</p>
<blockquote class="citation">
<p>
I have also made a few pep8 changes.
</p>
</blockquote>
<p>
You should see a doctor about that <code>:-P</code>
</p>
<blockquote class="citation">
<p>
Looks good to me. You can set a positive review if you agree with my changes.
</p>
</blockquote>
<p>
Thanks again ! <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketvbraunFri, 12 Dec 2014 13:34:22 GMTstatus changed
https://trac.sagemath.org/ticket/17408#comment:27
https://trac.sagemath.org/ticket/17408#comment:27
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
doctests fail
</p>
TicketgitFri, 12 Dec 2014 18:42:41 GMTcommit changed
https://trac.sagemath.org/ticket/17408#comment:28
https://trac.sagemath.org/ticket/17408#comment:28
<ul>
<li><strong>commit</strong>
changed from <em>858d7a9197144ee878bbe1c5b9687c4b12662143</em> to <em>ade98aa90d2954a59a6fad342b92d23f01803308</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ade98aa90d2954a59a6fad342b92d23f01803308"><span class="icon"></span>ade98aa</a></td><td><code>trac #17408: Broken doctests</code>
</td></tr></table>
TicketncohenSat, 13 Dec 2014 03:43:11 GMTstatus changed
https://trac.sagemath.org/ticket/17408#comment:29
https://trac.sagemath.org/ticket/17408#comment:29
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
TicketvbraunTue, 16 Dec 2014 13:57:13 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/17408#comment:30
https://trac.sagemath.org/ticket/17408#comment:30
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/ticket/17408</em> to <em>ade98aa90d2954a59a6fad342b92d23f01803308</em>
</li>
</ul>
Ticket