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:

Status badges

Description (last modified by mguaypaq)

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)

trac_13406-combinatorial_free_module-optimize_to_vector-nt.patch (6.0 KB) - added by nthiery 10 years ago.

Download all attachments as: .zip

Change History (16)

comment:1 Changed 10 years ago by nthiery

  • Description modified (diff)

comment:2 follow-up: Changed 10 years ago by chapoton

One suggestion, maybe: use the trac automatic link instead of just #number

:trac:`13406`: the code below has been optimized

comment:3 in reply to: ↑ 2 Changed 10 years ago by nthiery

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: Changed 10 years ago by 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?

comment:5 in reply to: ↑ 4 ; follow-up: Changed 10 years ago by 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).

comment:6 Changed 10 years ago by saliola

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 in reply to: ↑ 5 Changed 10 years ago by saliola

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 chapoton

  • Status changed from new to needs_review

comment:9 follow-up: Changed 10 years ago by mguaypaq

  • Cc mguaypaq added
  • Description modified (diff)
  • Status changed from needs_review to 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 in reply to: ↑ 9 Changed 10 years ago by nthiery

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!

comment:11 Changed 10 years ago by nthiery

  • Description modified (diff)
  • Reviewers set to Mathieu Guay-Paquet, Franco Saliola,
  • Status changed from needs_work to needs_review

Done! I could not find back the code, so I rewrote it (and gained another micro second :-))

comment:12 follow-up: Changed 10 years ago by mguaypaq

  • Description modified (diff)
  • Status changed from needs_review to 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 jdemeyer

  • Milestone changed from sage-5.4 to sage-5.5

comment:14 in reply to: ↑ 12 Changed 10 years ago by nthiery

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 jdemeyer

  • Merged in set to sage-5.5.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.