constructing matrices is very slow #18231

videlec · 2015-04-16T22:16:20Z

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 reasons why the creation of Polyhedron is so slow (see #18213). (This has now improved since the creation of the ticket)

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.

follow up: #18258

CC: @nathanncohen

Component: linear algebra

Issue created by migration from https://trac.sagemath.org/ticket/18231

The text was updated successfully, but these errors were encountered:

videlec · 2015-04-18T22:50:34Z

Author: Vincent Delecroix

videlec · 2015-04-18T22:50:34Z

Commit: c1c7034

videlec · 2015-04-18T22:50:34Z

comment:1

I only did some cleanup in matrix_space.py and matrix_generic_dense.pyx. And there is a substantial gain in speed! The tiny modification in #18213 to NumberField.__cmp__ actually makes a much bigger difference.

I did not solve the problem of the matrix space being rebuilt every time.

New commits:

`f6a87ed`	`Trac 18231: better code in matrices`
`d834354`	`Trac 18231: move _get_matrix_class out of the class`
`d52a63d`	`Trac 18231: constructor + __matrix_class -> _matrix_class`
`ecd6e27`	`Trac 18231: removed unused import`
`a23d09c`	`Trac 18231: get rid of a one year old deprecation`
`6e9aab1`	`Trac 18231: remove a useless function`
`95c9dfe`	`Trac 18231: set .__call__() as an alias of .matrix()`
`6dbf25e`	`Trac 18231: rewrite .matrix()`
`c1c7034`	`Trac 18231: fix dict_to_list`

videlec · 2015-04-18T22:50:34Z

Branch: u/vdelecroix/18231

sagetrac-git · 2015-04-18T22:56:10Z

Branch pushed to git repo; I updated commit sha1. New commits:

`da310db`	`Trac 18231: typo`

sagetrac-git · 2015-04-18T22:56:10Z

Changed commit from c1c7034 to da310db

nathanncohen · 2015-04-19T06:41:15Z

comment:3

Hello Vincent,

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

This is cool and everything to gain miliseconds, but that's not a good way to write public code

-        matrix.Matrix.__init__(self, parent)
+        # the four lines below avoid the following call
+        # matrix.Matrix.__init__(self, parent)
+        self._parent = parent
+        res._ncols  = parent.ncols()
+        res._nrows  = parent.nrows()
+        R = res._base_ring = parent.base_ring()

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__?

Why?


     cdef set_unsafe(self, Py_ssize_t i, Py_ssize_t j, value):
-        Py_DECREF(<object>PyList_GET_ITEM(self._entries, i*self._ncols + j))
-        Py_INCREF(value)
-        PyList_SET_ITEM(self._entries, i*self._ncols + j, value)
+        self._entries[i*self._ncols + j] = value
 
     cdef get_unsafe(self, Py_ssize_t i, Py_ssize_t j):
-        return <object>PyList_GET_ITEM(self._entries, i*self._ncols + j)
+        return self._entries[i*self._ncols + j]

Nathann

videlec · 2015-04-19T09:52:48Z

comment:4

Hello Nathann,

Thanks for having a look.

Replying to @nathanncohen:

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.

sagetrac-git · 2015-04-19T10:47:02Z

Branch pushed to git repo; I updated commit sha1. New commits:

`88525b8`	`Trac 18231: fix documentation`

sagetrac-git · 2015-04-19T10:47:02Z

Changed commit from da310db to 88525b8

sagetrac-git · 2015-04-19T12:53:21Z

Branch pushed to git repo; I updated commit sha1. New commits:

`715f49e`	`Trac 18231: fix doctests`

sagetrac-git · 2015-04-19T12:53:21Z

Changed commit from 88525b8 to 715f49e

nathanncohen · 2015-04-19T19:15:22Z

comment:7

Yoooooo !

I made a big effort to separate the commit at least! It is now in the description of the ticket.

Thanks

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.

Oh, okay!

All right. But then there is something wrong in the docstring of matrix0.Matrix

Hmmmm.... Can you at least observe the difference? All that this __init__ function does is precisely what you do. Can you measure this function call when your function copies lists around? O_o

All this was just old Cython code at the time Cython was not able to understand l[i] when l is a cdef list.

Okay!

Nathann

nathanncohen · 2015-04-19T19:19:51Z

comment:8

Okay, I give up. Sorry, I just don't know these classes enough, I barely ever used them, I would do a terrible job as a reviewer.

Nathann

fchapoton · 2015-08-09T18:43:14Z

comment:10

needs rebase, does not apply

sagetrac-git · 2015-08-13T13:54:24Z

Changed commit from 715f49e to d4fc6cd

sagetrac-git · 2015-08-13T13:54:24Z

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

`2d55497`	`Trac 18231: constructor + __matrix_class -> _matrix_class`
`5ac117f`	`Trac 18231: removed unused import`
`fcd06fa`	`Trac 18231: get rid of a one year old deprecation`
`b7bf1aa`	`Trac 18231: remove a useless function`
`12c9d0e`	`Trac 18231: set .__call__() as an alias of .matrix()`
`d59a9db`	`Trac 18231: rewrite .matrix()`
`46d8b6b`	`Trac 18231: fix dict_to_list`
`aa7ddb2`	`Trac 18231: typo`
`03fe3b1`	`Trac 18231: fix documentation`
`d4fc6cd`	`Trac 18231: fix doctests`

videlec · 2015-08-13T15:01:15Z

Dependencies: #18231

videlec · 2015-08-13T15:01:29Z

Changed dependencies from #18231 to #19026

sagetrac-git · 2015-08-13T15:06:06Z

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

`268cfc3`	`Trac 18231: move _get_matrix_class out of the class`
`66e5068`	`Trac 18231: constructor + __matrix_class -> _matrix_class`
`c9a82f2`	`Trac 18231: removed unused import`
`321d073`	`Trac 18231: get rid of a one year old deprecation`
`6111c37`	`Trac 18231: remove a useless function`
`cb6b82d`	`Trac 18231: set .__call__() as an alias of .matrix()`
`2dd0d09`	`Trac 18231: rewrite .matrix()`
`00dd4ac`	`Trac 18231: fix dict_to_list`
`07ba681`	`Trac 18231: fix documentation`
`742de47`	`Trac 18231: fix doctests`

sagetrac-git · 2015-08-13T15:06:06Z

Changed commit from d4fc6cd to 742de47

videlec · 2015-08-13T15:06:41Z

comment:16

I moved the first commit to another ticket (#19026).

fchapoton · 2015-09-11T06:44:11Z

comment:17

needs rebase

mkoeppe · 2022-02-19T18:22:28Z

Changed author from Vincent Delecroix to none

mkoeppe · 2022-02-19T18:22:28Z

comment:19

Outdated, this was fixed in #24742.

sage: %timeit test1()
3.91 ms ± 47.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
sage: %timeit test2()
3.03 ms ± 19.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

videlec · 2022-02-19T18:51:44Z

Changed dependencies from #19026 to none

videlec · 2022-02-19T18:51:44Z

Changed branch from u/vdelecroix/18231 to none

videlec · 2022-02-19T18:51:44Z

Changed commit from 742de47 to none

videlec added this to the sage-6.7 milestone Apr 16, 2015

videlec added c: linear algebra labels Apr 16, 2015

videlec added the s: needs review label Apr 18, 2015

nathanncohen mannequin added s: needs work and removed s: needs review labels Apr 19, 2015

This comment has been minimized.

Sign in to view

videlec added s: needs review and removed s: needs work labels Apr 19, 2015

This comment has been minimized.

Sign in to view

fchapoton added s: needs work and removed s: needs review labels Aug 9, 2015

videlec added the s: needs review label Aug 13, 2015

videlec added s: needs work and removed s: needs review labels Aug 13, 2015

videlec added s: needs review and removed s: needs work labels Aug 13, 2015

fchapoton added s: needs work and removed s: needs review labels Sep 11, 2015

This comment has been minimized.

Sign in to view

mkoeppe added s: needs review and removed s: needs work labels Feb 19, 2022

mkoeppe removed this from the sage-6.7 milestone Feb 19, 2022

videlec added s: positive review and removed s: needs review labels Feb 19, 2022

fchapoton removed the s: positive review label Feb 25, 2022

fchapoton closed this as completed Feb 25, 2022

fchapoton added r: duplicate and removed p: major / 3 labels Feb 25, 2022

This was referenced Apr 19, 2015

Great speedup in polytopes construction with generic backend #18241

Closed

Fix coercion for matrix groups / matrix spaces #18258

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

constructing matrices is very slow #18231

constructing matrices is very slow #18231

videlec commented Apr 16, 2015

videlec commented Apr 18, 2015

videlec commented Apr 18, 2015

videlec commented Apr 18, 2015

videlec commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

nathanncohen mannequin commented Apr 19, 2015

This comment has been minimized.

videlec commented Apr 19, 2015

sagetrac-git mannequin commented Apr 19, 2015

sagetrac-git mannequin commented Apr 19, 2015

sagetrac-git mannequin commented Apr 19, 2015

sagetrac-git mannequin commented Apr 19, 2015

nathanncohen mannequin commented Apr 19, 2015

nathanncohen mannequin commented Apr 19, 2015

This comment has been minimized.

fchapoton commented Aug 9, 2015

sagetrac-git mannequin commented Aug 13, 2015

sagetrac-git mannequin commented Aug 13, 2015

videlec commented Aug 13, 2015

videlec commented Aug 13, 2015

sagetrac-git mannequin commented Aug 13, 2015

sagetrac-git mannequin commented Aug 13, 2015

videlec commented Aug 13, 2015

fchapoton commented Sep 11, 2015

This comment has been minimized.

mkoeppe commented Feb 19, 2022

mkoeppe commented Feb 19, 2022

videlec commented Feb 19, 2022

videlec commented Feb 19, 2022

videlec commented Feb 19, 2022

constructing matrices is very slow #18231

constructing matrices is very slow #18231

Comments

videlec commented Apr 16, 2015

videlec commented Apr 18, 2015

videlec commented Apr 18, 2015

videlec commented Apr 18, 2015

videlec commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

sagetrac-git mannequin commented Apr 18, 2015

nathanncohen mannequin commented Apr 19, 2015

This comment has been minimized.

videlec commented Apr 19, 2015

sagetrac-git mannequin commented Apr 19, 2015

sagetrac-git mannequin commented Apr 19, 2015

sagetrac-git mannequin commented Apr 19, 2015

sagetrac-git mannequin commented Apr 19, 2015

nathanncohen mannequin commented Apr 19, 2015

nathanncohen mannequin commented Apr 19, 2015

This comment has been minimized.

fchapoton commented Aug 9, 2015

sagetrac-git mannequin commented Aug 13, 2015

sagetrac-git mannequin commented Aug 13, 2015

videlec commented Aug 13, 2015

videlec commented Aug 13, 2015

sagetrac-git mannequin commented Aug 13, 2015

sagetrac-git mannequin commented Aug 13, 2015

videlec commented Aug 13, 2015

fchapoton commented Sep 11, 2015

This comment has been minimized.

mkoeppe commented Feb 19, 2022

mkoeppe commented Feb 19, 2022

videlec commented Feb 19, 2022

videlec commented Feb 19, 2022

videlec commented Feb 19, 2022