Opened 10 years ago

Closed 10 years ago

# Optimize CombinatorialFreeModule.Element._vector_

Reported by: Owned by: nthiery jason, was major sage-5.5 linear algebra sage-combinat, bump, mguaypaq sage-5.5.beta0 Nicolas M. Thiéry Mathieu Guay-Paquet, Franco Saliola, N/A

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

### comment:1 Changed 10 years ago by nthiery

Description: modified (diff)

### comment:2 follow-up:  3 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

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

Hi Franco,

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

Hi Franco,

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: new → needs_review

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

Cc: mguaypaq added modified (diff) 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 in reply to:  9 Changed 10 years ago by nthiery

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) → Mathieu Guay-Paquet, Franco Saliola, 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 mguaypaq

Description: modified (diff) 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 jdemeyer

Milestone: sage-5.4 → sage-5.5

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

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: → sage-5.5.beta0 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.