Binary arithmetic optimization (Was: Why not an __assign__ method?)
Robin Thomas
robin900 at yahoo.com
Fri Apr 6 11:14:10 EDT 2001
At 10:15 AM 4/6/01 +0200, Roeland Rengelink wrote:
>Carlos Alberto Reis Ribeiro wrote:
>
>[extensively about a proposal to add a new magic method __onassign__ to
>solve a problem in arithmetic expressions]
>
>Hi,
>
>I've looked at another approach to solve the problem under
>consideration. This approach seems to work and does not require a magic
>__onassign__ method. It does require some refcount magic, which makes
>this procedure somewhat unobvious.
Yes, I agree with you that __onassign__ is not necessary. I also agree that
an object's reference count is the key to the solution. I do not agree that
any "magic" needs to be done to any object, either by copying it or setting
some flag.
I sent a possible solution to Carlos, but did not post it to the list. I
thought that the list's interest in our topic had waned, and that the
discussion should be taken offline. The ensuing responses from you and
others convince me that, hey, maybe it does belong on this list.
Here's the message in question (appended, not quoted or attached)...
---------
I've been thinking about your in-place operator optimizations. Two main
approaches I have considered:
1) Doing it at the bytecode level. Bytecodes that would produce "new"
objects mark that position on the stack (not the object on the stack
itself) as a candidate for in-place operator optimization. If, later in the
bytecode, a BINARY_* would execute with the marked position being second
from the top (the left operand of the binary op), the BINARY_* opcode is
replaced with the corresponding INPLACE_* opcode.
2) Exploiting the fact that, in the CPython virtual machine, the stack must
own its own reference to each object on the stack, one reference for each
stack position. When the VM executes an opcode, it pops the objects off the
stack, them does some stuff, and only as the final act decrements the
reference counts of the objects it popped.
Thus, when the VM POP()s an object from the stack, it still owns a
reference to it. And if the object's reference count is 1, then only the
stack can reach the object. This is tantamount to having the object marked
'temp'. No stacks in other frames refer to the object, nor does any other
Python object, if ob_refcnt == 1.
Then, we can have the code for BINARY_OP check the left operand object. If
ob_refcnt == 1, it's a "temp" object, and we can do the inplace operation
instead. No change to the compilation phase is needed.
Here's a test implementation, a patch against 2.1b1 Python/ceval.c. Looks
like it works.
*** Python/ceval.old Thu Apr 5 19:59:56 2001
--- Python/ceval.c Thu Apr 5 20:05:05 2001
***************
*** 410,415 ****
--- 410,418 ----
#define SETLOCAL(i, value) do { Py_XDECREF(GETLOCAL(i)); \
GETLOCAL(i) = value; } while (0)
+ /* Inplace operator optimization macro */
+ #define CAN_IOP(x) (x->ob_refcnt == 1)
+
/* Start of code */
#ifdef USE_STACKCHECK
***************
*** 883,889 ****
case BINARY_POWER:
w = POP();
v = POP();
! x = PyNumber_Power(v, w, Py_None);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
--- 886,895 ----
case BINARY_POWER:
w = POP();
v = POP();
! if (CAN_IOP(v))
! x = PyNumber_InPlacePower(v, w, Py_None);
! else
! x = PyNumber_Power(v, w, Py_None);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
***************
*** 893,899 ****
case BINARY_MULTIPLY:
w = POP();
v = POP();
! x = PyNumber_Multiply(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
--- 899,908 ----
case BINARY_MULTIPLY:
w = POP();
v = POP();
! if (CAN_IOP(v))
! x = PyNumber_InPlaceMultiply(v, w);
! else
! x = PyNumber_Multiply(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
***************
*** 903,909 ****
case BINARY_DIVIDE:
w = POP();
v = POP();
! x = PyNumber_Divide(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
--- 912,921 ----
case BINARY_DIVIDE:
w = POP();
v = POP();
! if (CAN_IOP(v))
! x = PyNumber_InPlaceDivide(v, w);
! else
! x = PyNumber_Divide(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
***************
*** 913,919 ****
case BINARY_MODULO:
w = POP();
v = POP();
! x = PyNumber_Remainder(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
--- 925,934 ----
case BINARY_MODULO:
w = POP();
v = POP();
! if (CAN_IOP(v))
! x = PyNumber_InPlaceRemainder(v, w);
! else
! x = PyNumber_Remainder(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
***************
*** 937,944 ****
else
x = PyInt_FromLong(i);
}
else
! x = PyNumber_Add(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
--- 952,961 ----
else
x = PyInt_FromLong(i);
}
+ else if (CAN_IOP(v))
+ x = PyNumber_InPlaceAdd(v, w);
else
! x = PyNumber_Add(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
***************
*** 962,969 ****
else
x = PyInt_FromLong(i);
}
else
! x = PyNumber_Subtract(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
--- 979,988 ----
else
x = PyInt_FromLong(i);
}
+ else if (CAN_IOP(v))
+ x = PyNumber_InPlaceSubtract(v, w);
else
! x = PyNumber_Subtract(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
***************
*** 1000,1006 ****
case BINARY_LSHIFT:
w = POP();
v = POP();
! x = PyNumber_Lshift(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
--- 1019,1028 ----
case BINARY_LSHIFT:
w = POP();
v = POP();
! if (CAN_IOP(v))
! x = PyNumber_InPlaceLshift(v, w);
! else
! x = PyNumber_Lshift(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
***************
*** 1010,1016 ****
case BINARY_RSHIFT:
w = POP();
v = POP();
! x = PyNumber_Rshift(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
--- 1032,1041 ----
case BINARY_RSHIFT:
w = POP();
v = POP();
! if (CAN_IOP(v))
! x = PyNumber_InPlaceRshift(v, w);
! else
! x = PyNumber_Rshift(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
***************
*** 1020,1026 ****
case BINARY_AND:
w = POP();
v = POP();
! x = PyNumber_And(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
--- 1045,1054 ----
case BINARY_AND:
w = POP();
v = POP();
! if (CAN_IOP(v))
! x = PyNumber_InPlaceAnd(v, w);
! else
! x = PyNumber_And(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
***************
*** 1030,1036 ****
case BINARY_XOR:
w = POP();
v = POP();
! x = PyNumber_Xor(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
--- 1058,1067 ----
case BINARY_XOR:
w = POP();
v = POP();
! if (CAN_IOP(v))
! x = PyNumber_InPlaceXor(v, w);
! else
! x = PyNumber_Xor(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
***************
*** 1040,1046 ****
case BINARY_OR:
w = POP();
v = POP();
! x = PyNumber_Or(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
--- 1071,1080 ----
case BINARY_OR:
w = POP();
v = POP();
! if (CAN_IOP(v))
! x = PyNumber_InPlaceOr(v, w);
! else
! x = PyNumber_Or(v, w);
Py_DECREF(v);
Py_DECREF(w);
PUSH(x);
--
robin900 at yahoo.com
_________________________________________________________
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com
More information about the Python-list
mailing list