Opened 10 years ago
Closed 10 years ago
#13406 closed enhancement (fixed)
Optimize CombinatorialFreeModule.Element._vector_
Reported by: | nthiery | Owned by: | jason, was |
---|---|---|---|
Priority: | major | Milestone: | sage-5.5 |
Component: | linear algebra | Keywords: | |
Cc: | sage-combinat, bump, mguaypaq | Merged in: | sage-5.5.beta0 |
Authors: | Nicolas M. Thiéry | Reviewers: | Mathieu Guay-Paquet, Franco Saliola, |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Converting a CombinatorialFreeModule
element to a vector (i.e. dense
FreeModule
element) was ridiculously slow:
Before:
sage: F = CombinatorialFreeModule(QQ, range(10)) sage: f = F.an_element() sage: %timeit f._vector_() 625 loops, best of 3: 142 µs per loop sage: %timeit f.to_vector() 625 loops, best of 3: 143 µs per loop sage: %timeit vector(f) 625 loops, best of 3: 159 µs per loop
After:
sage: F = CombinatorialFreeModule(QQ, range(10)) sage: f = F.an_element() sage: %timeit f._vector_() 625 loops, best of 3: 17.7 µs per loop sage: %timeit f.to_vector() 625 loops, best of 3: 17.5 µs per loop sage: %timeit vector(f) 625 loops, best of 3: 34.6 µs per loop
This impacts for example Weyl group actions, and thus lots of the root systems arithmetic.
Before:
sage: W = WeylGroup(["A",5]) sage: %time l = list(W) CPU times: user 3.55 s, sys: 0.00 s, total: 3.55 s Wall time: 3.57 s
After:
sage: W = WeylGroup(["A",5]) sage: %time l = list(W) CPU times: user 2.80 s, sys: 0.00 s, total: 2.81 s Wall time: 2.81 s
Attachments (1)
Change History (16)
comment:1 Changed 10 years ago by
Description: | modified (diff) |
---|
comment:2 follow-up: 3 Changed 10 years ago by
comment:3 Changed 10 years ago by
Replying to chapoton:
One suggestion, maybe: use the trac automatic link instead of just #number
:trac:`13406`: the code below has been optimized
Oops, thanks for catching this! Btw I fixed the patch header in the updated patch.
comment:4 follow-up: 5 Changed 10 years ago by
Nicolas: I see that the code hasn't changed much, yet you get an impressive speed-up. Can you comment on how/why it happens?
comment:5 follow-up: 7 Changed 10 years ago by
Hi Franco,
Replying to saliola:
Nicolas: I see that the code hasn't changed much, yet you get an impressive speed-up. Can you comment on how/why it happens?
Essentially, vector(...) is very slow, in particular because it first has to figure out which dense free module F to use. The patch builds that free module once for all (in the _dense_free_module method which is cached). And then it saves a bit more by feeding the data directly to the element class of F, and being careful about the options).
comment:6 Changed 10 years ago by
I'm ready to set a positive review on this, but I can't run doctests on sage-5.3.rc0 currently and the patchbot seems to be sleeping. Can someone run tests, etc.
comment:7 Changed 10 years ago by
Replying to nthiery:
Hi Franco,
Replying to saliola:
Nicolas: I see that the code hasn't changed much, yet you get an impressive speed-up. Can you comment on how/why it happens?
Essentially, vector(...) is very slow, in particular because it first has to figure out which dense free module F to use. The patch builds that free module once for all (in the _dense_free_module method which is cached). And then it saves a bit more by feeding the data directly to the element class of F, and being careful about the options).
Thanks for the explanation, Nicolas. It's very subtle.
comment:8 Changed 10 years ago by
Status: | new → needs_review |
---|
comment:9 follow-up: 10 Changed 10 years ago by
Cc: | mguaypaq added |
---|---|
Description: | modified (diff) |
Status: | needs_review → needs_work |
As far as I can tell, the patch as posted does not functionally change anything. It changes the documentation of CombinatorialFreeModuleElement._vector_
without changing the corresponding code, and adds the method CombinatorialFreeModule._dense_free_module
without adding any code to have it called.
I confirmed this experimentally by getting the following timings on sage-5.3 for the first three tests in the ticket description (f._vector_()
, f.to_vector()
, vector(f)
):
Before: 270, 270, 293 µs
After: 265, 266, 290 µs
and also by adding a print
statement to _dense_free_module
(so that I know the code is never called). I got similar results by trying this on sage-5.3 + combinat.
Is it possible that the patch file got corrupted, or that it is based on an already modified version of Sage, or that there is an unstated dependency which introduces _dense_free_module
as a hook?
comment:10 Changed 10 years ago by
Replying to mguaypaq:
Is it possible that the patch file got corrupted
Yikes! Yes, definitely, a hunk (well, THE interesting hunk) was somehow lost in that patch. I can't find it either on the combinat server, so I must have screwed up somewhere. Thanks for catching this! I'll work on this tomorrow morning.
Cheers,
Nicolas
PS: I now better understand Franco's comment about the subtlety of this patch!
Changed 10 years ago by
Attachment: | trac_13406-combinatorial_free_module-optimize_to_vector-nt.patch added |
---|
comment:11 Changed 10 years ago by
Description: | modified (diff) |
---|---|
Reviewers: | → Mathieu Guay-Paquet, Franco Saliola, |
Status: | needs_work → needs_review |
Done! I could not find back the code, so I rewrote it (and gained another micro second :-))
comment:12 follow-up: 14 Changed 10 years ago by
Description: | modified (diff) |
---|---|
Status: | needs_review → positive_review |
With the current patch, the code change makes sense, is well documented, and I can reproduce the impressive speedups described in the ticked description on my own machine. Also, the patchbot reports that all tests pass on Sage 5.4.rc1 and that the documentation builds cleanly.
comment:13 Changed 10 years ago by
Milestone: | sage-5.4 → sage-5.5 |
---|
comment:14 Changed 10 years ago by
Replying to mguaypaq:
With the current patch, the code change makes sense, is well documented, and I can reproduce the impressive speedups described in the ticked description on my own machine. Also, the patchbot reports that all tests pass on Sage 5.4.rc1 and that the documentation builds cleanly.
Thanks for the review!
comment:15 Changed 10 years ago by
Merged in: | → sage-5.5.beta0 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
One suggestion, maybe: use the trac automatic link instead of just #number