Opened 6 years ago

# constructing matrices is very slow

Reported by: Owned by: vdelecroix major sage-6.7 linear algebra ncohen Vincent Delecroix N/A u/vdelecroix/18231 742de47c66db9df0eee3f6200a0b8d2764ab743e #19026

The problem is in the code which looks like the following

```def test1():
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():
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.

### comment:1 Changed 6 years ago by vdelecroix

• Authors set to Vincent Delecroix
• Branch set to u/vdelecroix/18231
• Commit set to c1c7034ed54c7493a7fedbf6fa9798f23946902c
• Status changed from new to needs_review

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`

### comment:2 Changed 6 years ago by git

• Commit changed from c1c7034ed54c7493a7fedbf6fa9798f23946902c to da310db9b3b4238121b1a1ad2c3d5e36a5e846b5

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

 ​da310db `Trac 18231: typo`

### comment:3 follow-up: ↓ 4 Changed 6 years ago by ncohen

• Status changed from needs_review to needs_work

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

### comment:4 in reply to: ↑ 3 ; follow-up: ↓ 7 Changed 6 years ago by vdelecroix

• Description modified (diff)
• Status changed from needs_work to needs_review

Hello Nathann,

Thanks for having a look.

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

### comment:5 Changed 6 years ago by git

• Commit changed from da310db9b3b4238121b1a1ad2c3d5e36a5e846b5 to 88525b82a790bb4903ab19757acc7a3acd01da72

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

 ​88525b8 `Trac 18231: fix documentation`

### comment:6 Changed 6 years ago by git

• Commit changed from 88525b82a790bb4903ab19757acc7a3acd01da72 to 715f49ecab8ae8bb66725be77da51ce6eb8f8738

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

 ​715f49e `Trac 18231: fix doctests`

### comment:7 in reply to: ↑ 4 Changed 6 years ago by ncohen

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

### comment:8 Changed 6 years ago by ncohen

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

### comment:9 Changed 6 years ago by vdelecroix

• Description modified (diff)

### comment:10 Changed 6 years ago by chapoton

• Status changed from needs_review to needs_work

needs rebase, does not apply

### comment:11 Changed 6 years ago by git

• Commit changed from 715f49ecab8ae8bb66725be77da51ce6eb8f8738 to d4fc6cd87dc244113d7662b95a3d1c4f10258a36

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`

### comment:12 Changed 6 years ago by vdelecroix

• Status changed from needs_work to needs_review

Whether to see if patchbot is happy.

### comment:13 Changed 6 years ago by vdelecroix

• Dependencies set to #18231
• Status changed from needs_review to needs_work

### comment:14 Changed 6 years ago by vdelecroix

• Dependencies changed from #18231 to #19026

### comment:15 Changed 6 years ago by git

• Commit changed from d4fc6cd87dc244113d7662b95a3d1c4f10258a36 to 742de47c66db9df0eee3f6200a0b8d2764ab743e

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`

### comment:16 Changed 6 years ago by vdelecroix

• Status changed from needs_work to needs_review

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

### comment:17 Changed 6 years ago by chapoton

• Status changed from needs_review to needs_work

needs rebase

### comment:18 Changed 4 years ago by jipilab

• Description modified (diff)
Note: See TracTickets for help on using tickets.