Design discussion / request for comment
Florent Hivert
I'd like to discuss a design question. Some time ago Adrien Boussicault and
myself started to write some experimental code for copy-on-write in
Sage/Python. The idea is now more or less dropped because performance gain was
not so good and the syntax was not very usable. It still remain that along the
way we had a design idea that I would like to submit here for comment:
The idea is inspired from the "prototype" design pattern (see [Pro], [GOF]).
I want to define subclasses of Element with the following behavior: Those
classes are intended to be used to model *mathematical* objects, which are by
essence immutable. However, in many occasions, one wants to construct the
data-structure encoding of a new mathematical object by small modifications of
the data structure encoding some already built object. This is a very common
stuff for example in matrices: For example: given a matrix M we want to
replace every non_zero position by 1
res = copy(M)
for pos in res._nonzero_positions_by_row():
res[pos] = 1
res.set_immutable()
However in many cases, for the resulting data-structure to correctly encode
the mathematical object, some structural invariants must hold (say for example
we want that the matrix is symmetric). One problem is that, in many cases,
during the modification process, there is no possibility but to break the
invariants. Here there is no way to keep the matrix symmetric during the
replacement by 1...
A typical example in combinatorics, in a list modeling a permutation of
\{1,\dots,n\}, the integers must be distinct. A very common operation is to
take a permutation to make a copy with some small modifications, like
exchanging two consecutive values in the list or cycling some values. Though
the result is clearly a permutations there's no way to avoid breaking the
permutations invariants at some point during the modifications.
So the idea is the following: to allows local breaking of invariant on a
locally mutable copy and to check that things are restored in a proper state
at the end. So I wrote a small class called ClonableElement and several
derived subclasses (clone is the standard name for the copy method in the
"prototype" design pattern):
A class C inheriting from ClonableElement must implement the following
two methods
- obj.__copy__() -- returns a fresh copy of obj
- obj.check() -- returns nothing, raise an exception if obj
doesn't satisfies the data structure invariants
Then, given an instance obj of C, the following sequences of
instructions ensures that the invariants of new_obj are properly
restored at the end
with obj.clone() as new_obj:
...
# lot of invariant breaking modifications on new_obj
...
# invariants are ensured to be fulfilled
The following equivalent sequence of instructions can be used if speed is
needed, in particular in Cython code (unfortunately, the handling of the with
instruction make some overhead)...
new_obj = obj.__copy__()
...
# lot of invariant breaking modifications on new_obj
...
new_obj.set_immutable()
new_obj.check()
# invariants are ensured to be fulfilled
I also took to chance to handle hashing... All the code is on #8702, together
with some performance tests... Also this is my first real life Cython code so
any help is welcome.
Thanks for any comment or suggestion.
Cheers,
Florent
[Pro] Prototype pattern http://en.wikipedia.org/wiki/Prototype_pattern
[GOF] Design Patterns: Elements of Reusable Object-Oriented
Software. E. Gamma; R. Helm; R. Johnson; J. Vlissides (1994).
Addison-Wesley. ISBN 0-201-63361-2.
Jason Grout
> Hi There,
>
> I'd like to discuss a design question. Some time ago Adrien Boussicault and
> myself started to write some experimental code for copy-on-write in
> Sage/Python. The idea is now more or less dropped because performance gain was
> not so good and the syntax was not very usable.
Rob and I were just talking yesterday how it's so inconvenient that
identity_matrix() now returns an immutable matrix, so constructing
something from it involves making a copy, which is not the most obvious
thing to a new person, or the most elegant thing to someone that has
been using matrices for a while now. It would be fantastic if immutable
matrices had copy-on-write semantics, not necessarily for performance,
but just for usability after some of the recent design decisions (which
I guess were made for performance reasons).
I like the ideas you've described in the rest of the message, so +1 on
the prototype ideas too!
Thanks,
Jason
Robert Bradshaw
On Jun 10, 2010, at 8:17 PM, Jason Grout wrote:
> On 6/10/10 12:25 PM, Florent Hivert wrote:
>> Hi There,
>>
>> I'd like to discuss a design question. Some time ago Adrien
>> Boussicault and
>> myself started to write some experimental code for copy-on-write in
>> Sage/Python. The idea is now more or less dropped because
>> performance gain was
>> not so good and the syntax was not very usable.
>
> Rob and I were just talking yesterday how it's so inconvenient that
> identity_matrix() now returns an immutable matrix, so constructing
> something from it involves making a copy, which is not the most
> obvious thing to a new person, or the most elegant thing to someone
> that has been using matrices for a while now. It would be fantastic
> if immutable matrices had copy-on-write semantics, not necessarily
> for performance, but just for usability after some of the recent
> design decisions (which I guess were made for performance reasons).
Copy on write *should* be rather easy to implement for matrices at
least.
- Robert
William Stein
Just out of curiosity, is this what would happen below with what you
guys are envisioning
for immutable copy on write matrices?
sage: a = matrix(ZZ, 3)
sage: a[1,2] = 5
sage: a.set_immutable()
sage: a[1,2] = 7
sage: print a
7
If so, what about:
sage: A = M.hecke_matrix(2)
sage: A[1,2]
20
sage: A[1,2] = 5; A
5
sage: M.hecke_matrix(2)[1,2]
20
I think the above would be very, very confusing to me. If immutable
matrices *act* as if they are fully mutable, but basically silently
have completely different semantics, this will be confusing.
-- William
--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org
Jason Grout
>> Copy on write *should* be rather easy to implement for matrices at least.
William indicates otherwise in [1]. I can't think of an easy way to do
it either, so I'm really curious what how you think it would be easy.
>
> Just out of curiosity, is this what would happen below with what you
> guys are envisioning
> for immutable copy on write matrices?
>
[snip]
> I think the above would be very, very confusing to me. If immutable
> matrices *act* as if they are fully mutable, but basically silently
> have completely different semantics, this will be confusing.
I agree. I think my concerns would be taken care of if we just made the
top-level identity_matrix (and zero_matrix) function return a mutable
matrix (i.e., MM(1) or MM(0), rather than MM.one() or MM.zero())
I've posted a patch for doing this at
http://trac.sagemath.org/sage_trac/ticket/9212. It's ready for review.
Thanks,
Jason
[1]
http://groups.google.com/group/sage-devel/browse_frm/thread/1042edd11b3854b2
William Stein
Wait. Wasn't there a big discussion on sage-devel only maybe 3 months
ago which was
all about changing identity_matrix() to be *immutable*???
http://trac.sagemath.org/sage_trac/ticket/8276
>
> Thanks,
>
> Jason
>
> [1]
> http://groups.google.com/group/sage-devel/browse_frm/thread/1042edd11b3854b2
>
> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to
> sage-devel+...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
Jason Grout
> On Fri, Jun 11, 2010 at 12:19 AM, Jason Grout
> <jason...@creativetrax.com> wrote:
>> On 6/11/10 1:50 AM, William Stein wrote:
>>
>>>> Copy on write *should* be rather easy to implement for matrices at least.
>>
>> William indicates otherwise in [1]. I can't think of an easy way to do it
>> either, so I'm really curious what how you think it would be easy.
>>
>>>
>>> Just out of curiosity, is this what would happen below with what you
>>> guys are envisioning
>>> for immutable copy on write matrices?
>>>
>>
>> [snip]
>>
>>> I think the above would be very, very confusing to me. If immutable
>>> matrices *act* as if they are fully mutable, but basically silently
>>> have completely different semantics, this will be confusing.
>>
>> I agree. I think my concerns would be taken care of if we just made the
>> top-level identity_matrix (and zero_matrix) function return a mutable matrix
>> (i.e., MM(1) or MM(0), rather than MM.one() or MM.zero())
>>
>> I've posted a patch for doing this at
>> http://trac.sagemath.org/sage_trac/ticket/9212. It's ready for review.
>
> Wait. Wasn't there a big discussion on sage-devel only maybe 3 months
> ago which was
> all about changing identity_matrix() to be *immutable*???
>
> http://trac.sagemath.org/sage_trac/ticket/8276
Yes and no. That's the discussion I pulled your comment from (linked in
[1] below).
The discussion before was dealing with (if MM is a matrix space)
MM.one() and MM.zero() (and MM.identity_matrix()). It was decided that
MM(1) and MM(0) would stay mutable.
For someone that doesn't want to deal with creating a matrix space, but
just wants to create a matrix (think: student), having the *top-level*
identity_matrix function return MM(1) instead of MM.one() (i.e., mutable
matrix instead of immutable matrix) is very convenient. That is the
change that is in #9212. The same comment applies to the *top-level*
zero_matrix function.
Thanks,
Jason
Florent Hivert
>> Rob and I were just talking yesterday how it's so inconvenient that
>> identity_matrix() now returns an immutable matrix, so constructing
>> something from it involves making a copy, which is not the most obvious
>> thing to a new person, or the most elegant thing to someone that has been
>> using matrices for a while now. It would be fantastic if immutable
>> matrices had copy-on-write semantics, not necessarily for performance, but
>> just for usability after some of the recent design decisions (which I
>> guess were made for performance reasons).
>
> Copy on write *should* be rather easy to implement for matrices at least.
This is both true and false:
Making the data-structure for having copy-on-write object is fairly easy. This
is just aving an extra level of indirection and we have something good for
that in sage-combinat queue (see [1]). Note that if this patch were be really
used, it certainly should be Cythonized.
The main problem for COW is a problem of syntax. If obj is a python object
then
obj1 = obj
makes only a new reference on the *same* object. Unfortunately in Python, there
is now way to change that like overloading operator::= in C++. if you want to
make a new *semantic copy* you have to use a different syntax. The way we
tried that in our experiment is
with obj.mutable(): # obj is now a new semantic copy of itself
# copy is done here if needed.
obj[1] = 1 # in place modifications
The result of the experiment is that, given you have to use this new syntax,
most of the time if you use it, you really need a *new* copy. The overhead of
COW is simply not worth it. Therefore we decided that the prototype design
pattern was better suitable to our need than COW. Of course, if there was a
was to overload "=" things were completely different.
Cheers,
Florent
[1] http://combinat.sagemath.org/hgwebdir.cgi/patches/file/2521d1fbfebb/copy_on_write-ab.patch#l1
Robert Bradshaw
No, I was thinking that one would still have to do m.copy(), but the
actual copying would only occur the first time the matrix entries were
mutated. Thus methods like one() and zero() would return mutable
copies without the overhead of actually copying.
> If so, what about:
>
> sage: A = M.hecke_matrix(2)
> sage: A[1,2]
> 20
> sage: A[1,2] = 5; A
> 5
> sage: M.hecke_matrix(2)[1,2]
> 20
>
> I think the above would be very, very confusing to me.
But A is no longer the Hecke matrix--so I wouldn't expect it to be
equal to the Hecke matrix as recomputed on the last line.
> If immutable
> matrices *act* as if they are fully mutable, but basically silently
> have completely different semantics, this will be confusing.
The above makes perfect sense to me--whenever I do
sage: X = foo()
sage: # mutate X
I *don't* expect future calls to foo() to be mangled, rather I expect
it to be recomputed (or, if cached, acting as it if were recomputed).
In fact, most of the time this happens I'd call it a bug, which is why
we try so hard to return copies of lists, or tuples, and one of the
primary motivations for immutable matrices in the first place.
- Robert
Robert Bradshaw
Personally, I think not being able to execute arbitrary code on
assignment is a feature not a bug :)
> if you want to
> make a new *semantic copy* you have to use a different syntax. The
> way we
> tried that in our experiment is
>
> with obj.mutable(): # obj is now a new semantic copy of itself
> # copy is done here if needed.
> obj[1] = 1 # in place modifications
>
> The result of the experiment is that, given you have to use this new
> syntax,
> most of the time if you use it, you really need a *new* copy. The
> overhead of
> COW is simply not worth it. Therefore we decided that the prototype
> design
> pattern was better suitable to our need than COW. Of course, if
> there was a
> was to overload "=" things were completely different.
My proposal is not to make everything copy on write by default, but
rather to make the copy() method lazy. This would be a smaller step,
but still useful. In particular, this wouldn't change any current Sage
semantics, but would only be an optimization feature. The prototypical
use case is when something returns a matrix that's worth caching, but
doesn't know if the user just wants to read it, or might want to
modify it. As for the overhead, one could put the copying code in
clear_cache(), and there would be no need for an extra layer of
indirection.
- Robert
Florent Hivert
>>> Copy on write *should* be rather easy to implement for matrices at least.
>>
>> This is both true and false:
>>
>> Making the data-structure for having copy-on-write object is fairly easy.
>> This
>> is just aving an extra level of indirection and we have something good for
>> that in sage-combinat queue (see [1]). Note that if this patch were be
>> really
>> used, it certainly should be Cythonized.
>>
>> The main problem for COW is a problem of syntax. If obj is a python object
>> then
>>
>> obj1 = obj
>>
>> makes only a new reference on the *same* object. Unfortunately in Python,
>> there
>> is now way to change that like overloading operator::= in C++.
>
> Personally, I think not being able to execute arbitrary code on assignment
> is a feature not a bug :)
I more or less agrees with that...
>> if you want to
>> make a new *semantic copy* you have to use a different syntax. The way we
>> tried that in our experiment is
>>
>> with obj.mutable(): # obj is now a new semantic copy of itself
>> # copy is done here if needed.
>> obj[1] = 1 # in place modifications
>>
>> The result of the experiment is that, given you have to use this new
>> syntax,
>> most of the time if you use it, you really need a *new* copy. The overhead
>> of
>> COW is simply not worth it. Therefore we decided that the prototype design
>> pattern was better suitable to our need than COW. Of course, if there was
>> a
>> was to overload "=" things were completely different.
>
> My proposal is not to make everything copy on write by default, but rather
> to make the copy() method lazy. This would be a smaller step, but still
> useful. In particular, this wouldn't change any current Sage semantics, but
> would only be an optimization feature. The prototypical use case is when
> something returns a matrix that's worth caching, but doesn't know if the
> user just wants to read it, or might want to modify it.
Well ! I not sure to understand exactly... So you want to return a (semantic)
copy of what is cached, right ? So any function returning a matrix (say
inverse) will have to explicitely call "return copy(result)". So inverse is
only computed once. But still, do you return a mutable or immutable matrix ?
Or maybe with this COW you don't want to distinguish anymore ?
> As for the overhead, one could put the copying code in clear_cache(), and
> there would be no need for an extra layer of indirection.
So basically you still want to write
A = copy(B) # create a semantic copy but no actual copy is done
A[1,2] = 4 # the copy is triggered...
An since the actual entries of the matrix are stored in an attributes called
_entries, two different matrix objects can have share the same entries so that
the matrix object is doing the indirection for you. So this sound good and not
very hard to do...
Cheers,
Florent
Jason Grout
> So basically you still want to write
>
> A = copy(B) # create a semantic copy but no actual copy is done
> A[1,2] = 4 # the copy is triggered...
>
> An since the actual entries of the matrix are stored in an attributes called
> _entries, two different matrix objects can have share the same entries so that
> the matrix object is doing the indirection for you. So this sound good and not
> very hard to do...
>
Hmm. It would be interesting to see if you could have sparse matrices
where it was COW per-entry, rather than per-matrix (i.e., A[1,2]=3 would
just add an entry, an overlay, sort of, on the original data. I can see
some performance issues, but maybe the space savings would be worth it.
Anyways, these are interesting ideas.
Jason
Robert Bradshaw
Yes.
> But still, do you return a mutable or immutable matrix ?
If you were returning an immutable one, there would be no need to
bother with the copy.
> Or maybe with this COW you don't want to distinguish anymore ?
I'm fine with still making this distinction. E.g. The original inverse
matrix could still be immutable (for safety, in case anyone gets their
hands on it).
>> As for the overhead, one could put the copying code in
>> clear_cache(), and
>> there would be no need for an extra layer of indirection.
>
> So basically you still want to write
>
> A = copy(B) # create a semantic copy but no actual copy is done
> A[1,2] = 4 # the copy is triggered...
>
> An since the actual entries of the matrix are stored in an
> attributes called
> _entries, two different matrix objects can have share the same
> entries so that
> the matrix object is doing the indirection for you. So this sound
> good and not
> very hard to do...
Yep. It's not as transparent as COW on assignment, and happens to be
specific to matrices (arguably the most common use) but "explicit is
better than implicit."
- Robert