Optimize CombinatorialFreeModule.Element._vector_

[nthiery]

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

[chapoton]

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

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

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

[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?

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

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

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

[mguaypaq]

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?

[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!

[nthiery]

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

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

[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!