the vector(...) function is extremely slow

[was]

I was shocked by this:

sage: timeit('vector(ZZ,100)')
625 loops, best of 3: 302 µs per loop
sage: timeit('(ZZ^100)(0)')
625 loops, best of 3: 24.9 µs per loop
sage: timeit('(ZZ^100).zero_vector()')
625 loops, best of 3: 21.8 µs per loop

I didn't realize that the special case of the zero vector is incredibly slow for the vector function. This needs to be fixed.

Apply:

1. trac_11657-rewrite.patch
2. trac_11657-zero-vector-edits.patch

[rbeezer]

The vector constructor has to do a fair amount of checking to accomodate all of its flexibility. There is a numpy type check that could probably go away due to a subsequent call to Sequence() in prepare(), though it does not appear this is the problem (verbose() says 0.0 seconds, is it granular enough?).

I think this Sequence call is used to find a common parent for the types of the entries. However, it is about 1/3 of the time.

sage: timeit('vector(ZZ,100)')
625 loops, best of 3: 231 µs per loop
sage: timeit('(ZZ^100).zero_vector()')
625 loops, best of 3: 11.2 µs per loop
sage: timeit("Sequence(v)")
625 loops, best of 3: 69.5 µs per loop

It would be possible to have the routine return the zero vector sooner, since there is no type checking involved. With a crude fix that passes all tests in sage/matrix, sage/modules, there is an improvement, but still slower.

sage: sage: timeit('vector(ZZ,100)')
625 loops, best of 3: 43.9 µs per loop

Trouble is we need to support two-argument calls like

vector(range(5), ZZ)

and so need to do some type-checking on the arguments, though maybe it could be reduced slightly.

[rbeezer]

Patch generally improves speed of conveniences (constructors) for creating zero vectors. Fastest route seems to usually be the .zero_vector() method of a module, which just barely beats coercing a zero scalar into the module most of the time.

The zero_vector() *constructor function* now uses the .zero_vector() *method*, and the vector() method short-circuits to return a zero vector just as soon as possible. The multi-format capabilities of the vector() constructor require some necessary overhead, which seems to be a constant 30 micro-seconds on my machine.

Additions to documentation provide advice for the truly speed-hungry.

4.7.1, without patch:

sage: n = 1000
sage: timeit("(ZZ^n).zero_vector()")
625 loops, best of 3: 69.9 µs per loop
sage: timeit("(ZZ^n)(0)")
625 loops, best of 3: 74.6 µs per loop
sage: timeit("zero_vector(ZZ, n)")
125 loops, best of 3: 2.55 ms per loop
sage: timeit("vector(ZZ, n)")
125 loops, best of 3: 2.52 ms per loop

sage: n = 10000
sage: timeit("(ZZ^n).zero_vector()")
625 loops, best of 3: 613 µs per loop
sage: timeit("(ZZ^n)(0)")
625 loops, best of 3: 617 µs per loop
sage: timeit("zero_vector(ZZ, n)")
25 loops, best of 3: 24.8 ms per loop
sage: timeit("vector(ZZ, n)")
25 loops, best of 3: 24.9 ms per loop

4.7.1, with patch:

sage: n = 1000
sage: timeit("(ZZ^n).zero_vector()")
625 loops, best of 3: 73.9 µs per loop
sage: timeit("(ZZ^n)(0)")
625 loops, best of 3: 77.2 µs per loop
sage: timeit("zero_vector(ZZ, n)")
625 loops, best of 3: 78.1 µs per loop
sage: timeit("vector(ZZ, n)")
625 loops, best of 3: 109 µs per loop

sage: n = 10000
sage: timeit("(ZZ^n).zero_vector()")
625 loops, best of 3: 624 µs per loop
sage: timeit("(ZZ^n)(0)")
625 loops, best of 3: 621 µs per loop
sage: timeit("zero_vector(ZZ, n)")
625 loops, best of 3: 624 µs per loop
sage: timeit("vector(ZZ, n)")
625 loops, best of 3: 654 µs per loop

[was]

Your examples above, with large n, are probably unfair, since they are much less likely. I'm still concerned by how very slow this is with smaller n, e.g., even with your patch:

sage:  timeit('vector(ZZ,50)') 
625 loops, best of 3: 44.3 µs per loop
sage:  timeit('(ZZ^50).zero_vector()') 
625 loops, best of 3: 9.58 µs per loop

I'm posting a new version of your patch that is pretty much "optimal":

sage: timeit('vector(ZZ,50)') 
625 loops, best of 3: 9.7 µs per loop

[was]

apply only this; total rewrite of the previous patch

[was]

Now Rob (say) has to review this new patch. It significantly speeds up vector and zero_vector. It also moves some error checking to FreeModule?, where it belongs.

[rbeezer]

Replying to was:

Now Rob (say) has to review this new patch.

Yes, I've got it. Looks good and nearly optimal. Nothing much to add in the way of performance.

Comments:

Line 127 - typo in comments "slowedue"

Line 447 - return statement with zero vector should now be dead code - at least we want it to be. Commenting-it out and running tests confirms. The comment preceding needs adjustment.

Line 665 - is the whole discussion about "or" now moot with the super-fast is_Ring() defined earlier?

Line 670 - error message: can we say "first argument must be a ring" rather than "arg0 must be a ring"?

Reactions? I can make a follow-up patch for you to review, or vice-versa?

[rbeezer]

"rewrite" patch has positive review from me.

"edits" patch addresses all four comments above. Needs review.

Combination of two patches passes all tests. Timings are now very similar for all four ways to get a zero vector - within about 3 microseconds difference in overhead.

[was]

Looks great -- thanks for the cleanup!