#11589: faster zero matrix creation
------------------------------+---------------------------------------------
Reporter: malb | Owner: jason, was
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.7.2
Component: linear algebra | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author: Martin Albrecht, Simon King
Merged: | Dependencies:
------------------------------+---------------------------------------------
Changes (by SimonKing):
* status: new => needs_review
Comment:
I made all matrices accept "None" as an argument.
I tried to determine the threshold for copying versus creating a zero
matrix, using the following test function:
{{{
sage: def tests(R):
....: BetterCopy = []
....: for d in srange(10,511,20):
....: MS = MatrixSpace(R,d)
....: MS._copy_zero = True
....: globals()['d'] = d
....: globals()['R'] = R
....: TCopy = timeit.eval("M = matrix(R,d,d)",number=1000)
....: MS._copy_zero = False
....: TNoCopy = timeit.eval("M = matrix(R,d,d)",number=1000)
....: if TCopy.stats[3] < TNoCopy.stats[3]:
....: BetterCopy.append((d,TCopy,TNoCopy))
....: return BetterCopy
....:
}}}
It turns out that with both patches applied, copying is not a good idea
over GF(2) and over the rationals:
{{{
sage: tests(GF(2))
[]
sage: tests(QQ)
[]
}}}
Note that I observed that the memory consumption for the test over the
rationals constantly increased: Perhaps there is a memory leak.
However, in all other cases I studied, copying was better, for matrices of
up to 30 rows and columns:
{{{
sage: tests(GF(3))
[(10, 1000 loops, best of 3: 48.2 µs per loop, 1000 loops, best of 3: 49
µs per loop), (30, 1000 loops, best of 3: 50 µs per loop, 1000 loops, best
of 3: 50.9 µs per loop)]
sage: tests(GF(1019))
[(10, 1000 loops, best of 3: 48.3 µs per loop, 1000 loops, best of 3: 49.2
µs per loop)]
sage: tests(GF(625,'a'))
[(10, 1000 loops, best of 3: 45.1 µs per loop, 1000 loops, best of 3: 63.1
µs per loop), (30, 1000 loops, best of 3: 62.9 µs per loop, 1000 loops,
best of 3: 68 µs per loop), (230, 1000 loops, best of 3: 1.15 ms per loop,
1000 loops, best of 3: 367 µs per loop), (250, 1000 loops, best of 3: 1.35
ms per loop, 1000 loops, best of 3: 423 µs per loop), (270, 1000 loops,
best of 3: 1.71 ms per loop, 1000 loops, best of 3: 618 µs per loop),
(290, 1000 loops, best of 3: 1.95 ms per loop, 1000 loops, best of 3: 701
µs per loop), (310, 1000 loops, best of 3: 2.23 ms per loop, 1000 loops,
best of 3: 791 µs per loop), (330, 1000 loops, best of 3: 2.52 ms per
loop, 1000 loops, best of 3: 883 µs per loop), (350, 1000 loops, best of
3: 2.82 ms per loop, 1000 loops, best of 3: 988 µs per loop)]
sage: tests(ZZ)
[(10, 625 loops, best of 3: 48.6 µs per loop, 625 loops, best of 3: 56.5
µs per loop), (30, 625 loops, best of 3: 111 µs per loop, 625 loops, best
of 3: 118 µs per loop), (50, 625 loops, best of 3: 230 µs per loop, 625
loops, best of 3: 235 µs per loop)]
}}}
Therefore, I modified the threshold in `_copy_zero` a bit. There is no
special case for `Matrix_modn_dense`, but for `Matrix_rational_dense`.
Here are timings similar to the ones you did above (adding another test
case).
With both patches:
{{{
sage: for n in (50,500,1000): timeit('A=matrix(GF(2),%d,%d)'%(n,n))
....:
625 loops, best of 3: 105 µs per loop
625 loops, best of 3: 108 µs per loop
625 loops, best of 3: 116 µs per loop
sage: for n in (50,500,1000): timeit('A=matrix(GF(3),%d,%d)'%(n,n))
....:
625 loops, best of 3: 103 µs per loop
625 loops, best of 3: 403 µs per loop
625 loops, best of 3: 1.3 ms per loop
sage: for n in (50,500,1000): timeit('A=matrix(GF(625,"a"),%d,%d)'%(n,n))
....:
625 loops, best of 3: 198 µs per loop
125 loops, best of 3: 1.97 ms per loop
125 loops, best of 3: 7.29 ms per loop
}}}
Without patches:
{{{
sage: for n in (50,500,1000): timeit('A=matrix(GF(2),%d,%d)'%(n,n))
....:
625 loops, best of 3: 108 µs per loop
625 loops, best of 3: 116 µs per loop
625 loops, best of 3: 137 µs per loop
sage: for n in (50,500,1000): timeit('A=matrix(GF(3),%d,%d)'%(n,n))
....:
625 loops, best of 3: 103 µs per loop
625 loops, best of 3: 566 µs per loop
125 loops, best of 3: 2.46 ms per loop
sage: for n in (50,500,1000): timeit('A=matrix(GF(625,"a"),%d,%d)'%(n,n))
....:
625 loops, best of 3: 225 µs per loop
125 loops, best of 3: 5.95 ms per loop
25 loops, best of 3: 22.9 ms per loop
}}}
So, with both patches applied, the timings consistently improve.
'''__Reviewing__'''
I am not sure how the reviewing should be done, as we are both authors. Do
you think it is ok if I review the first patch and you review the second
patch? I need to run all long doctests, though; so far, I only did the
tests in sage/matrix.
'''__TODO__'''
On a different ticket, the potential memory leak for rational dense
matrices should be studied.
I recall that in some arithmetic routines of matrices, zero matrices are
created at the beginning. I am not sure whether that is done "the official
way" or by ''always'' copying a zero matrix, but I think it was the
latter. That might be worth while to fix as well.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11589#comment:9>
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.
