Opened 4 years ago

Closed 4 years ago

#17408 closed enhancement (fixed)

Faster transitive_reduction (=> faster Poset creation)

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.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 ncohen)

As reported on #17361, the call to transitive_reduction represents a non-negligible part of Poset creation.

This branch re-implements 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 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).

Nathann

Change History (30)

comment:1 Changed 4 years ago by ncohen

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 4 years ago by ncohen

  • Branch set to u/ncohen/17408

comment:3 Changed 4 years ago by git

  • Commit set to ce577a909e3ac2835f975cc9515b54459174e8ca

Branch pushed to git repo; I updated commit sha1. New commits:

ce577a9trac #17408: Faster transitive_reduction (=> faster Poset creation)

comment:4 Changed 4 years ago by chapoton

  • Keywords poset added

comment:5 Changed 4 years ago by ncohen

  • Description modified (diff)

comment:6 Changed 4 years ago by jmantysalo

"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)."

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 follow-up: Changed 4 years ago by 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 ...

comment:8 in reply to: ↑ 7 Changed 4 years ago by jmantysalo

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 4 years ago by ncohen

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 follow-up: Changed 4 years ago by nbruin

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 full-fledged parents every now and again, then consider making it possible to create a full-scale poset from a lightweight one.

See http://trac.sagemath.org/ticket/14356#comment:6

comment:11 in reply to: ↑ 10 Changed 4 years ago by jmantysalo

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 follow-up: Changed 4 years ago by ncohen

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 4 years ago by ncohen

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 4 years ago by nbruin

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 follow-up: Changed 4 years ago by jmantysalo

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 ; follow-ups: Changed 4 years ago by nbruin

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, equal-but-non-identical 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 no-one 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 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 UniqueRepesentation parent.

comment:17 in reply to: ↑ 16 ; follow-up: Changed 4 years ago by ncohen

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 4 years ago by ncohen

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 ; follow-up: Changed 4 years ago by nbruin

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 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.

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.

comment:20 in reply to: ↑ 19 Changed 4 years ago by ncohen

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.

Well, perhaps we could return "Poset-as-parents" when the user asks for a non-facade poset, and non-parent posets otherwise.

Sigh. I'll write to the sage-devel and the combinat guys...

Nathann

comment:21 in reply to: ↑ 16 Changed 4 years ago by jmantysalo

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} 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 no-one 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 4 years ago by ncohen

(beyond the poset discussion, this ticket is still needing a review) :-P

comment:23 Changed 4 years ago by git

  • Commit changed from ce577a909e3ac2835f975cc9515b54459174e8ca to 253fc21867d070748a2c6391fbddd960e98c1aaa

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

253fc21trac #17408: Faster transitive_reduction (=> faster Poset creation)

comment:24 Changed 4 years ago by ncohen

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 follow-up: Changed 4 years ago by chapoton

  • 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:

858d7a9trac #17408 reviewer commit, pep8 and other details

comment:26 in reply to: ↑ 25 Changed 4 years ago by ncohen

  • 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:27 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

doctests fail

comment:28 Changed 4 years ago by git

  • Commit changed from 858d7a9197144ee878bbe1c5b9687c4b12662143 to ade98aa90d2954a59a6fad342b92d23f01803308

Branch pushed to git repo; I updated commit sha1. New commits:

ade98aatrac #17408: Broken doctests

comment:29 Changed 4 years ago by ncohen

  • Status changed from needs_work to positive_review

comment:30 Changed 4 years ago by vbraun

  • Branch changed from public/ticket/17408 to ade98aa90d2954a59a6fad342b92d23f01803308
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.