SAGE and inplace operators
Robert Bradshaw
can be considerable), SAGE has avoided almost all use of inplace
operators due to the fact that elements are supposed to be immutable,
despite the fact that one does not really need the "old" result
anymore. For example, if I type x^5 - 3*x + 1, the subexpressions
(x^5), (3*x), and (x^5-3*x) are all created and then discarded. This
also shows up in places like the operation sum() which doesn't return
any of its intermediate results, or loops that increment variables in
certain ways. The worry is that perhaps somewhere something else is
holding onto a given variable, and we don't want to mess it up.
Just the other day, I realized that Python provides the perfect
solution--by looking at the reference count of an object we can
detect whether or not its safe to mutate it (i.e. nothing else is
holding onto it but the current call). If it is safe to mutate, then
do so, otherwise create and return a new object. I propose adding
_iadd_c, _imul_c, etc. to the coercion hierarchy such that the
default __iadd__/__add__ detects whether or not inplace operations
are safe and calls the respective operation accordingly. One would
have bold comments on functions that are not safe to call directly.
The only caveat is that it might make it a tiny bit slower for types
that do not define inplace operations, and it would take a slight
(SAGE-specific and optional) tweak to Cython (specifically Cython
local function variables have a refcount one less than expected due
to their not being in any kind of a python "scope" container, so we
would need an extra incref/decref them when performing arithmetic on
them).
- Robert
boo...@u.washington.edu
Nick Alexander
On 5-Sep-07, at 3:27 PM, Robert Bradshaw wrote:
>
> Despite the potential speed increase (I've implemented some and it
> can be considerable), SAGE has avoided almost all use of inplace
> operators due to the fact that elements are supposed to be immutable,
> despite the fact that one does not really need the "old" result
> anymore. For example, if I type x^5 - 3*x + 1, the subexpressions
> (x^5), (3*x), and (x^5-3*x) are all created and then discarded. This
> also shows up in places like the operation sum() which doesn't return
> any of its intermediate results, or loops that increment variables in
> certain ways. The worry is that perhaps somewhere something else is
> holding onto a given variable, and we don't want to mess it up.
>
> Just the other day, I realized that Python provides the perfect
> solution--by looking at the reference count of an object we can
> detect whether or not its safe to mutate it (i.e. nothing else is
> holding onto it but the current call). If it is safe to mutate, then
> do so, otherwise create and return a new object. I propose adding
> _iadd_c, _imul_c, etc. to the coercion hierarchy such that the
> default __iadd__/__add__ detects whether or not inplace operations
> are safe and calls the respective operation accordingly. One would
> have bold comments on functions that are not safe to call directly.
+1, this is a very interesting idea.
Nick
David Harvey
If this works, I give it a +5.
But I'm a bit concerned.... why doesn't Python do this itself? I just
had a look at the implementations of some arithmetic operations on
e.g. floats and strings in the python source, and they never use this
trick.
I would feel much more comfortable if there was some "mainstream"
precedent for this.
Scary: when I googled "python inplace operators" to try to find a
precedent, the sixth link was a talk I gave at some SAGE event.
david
Robert Bradshaw
Thanks.
> But I'm a bit concerned.... why doesn't Python do this itself? I just
> had a look at the implementations of some arithmetic operations on
> e.g. floats and strings in the python source, and they never use this
> trick.
>
> I would feel much more comfortable if there was some "mainstream"
> precedent for this.
Good questions. I think there is a good reason why Python doesn't do
this. First, there is no requirement in Python that a.__add__(b) ==
a.__iadd__(b), I think it is safe to consider this a *bug* for sage
Elements. Secondly, it is possible to write a python extension
classes that will break this. Specifically, imagine this code:
PyObject* tmp = <PyObject *>x
x += y # now tmp has changed as well, because we think we own
the only reference to x
z = <object>tmp # which has been mutated
This is not typical SAGE Cython code, and would only apply in that
context (x and y would have to be elements). I can't even come up
with an example that breaks x+y (by mutating x) but one could perhaps
do pointer manipulation and call PyNumber_Add directly (after re-
declaring it to take PyObject*) or do something directly in C.
>
> Scary: when I googled "python inplace operators" to try to find a
> precedent, the sixth link was a talk I gave at some SAGE event.
So...that would make you one of the world experts, right :-).
>
> david
>
>
>
David Harvey
On Sep 5, 2007, at 7:37 PM, Robert Bradshaw wrote:
>> But I'm a bit concerned.... why doesn't Python do this itself? I just
>> had a look at the implementations of some arithmetic operations on
>> e.g. floats and strings in the python source, and they never use this
>> trick.
>>
>> I would feel much more comfortable if there was some "mainstream"
>> precedent for this.
>
> Good questions. I think there is a good reason why Python doesn't do
> this. First, there is no requirement in Python that a.__add__(b) ==
> a.__iadd__(b), I think it is safe to consider this a *bug* for sage
> Elements. Secondly, it is possible to write a python extension
> classes that will break this. Specifically, imagine this code:
>
> PyObject* tmp = <PyObject *>x
> x += y # now tmp has changed as well, because we think we own
> the only reference to x
> z = <object>tmp # which has been mutated
>
> This is not typical SAGE Cython code, and would only apply in that
> context (x and y would have to be elements). I can't even come up
> with an example that breaks x+y (by mutating x) but one could perhaps
> do pointer manipulation and call PyNumber_Add directly (after re-
> declaring it to take PyObject*) or do something directly in C.
Hmmmmm this has me a bit worried.
The corollary of what you just said is: if someone writes some code
that tries to optimise by avoiding a refcount that they think is safe
to avoid, then it can break your inplace operators.
Like for example, suppose you are writing a cython function that
operates on a python list containing Elements. You know that the
Elements are already refcounted (from the list), so when you do
arithmetic on them, you can avoid refcounting. For example maybe
you're doing a row operation in a generic matrix class, or something
like that.
david
Robert Bradshaw
Yes, but it's hard to optimize to that point. Definitely something to
think hard about though.
>
> Like for example, suppose you are writing a cython function that
> operates on a python list containing Elements. You know that the
> Elements are already refcounted (from the list), so when you do
> arithmetic on them, you can avoid refcounting. For example maybe
> you're doing a row operation in a generic matrix class, or something
> like that.
This was the extra incref that I mentioned needed to be (has been in
fact) added to Cython. It is very conservative, and I think the
overhead of forcing an increfs/decref is far smaller then the
potential savings, and will be overwhelmed by the overhead of calling
__add__.
- Robert
Robert Bradshaw
http://www.sagemath.org:9002/sage_trac/ticket/624
William Stein
>
> An implementation is up to test and play with at
>
> http://www.sagemath.org:9002/sage_trac/ticket/624
>
1. Could you post some (impressive) benchmarks?
2. Could you post a little example session that specifically
illustrates what's happening?
3. Do you believe this code is stable and ready to release in SAGE?
william
Robert Bradshaw
> On 9/13/07, Robert Bradshaw <robe...@math.washington.edu> wrote:
>>
>> An implementation is up to test and play with at
>>
>> http://www.sagemath.org:9002/sage_trac/ticket/624
>>
>
> 1. Could you post some (impressive) benchmarks?
I've put some up on trac.
> 2. Could you post a little example session that specifically
> illustrates what's happening?
Same.
> 3. Do you believe this code is stable and ready to release in SAGE?
I think so, but would like lots of other people to test it (sage -t
on other machines at the very least), and those who are so inclined
to try and break it.
- Robert