Opened 6 years ago

Closed 6 years ago

#11657 closed defect (fixed)

the vector(...) function is extremely slow

Reported by: was Owned by: jason, was
Priority: minor Milestone: sage-4.7.2
Component: linear algebra Keywords: sd32
Cc: Merged in: sage-4.7.2.alpha3
Authors: William Stein, Rob Beezer Reviewers: Rob Beezer, William Stein
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by rbeezer)

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

Attachments (3)

trac_11657-zero-vector-speedup.patch (3.7 KB) - added by rbeezer 6 years ago.
trac_11657-rewrite.patch (7.8 KB) - added by was 6 years ago.
apply only this; total rewrite of the previous patch
trac_11657-zero-vector-edits.patch (2.0 KB) - added by rbeezer 6 years ago.

Download all attachments as: .zip

Change History (12)

comment:1 Changed 6 years ago by 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.

Changed 6 years ago by rbeezer

comment:2 Changed 6 years ago by rbeezer

  • Authors set to Rob Beezer
  • Description modified (diff)
  • Status changed from new to needs_review

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

comment:3 Changed 6 years ago by 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

Changed 6 years ago by was

apply only this; total rewrite of the previous patch

comment:4 follow-up: Changed 6 years ago by 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.

comment:5 in reply to: ↑ 4 Changed 6 years ago by rbeezer

  • Status changed from needs_review to needs_info

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?

Changed 6 years ago by rbeezer

comment:6 Changed 6 years ago by rbeezer

  • Authors changed from Rob Beezer to William Stein, Rob Beezer
  • Description modified (diff)
  • Reviewers set to Rob Beezer, William Stein
  • Status changed from needs_info to needs_review

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

comment:7 Changed 6 years ago by rbeezer

  • Keywords sd32 added

comment:8 Changed 6 years ago by was

  • Status changed from needs_review to positive_review

Looks great -- thanks for the cleanup!

comment:9 Changed 6 years ago by leif

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