Opened 6 years ago

Last modified 4 years ago

#18231 needs_work defect

constructing matrices is very slow

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.7
Component: linear algebra Keywords:
Cc: ncohen Merged in:
Authors: Vincent Delecroix Reviewers:
Report Upstream: N/A Work issues:
Branch: u/vdelecroix/18231 (Commits, GitHub, GitLab) Commit: 742de47c66db9df0eee3f6200a0b8d2764ab743e
Dependencies: #19026 Stopgaps:

Status badges

Description (last modified by jipilab)

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

Change History (18)

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:

f6a87edTrac 18231: better code in matrices
d834354Trac 18231: move _get_matrix_class out of the class
d52a63dTrac 18231: constructor + __matrix_class -> _matrix_class
ecd6e27Trac 18231: removed unused import
a23d09cTrac 18231: get rid of a one year old deprecation
6e9aab1Trac 18231: remove a useless function
95c9dfeTrac 18231: set .__call__() as an alias of .matrix()
6dbf25eTrac 18231: rewrite .matrix()
c1c7034Trac 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:

da310dbTrac 18231: typo

comment:3 follow-up: 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: Changed 6 years ago by vdelecroix

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

Hello Nathann,

Thanks for having a look.

Replying to 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.

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:

88525b8Trac 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:

715f49eTrac 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:

2d55497Trac 18231: constructor + __matrix_class -> _matrix_class
5ac117fTrac 18231: removed unused import
fcd06faTrac 18231: get rid of a one year old deprecation
b7bf1aaTrac 18231: remove a useless function
12c9d0eTrac 18231: set .__call__() as an alias of .matrix()
d59a9dbTrac 18231: rewrite .matrix()
46d8b6bTrac 18231: fix dict_to_list
aa7ddb2Trac 18231: typo
03fe3b1Trac 18231: fix documentation
d4fc6cdTrac 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:

268cfc3Trac 18231: move _get_matrix_class out of the class
66e5068Trac 18231: constructor + __matrix_class -> _matrix_class
c9a82f2Trac 18231: removed unused import
321d073Trac 18231: get rid of a one year old deprecation
6111c37Trac 18231: remove a useless function
cb6b82dTrac 18231: set .__call__() as an alias of .matrix()
2dd0d09Trac 18231: rewrite .matrix()
00dd4acTrac 18231: fix dict_to_list
07ba681Trac 18231: fix documentation
742de47Trac 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.