Opened 11 years ago

Closed 11 years ago

Last modified 11 years ago

#8746 closed defect (fixed)

Equality of posets element is very slow

Reported by: hivert Owned by:
Priority: blocker Milestone: sage-4.4.1
Component: combinatorics Keywords: Comparison posets elements
Cc: sage-combinat Merged in: sage-4.4.1.alpha2
Authors: Florent Hivert Reviewers: Andrey Novoseltsev
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

This is due to comparing the parent which can indeed be very slow. However most of the time when comparing x and y, the two parent are identical and are better compared with is. Here is the results:

Before the patch:

sage: P = Posets.ChainPoset(30)
sage: %time len([x == y for x in P for y in P])
CPU times: user 18.05 s, sys: 0.04 s, total: 18.09 s
Wall time: 18.25 s
900

After the patch:

sage: P = Posets.ChainPoset(30)
sage: %time len([x == y for x in P for y in P])
CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s
Wall time: 0.02 s
900

Cheers,

Florent

Attachments (1)

trac_8746-posets__eq__speedup-fh.patch (4.2 KB) - added by hivert 11 years ago.

Download all attachments as: .zip

Change History (8)

comment:1 Changed 11 years ago by hivert

  • Cc sage-combinat added
  • Status changed from new to needs_review

Changed 11 years ago by hivert

comment:2 follow-up: Changed 11 years ago by novoselt

  • Reviewers set to Andrey Novoseltsev
  • Status changed from needs_review to positive_review

Looks good to me and passes all doctests.

comment:3 in reply to: ↑ 2 Changed 11 years ago by hivert

Replying to novoselt:

Looks good to me and passes all doctests.

Thanks a lot for the very quick review !

comment:4 Changed 11 years ago by hivert

  • Owner changed from sage-combinat to (none)
  • Priority changed from major to blocker

comment:5 Changed 11 years ago by hivert

I've sent the following message to sage-release and sage-devel but it doesn't seems to pass through

> This release candidate for Sage 4.4 closed 19 tickets (on top of
> 4.4.alpha1). On trac, these tickets were labeled as "merged into
> 4.4.alpha2", but then I decided that alpha2 should be the same as rc0.

Cool ! So there is a good chance that we'll have 4.4 for sage 20.5 next week
at Toronto ! This is perfect...

I'm however embarrassed to have the following question/request:
 - how do we decide to make some ticket blocker for a release. Is it possible
at this stage to make #8746 blocker for 4.4. Here is the rationale:

The Posets library (by Franco Saliola) allows to deals with small Partially
Ordered SETS. This kind of structure is extremely useful an common in
combinatorics. Usually we play with one poset at a time, seeking for
particular property of one of them. For my research I had to play with many of
them and I discovered that the equality was (very fast) but completely broken,
preventing them to be used eg. as key in dict. This was fixed in #7438. We
solved this together with Nicolas Borie (which is a student of Nicolas Thiéry)
and this was merged in alpha0. However we didn't realize that doing this we
slowed of the most common usage that is comparing element in a single poset by
several order of magnitude. I take the full blame for this mistake which I
consider as an important regression. #8746 solve this common use issue.

So is there still possible to merge #8746 while having 4.4 out before sage
days 20.5 ? I realize that I should have marked this ticket as critical or
blocker at its creation but I don't know how this is decided so that I never
change this field... Many Apologies for this late request.

comment:6 Changed 11 years ago by was

  • Merged in set to 4.4.1.alpha2
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:7 Changed 11 years ago by mvngu

  • Merged in changed from 4.4.1.alpha2 to sage-4.4.1.alpha2
Note: See TracTickets for help on using tickets.