Sage: Ticket #11657: the vector(...) function is extremely slow
https://trac.sagemath.org/ticket/11657
<p>
I was shocked by this:
</p>
<pre class="wiki">
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
</pre><p>
I didn't realize that the special case of the zero vector is incredibly slow for the <code>vector</code> function. This needs to be fixed.
</p>
<p>
<strong>Apply</strong>:
</p>
<ol><li> <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11657/trac_11657-rewrite.patch" title="Attachment 'trac_11657-rewrite.patch' in Ticket #11657">trac_11657-rewrite.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11657/trac_11657-rewrite.patch" title="Download"></a>
</li><li> <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11657/trac_11657-zero-vector-edits.patch" title="Attachment 'trac_11657-zero-vector-edits.patch' in Ticket #11657">trac_11657-zero-vector-edits.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11657/trac_11657-zero-vector-edits.patch" title="Download"></a>
</li></ol>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/11657
Trac 1.1.6rbeezerSat, 06 Aug 2011 22:08:12 GMT
https://trac.sagemath.org/ticket/11657#comment:1
https://trac.sagemath.org/ticket/11657#comment:1
<p>
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?).
</p>
<p>
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.
</p>
<pre class="wiki">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
</pre><p>
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.
</p>
<pre class="wiki">sage: sage: timeit('vector(ZZ,100)')
625 loops, best of 3: 43.9 µs per loop
</pre><p>
Trouble is we need to support two-argument calls like
</p>
<pre class="wiki">vector(range(5), ZZ)
</pre><p>
and so need to do <em>some</em> type-checking on the arguments, though maybe it could be reduced slightly.
</p>
TicketrbeezerWed, 24 Aug 2011 19:51:51 GMTattachment set
https://trac.sagemath.org/ticket/11657
https://trac.sagemath.org/ticket/11657
<ul>
<li><strong>attachment</strong>
set to <em>trac_11657-zero-vector-speedup.patch</em>
</li>
</ul>
TicketrbeezerWed, 24 Aug 2011 19:55:11 GMTstatus, description changed; author set
https://trac.sagemath.org/ticket/11657#comment:2
https://trac.sagemath.org/ticket/11657#comment:2
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11657?action=diff&version=2">diff</a>)
</li>
<li><strong>author</strong>
set to <em>Rob Beezer</em>
</li>
</ul>
<p>
Patch generally improves speed of conveniences (constructors) for creating zero vectors. Fastest route seems to usually be the <code>.zero_vector()</code> method of a module, which just barely beats coercing a zero scalar into the module most of the time.
</p>
<p>
The <code>zero_vector()</code> *constructor function* now uses the <code>.zero_vector()</code> *method*, and the <code>vector()</code> method short-circuits to return a zero vector just as soon as possible. The multi-format capabilities of the <code>vector()</code> constructor require some necessary overhead, which seems to be a constant 30 micro-seconds on my machine.
</p>
<p>
Additions to documentation provide advice for the truly speed-hungry.
</p>
<p>
4.7.1, without patch:
</p>
<pre class="wiki">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
</pre><p>
4.7.1, with patch:
</p>
<pre class="wiki">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
</pre>
TicketwasWed, 24 Aug 2011 20:55:20 GMT
https://trac.sagemath.org/ticket/11657#comment:3
https://trac.sagemath.org/ticket/11657#comment:3
<p>
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:
</p>
<pre class="wiki">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
</pre><p>
I'm posting a new version of your patch that is pretty much "optimal":
</p>
<pre class="wiki">sage: timeit('vector(ZZ,50)')
625 loops, best of 3: 9.7 µs per loop
</pre>
TicketwasWed, 24 Aug 2011 21:22:16 GMTattachment set
https://trac.sagemath.org/ticket/11657
https://trac.sagemath.org/ticket/11657
<ul>
<li><strong>attachment</strong>
set to <em>trac_11657-rewrite.patch</em>
</li>
</ul>
<p>
apply only this; total rewrite of the previous patch
</p>
TicketwasWed, 24 Aug 2011 21:23:39 GMT
https://trac.sagemath.org/ticket/11657#comment:4
https://trac.sagemath.org/ticket/11657#comment:4
<p>
Now Rob (say) has to review this new patch. It significantly speeds up vector and zero_vector. It also moves some error checking to <a class="missing wiki">FreeModule?</a>, where it belongs.
</p>
TicketrbeezerWed, 24 Aug 2011 23:04:00 GMTstatus changed
https://trac.sagemath.org/ticket/11657#comment:5
https://trac.sagemath.org/ticket/11657#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11657#comment:4" title="Comment 4">was</a>:
</p>
<blockquote class="citation">
<p>
Now Rob (say) has to review this new patch.
</p>
</blockquote>
<p>
Yes, I've got it. Looks good and <em>nearly</em> optimal. Nothing much to add in the way of performance.
</p>
<p>
Comments:
</p>
<p>
Line 127 - typo in comments "slowedue"
</p>
<p>
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.
</p>
<p>
Line 665 - is the whole discussion about "or" now moot with the super-fast <code></code>is_Ring()<code></code> defined earlier?
</p>
<p>
Line 670 - error message: can we say "first argument must be a ring" rather than "arg0 must be a ring"?
</p>
<p>
Reactions? I can make a follow-up patch for you to review, or vice-versa?
</p>
TicketrbeezerThu, 25 Aug 2011 00:30:17 GMTattachment set
https://trac.sagemath.org/ticket/11657
https://trac.sagemath.org/ticket/11657
<ul>
<li><strong>attachment</strong>
set to <em>trac_11657-zero-vector-edits.patch</em>
</li>
</ul>
TicketrbeezerThu, 25 Aug 2011 00:35:13 GMTstatus, description, author changed; reviewer set
https://trac.sagemath.org/ticket/11657#comment:6
https://trac.sagemath.org/ticket/11657#comment:6
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Rob Beezer, William Stein</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11657?action=diff&version=6">diff</a>)
</li>
<li><strong>author</strong>
changed from <em>Rob Beezer</em> to <em>William Stein, Rob Beezer</em>
</li>
</ul>
<p>
"rewrite" patch has positive review from me.
</p>
<p>
"edits" patch addresses all four comments above. Needs review.
</p>
<p>
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.
</p>
TicketrbeezerThu, 25 Aug 2011 18:55:49 GMTkeywords set
https://trac.sagemath.org/ticket/11657#comment:7
https://trac.sagemath.org/ticket/11657#comment:7
<ul>
<li><strong>keywords</strong>
<em>sd32</em> added
</li>
</ul>
TicketwasFri, 26 Aug 2011 00:50:01 GMTstatus changed
https://trac.sagemath.org/ticket/11657#comment:8
https://trac.sagemath.org/ticket/11657#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Looks great -- thanks for the cleanup!
</p>
TicketleifSat, 17 Sep 2011 05:03:30 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/11657#comment:9
https://trac.sagemath.org/ticket/11657#comment:9
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.7.2.alpha3</em>
</li>
</ul>
Ticket