#18231: constructing matrices is very slow
-------------------------------------+-------------------------------------
Reporter: vdelecroix | Owner:
Type: defect | Status: needs_review
Priority: major | Milestone: sage-6.7
Component: linear algebra | Resolution:
Keywords: | Merged in:
Authors: Vincent Delecroix | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/vdelecroix/18231 | da310db9b3b4238121b1a1ad2c3d5e36a5e846b5
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by vdelecroix):
* status: needs_work => needs_review
Old description:
> The problem is in the code which looks like the following
> {{{
> def test1():
> K = QuadraticField(2)
> for _ in range(100):
> i = randint(2,3)
> j = randint(2,3)
> m = matrix(K, i, j, range(i*j))
> }}}
> It causes the various matrix spaces to rebuilt almost each time! If we
> compare with
> {{{
> def test2():
> K = QuadraticField(2)
> M = {(i,j): MatrixSpace(K,i,j) for i in range(2,4) for j in
> range(2,4)}
> for _ in range(100):
> i = randint(2,3)
> j = randint(2,3)
> m = M[i,j](range(i*j))
> }}}
> then we got
> {{{
> sage: %timeit test1()
> 10 loops, best of 3: 55 ms per loop
> sage: %timeit test2()
> 100 loops, best of 3: 6.49 ms per loop
> }}}
>
> This is one of the reason why the creation of Polyhedron is so slow (see
> #18213).
New description:
The problem is in the code which looks like the following
{{{
def test1():
K = QuadraticField(2)
for _ in range(100):
i = randint(2,3)
j = randint(2,3)
m = matrix(K, i, j, range(i*j))
}}}
It causes the various matrix spaces to rebuilt almost each time! If we
compare with
{{{
def test2():
K = QuadraticField(2)
M = {(i,j): MatrixSpace(K,i,j) for i in range(2,4) for j in
range(2,4)}
for _ in range(100):
i = randint(2,3)
j = randint(2,3)
m = M[i,j](range(i*j))
}}}
then we got
{{{
sage: %timeit test1()
10 loops, best of 3: 55 ms per loop
sage: %timeit test2()
100 loops, best of 3: 6.49 ms per loop
}}}
This is one of the reason why the creation of Polyhedron is so slow (see
#18213).
In the branch we:
- replace some old Cython code in `matrix_generic_dense` and `matrix0` and
do some optimization
- move the function `_get_matrix_class` in `MatrixSpace` out of the class
(as it depends only on the base ring and the sparseness)
- In the class `MatrixSpace` the argument `__matrix_class` is now
`_matrix_class`. That way, it is possible in other part of Sage to
optimize the creation of matrices by calling directly
{{{
sage: M = MatrixSpace(ZZ,3,2)
sage: M._matrix_class([1,5,3,-1,2,3], coerce=False, copy=False)
}}}
- we simplify the main element constructor of matrix, namely
`MatrixSpace.matrix` and gain a significant speedup.
--
Comment:
Hello Nathann,
Thanks for having a look.
Replying to [comment:3 ncohen]:
> In this branch you create functions, remove others, and change a lot of
code. There is still a lot of guessing to do on the reviewer's part.
>
> It would be really cool if you could be more verbose about what you do.
Really.
I made a big effort to separate the commit at least! It is now in the
description of the ticket.
> I began to read the first commit, and I have several more specific
questions:
>
> - You modify a function which takes a `MonoidElement` as input, which
you immeditely cast with `cdef Matrix right = _right`. Either it is a
matrix and it should not read `MonoidElement` in the first place, or it is
not a `Matrix` and you cannot cast it?..
No choice. This is a cdef function defined in `structure.element.Element`
and you can not change the signature in children classes. I thought it was
more readable this way.
> - This is cool and everything to gain miliseconds, but that's not a good
way to write public code
> If the main constructor does not do what you want ty to change it.
What if somebody adds a new parameter to matrix? The code has to be
copy/pasted in every single function that did not want to call `__init__`?
All right. But then there is something wrong in the docstring of
`matrix0.Matrix`
{{{
def __init__(...):
...
Subclasses of ``Matrix`` can safely skip calling
``Matrix.__init__`` provided they take care of initializing these
attributes themselves.
...
}}}
> - Why?
All this was just old Cython code at the time Cython was not able to
understand `l[i]` when `l` is a `cdef list`.
--
Ticket URL: <http://trac.sagemath.org/ticket/18231#comment:4>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
