#11657: the vector(...) function is extremely slow
------------------------------+---------------------------------------------
Reporter: was | Owner: jason, was
Type: defect | Status: needs_review
Priority: minor | Milestone: sage-4.7.2
Component: linear algebra | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author: Rob Beezer
Merged: | Dependencies:
------------------------------+---------------------------------------------
Changes (by newvalueoldvalue):
* status: new => needs_review
* author: => Rob Beezer
Old description:
> 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.
New description:
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. [attachment:trac_11657-zero-vector-speedup.patch]
--
Comment:
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
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11657#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
