Opened 9 years ago

Closed 9 years ago

#13949 closed enhancement (fixed)

Make mutability on matrices a simple bint flag

Reported by: nbruin Owned by: jason, was
Priority: major Milestone: sage-5.7
Component: linear algebra Keywords:
Cc: tkluck, roed Merged in: sage-5.7.beta3
Authors: Nils Bruin Reviewers: David Loeffler
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by davidloeffler)

Presently, proper initialization of a Matrix (inherited) object implies the creation of a Mutability object, which needs a memory allocation of its own. Since it's just a single flag, Matrix can just have this without linking to a separate class. Hopefully this speeds up Matrix creation sufficiently that sage.matrix.matrix_integer_2x2 can afford to just call it.

See this sage-devel thread.


Instructions:

Attachments (3)

trac_13949-change_mutability.patch (10.3 KB) - added by nbruin 9 years ago.
change to a simple flag _is_immutable om Matrix
trac_13949-fix_integer_dense_cinit.patch (3.2 KB) - added by nbruin 9 years ago.
improve efficiency of integer_dense initialization
trac_13949-doctest.patch (797 bytes) - added by davidloeffler 9 years ago.
Add doctest

Download all attachments as: .zip

Change History (21)

comment:1 follow-up: Changed 9 years ago by nbruin

First attempt: straightforward exercise. Things of note:

  • I changed the name of the attribute to Matrix._immutability, because a False value on a Mutability object already means mutable (horrible user interface for that routine! At least the internal attributes are at least named appropriately. Added benefit: The compiler immediately complains about unchanged locations (because the old attribute simply doesn't exist anymore). Possible better name: _is_immutable.
  • It almost seemed pickling would be a problem. However, in matrix0, it turns out that pickling isn't implemented anyway, so there are no old pickles to be concerned about.
  • note that Matrix instances also have a _cache attribute; a dictionary. This is also expensive to initialize. Would it be a good idea to also allow None as a sentinel value there and that any routine that needs _cache replaces None there by an empty dictionary? Or is that an unacceptable cost for cache use?

comment:2 in reply to: ↑ 1 Changed 9 years ago by nbruin

Replying to nbruin:

  • Would it be a good idea to also allow None as a sentinel value there and that any routine that needs _cache replaces None there by an empty dictionary? Or is that an unacceptable cost for cache use?

In fact, that's already in place in the cache access routines! It's just the init method that insists on setting self._cache = {}. It simply shouldn't do that! That will be much more efficient.

comment:3 Changed 9 years ago by nbruin

Unfortunately, following integer_dense.__cinit__ example to put a call to __init__ in the cinit method of 2x2 doubles the reported time taken by

from sage.matrix.matrix_integer_2x2 import Matrix_integer_2x2 as mi2x2
M2Z = MatrixSpace(ZZ,2)
null = mi2x2(M2Z,None,false,false)
timeit("null+null")

so that's not really reasonable. However, after reading cython's documentation, I don't think __cinit__ should ever call __init__. Those are separate initialization phases. So I think that sage/matrix/matrix_integer_dense.pyx:187:

    def __cinit__(self, parent, entries, coerce, copy):
...
        matrix_dense.Matrix_dense.__init__(self, parent)
...

is a bug, or at least a breach of protocol. Getting to a "cinited" state should note require __init__ on a previous one. The __init__ methods get called separately, after cinit is done.

(incidentally, Matrix_dense doesn't have an __init__, so this is just Matrix.__init__ being called)

I guess the trick here is that some code can get away with avoiding __init__. Then some code couldn't quite, so this line was added in as a hack. Changeset responsible:

changeset:   2250:797bd1fc80d9
user:        William Stein <wstein@gmail.com>
date:        Mon Dec 18 16:06:31 2006 -0800
summary:     Fast copy of matrices over ZZ.

so this is old. Cython has evolved since, so perhaps the organization here needs reconsidering. If it's absolutely necessary to create usable matrices via __new__, shouldn't we just put the required initializations in __cinit__? Those are guaranteed to be called, but it's generally recommended to put off as much as possible to __init__.

It seems to me that 2x2 is really just following in the footsteps of the rest of the matrix classes in only loosely following protocol for initialization. It should just do whatever is fastest. Incidentally, making the change as proposed on this ticket solves the initialization problem of the mutability, since such attributes are set to 0 anyway.

comment:4 Changed 9 years ago by nbruin

  • Component changed from PLEASE CHANGE to linear algebra
  • Owner changed from tbd to jason, was

comment:5 Changed 9 years ago by tkluck

  • Cc tkluck added
  • Type changed from PLEASE CHANGE to enhancement

comment:6 Changed 9 years ago by nbruin

Just some notes here. In order to make usable matrices from just Matrix.__new__(), i.e., without running __init__ we'd need to move some things into Matrix.__cinit__. The main things there are:

        self._immutability = False
        self._cache = None
        self._parent = parent
        self._base_ring = parent.base_ring()
        self._nrows = parent.nrows()
        self._ncols = parent.ncols()

The first 3 instructions are fast and could be moved into matrix.__cinit__ (which doesn't exist at the moment), except that some matrix routines call __new__ with parent=NULL. They set the parent themselves manually afterwards. We could fix that. However, if they have to muck about with _base_ring and _nrows,_ncols anyway, there's not much to win.

The last 3 instructions are slow, of course, because they require full-blown method resolutions. Many matrix subclasses can be more efficient about those, so it's probably good to leave those in the avoidable __init__ rather than the unavoidable __cinit__.

Note that the first two instructions are not necessary: Those are the values to which those attributes get initialized by cython already.

The following might be reasonable:

  • Change mutability to a bint flag, as proposed to this ticket. It means that a mutable matrix doesn't need to touch that flag at all upon initialization!
  • matrix classes can avoid the base class matrix.__init__ as long as they set _parent, _base_ring, _nrows, _ncols themselves.

This is largely how currently things work, except for Matrix_integer_dense, where the __cinit__ calls Matrix_dense.__init__ already. Hence, if you inherit from Matrix_integer_dense, you cannot get super efficient __new__ anymore.

This is of course silly, because already setting self._base_ring is something this class could do very efficiently. So, probably this call to Matrix_dense should be removed, setting self._base_ring can be done in Matrix_integer_dense.__cinit__ directly (because it's just ZZ), and setting nrows and ncols should probably be done explicitly (in most cases you KNOW how big the matrix is)

comment:7 Changed 9 years ago by nbruin

Patch attached to avoid calling __init__ in Matrix_integer_dense.__cinit__. This routine chooses to already set _parent (that's easy because that should be a parameter anyway! note that other classes sometimes get called with __new__ and parent=NULL), setting base ring is easy. This class also needs nrows and ncols set in __cinit__ already, but unfortunately the only way to get that information is via an expensive method call on the parent. This is no worse than happened before, though, because previously this happened in __init__. The present patch should give a very modest speedup (it doesn't have to look up the base ring and it doesn't set _nrows and _ncols twice anymore) but mostly it means the code is a little cleaner

Last edited 9 years ago by nbruin (previous) (diff)

comment:8 Changed 9 years ago by nbruin

  • Authors set to Nils Bruin
  • Description modified (diff)
  • Status changed from new to needs_review

comment:9 Changed 9 years ago by nbruin

OK, I think the patches presently supplied are safe for merger. Main work:

  • mutability is stored on Matrix via a direct bint flag. This is much more robust, because by default it gets initialized to a valid (False) value. The attribute is _immutability, so matrices are by default mutable, as before.
  • matrix_integer_dense previously called Matrix.__init__. That call has been unpacked. Previously, this code set _nrows and _ncols twice!
  • added doc to Matrix.__init__ to make explicit the contract
  • the approach in matrix_integer_2x2 is now as documented (before it seemed dodgy)

comment:10 follow-up: Changed 9 years ago by davidloeffler

Line 447 of matrix0.pyx looks fishy:

if self._is_immutable:

I'm not sure where the attribute self._is_immutable comes from -- how does it relate to self._immutability?

comment:11 in reply to: ↑ 10 Changed 9 years ago by nbruin

Replying to davidloeffler:

Line 447 of matrix0.pyx looks fishy:

if self._is_immutable:

Thanks! That's indeed a typo. In fact, it convinced me that we really SHOULD name this attribute _is_immutable, so I changed all the other ones. This actually reads as correct english!

Patchbot apply trac_13949-change_mutability.patch, trac_13949-fix_integer_dense_cinit.patch

comment:12 follow-up: Changed 9 years ago by kcrisman

Really tiny nitpick

[mq]: trac_13949-change_mutability.patch

just needs a quick hg qrefresh -e or something.

Last edited 9 years ago by kcrisman (previous) (diff)

Changed 9 years ago by nbruin

change to a simple flag _is_immutable om Matrix

Changed 9 years ago by nbruin

improve efficiency of integer_dense initialization

comment:13 in reply to: ↑ 12 Changed 9 years ago by nbruin

Replying to kcrisman:

Really tiny nitpick

[mq]: trac_13949-change_mutability.patch

just needs a quick hg qrefresh -e or something.

thanks! (sigh ... so painful to make such changes)

comment:14 Changed 9 years ago by nbruin

Patchbot apply trac_13949-change_mutability.patch, trac_13949-fix_integer_dense_cinit.patch

Changed 9 years ago by davidloeffler

Add doctest

comment:15 Changed 9 years ago by davidloeffler

  • Cc roed added
  • Description modified (diff)
  • Reviewers set to David Loeffler

I'm happy with this, but I thought it was best to add the original failing example from the sage-devel thread as a doctest, to make double-sure it doesn't get broken again. Can someone else OK my very tiny patch?

comment:16 Changed 9 years ago by davidloeffler

Patchbot apply trac_13949-change_mutability.patch, trac_13949-fix_integer_dense_cinit.patch, trac_13949-doctest.patch

comment:17 Changed 9 years ago by roed

  • Status changed from needs_review to positive_review

Looks good to me.

comment:18 Changed 9 years ago by jdemeyer

  • Merged in set to sage-5.7.beta3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.