Re: Multiplication optimization
Atanas Banov wrote: Paul McGuire wrote: Does Python's run-time do any optimization of multiplication operations, like it does for boolean short-cutting? That is, for a product a*b, is there any shortcutting of (potentially expensive) multiplication operations no. and the reason is very simple: to the extent such optimization makes sense, it has been done on assembler/CPU level already. i.e. when the multiplication is mapped to the machine code IMUL op the Pentium processor would be smart enough not to do the work if AX or the op are 0 or 1. Python has no job trying to outsmart Intel (and the other chipmakers). Boolean shortcuts are useful for entirely different reason, not speed. e.g. if lastDigit == 0 or i % lastDigit != 0: break if both operands of OR were to be evaluated, that would end up with division-by-zero exception for lastDigit=0. The point is not to avoid the multiplication on the CPU level but the object creation overhead: a = 1234 1 * a is a False # could be True $ python -m timeit -s'a=1;b=1234567' 'if a is 1: x = b' 'else: x = a * b' 1000 loops, best of 3: 0.171 usec per loop $ python -m timeit -s'a=1;b=1234567' 'x = a * b' 100 loops, best of 3: 0.211 usec per loop $ python -m timeit -s'a=2;b=1234567' 'if a is 1: x = b' 'else: x = a * b' 100 loops, best of 3: 0.329 usec per loop If 'a is 1' is sufficiently likely, that test speeds up the code even in pure Python. Of course a generalized implementation would also have to check b's type: $ python -m timeit -s'a=1;b=1234567' 'if a is 1 and b.__class__ is int: x = b' 'else: x = a * b' 100 loops, best of 3: 0.484 usec per loop So that is not a good idea, at least in pure Python. Peter -- http://mail.python.org/mailman/listinfo/python-list
Re: Multiplication optimization
Paul McGuire [EMAIL PROTECTED] wrote: Does Python's run-time do any optimization of multiplication operations, like it does for boolean short-cutting? That is, for a product a*b, is there any shortcutting of (potentially expensive) multiplication operations as in: Integer multiplication is a 1-cycle operation in Intel processors. Even multiple-precision multiplication is very efficient -- probably more so than multiple comparisons and jumps. -- - Tim Roberts, [EMAIL PROTECTED] Providenza Boekelheide, Inc. -- http://mail.python.org/mailman/listinfo/python-list
Re: Multiplication optimization
Paul McGuire wrote: Does Python's run-time do any optimization of multiplication operations, like it does for boolean short-cutting? That is, for a product a*b, is there any shortcutting of (potentially expensive) multiplication operations no. and the reason is very simple: to the extent such optimization makes sense, it has been done on assembler/CPU level already. i.e. when the multiplication is mapped to the machine code IMUL op the Pentium processor would be smart enough not to do the work if AX or the op are 0 or 1. Python has no job trying to outsmart Intel (and the other chipmakers). Boolean shortcuts are useful for entirely different reason, not speed. e.g. if lastDigit == 0 or i % lastDigit != 0: break if both operands of OR were to be evaluated, that would end up with division-by-zero exception for lastDigit=0. -- http://mail.python.org/mailman/listinfo/python-list
Multiplication optimization
Does Python's run-time do any optimization of multiplication operations, like it does for boolean short-cutting? That is, for a product a*b, is there any shortcutting of (potentially expensive) multiplication operations as in: if a == 0 return 0 if a == 1 return b return a*b Of course, for the cases where a is not 0 or 1 we are adding two comparisons to each multiply operation. But in some applications (sparse matrices? binary conversion?), the multiplication step could be avoided in many cases, if the user was aware that left-to-right short-cutting were implemented. Or by adding two *more* comparisons, then all multiplications would be optimized: if a == 0 or b == 0 return 0 if a == 1 return b if b == 1 return a return a*b But this seems overkill, especially since boolean short-cutting only works left-to-right. Just curious... -- Paul -- http://mail.python.org/mailman/listinfo/python-list
Re: Multiplication optimization
On Sat, 18 Feb 2006 16:48:38 -0800, Paul McGuire wrote: Does Python's run-time do any optimization of multiplication operations, like it does for boolean short-cutting? Do you know that these shortcuts are optimizations, or are you just assuming it takes less time to do the comparison than it would for the CPU to blast bits around? I have no idea whether your shortcuts are optimizations or pessimizations. I'm just asking whether you know, or if you are making assumptions. -- Steven. -- http://mail.python.org/mailman/listinfo/python-list
Re: Multiplication optimization
[Paul McGuire]
Does Python's run-time do any optimization of multiplication
operations, like it does for boolean short-cutting?
Usually, it is safest (and typically true) to assume that Python
performs no optimizations. To go beyond making assumptions, it is easy
to run a few timings:
from timeit import Timer
min(Timer('0*1234567').repeat(5))
0.11315376674968469
min(Timer('1*1234567').repeat(5))
0.11920453577200618
min(Timer('113*1234567').repeat(5))
0.11881482143680699
In your specific case, I can answer than the source shows no special
optimization for multiplications by specific values. There is a
short-path for integer multiplications but it is not value specific.
In Py2.5, the compiler will do a limited amount of constant folding;
however, its scope is somewhat limited because expressions like a*3
vary depending on the a's type which is often not knowable by the
compiler without some form of global analysis.
One other thought: Python is not assembly. Run time is unlikely to be
dominated by the time to execute a multiplication. With Python, it is
best to focus optimization efforts on making choosing the best data
structures and hoisting constants out of loops.
Raymond
--
http://mail.python.org/mailman/listinfo/python-list
Re: Multiplication optimization
On 18 Feb 2006 16:48:38 -0800, Paul McGuire [EMAIL PROTECTED] wrote:
Does Python's run-time do any optimization of multiplication
operations, like it does for boolean short-cutting?
Here's the beginning of int_mul from Objects/intobject.c:
static PyObject *
int_mul(PyObject *v, PyObject *w)
{
long a, b;
long longprod; /* a*b in native long arithmetic */
double doubled_longprod;/* (double)longprod */
double doubleprod; /* (double)a * (double)b */
CONVERT_TO_LONG(v, a);
CONVERT_TO_LONG(w, b);
longprod = a * b;
doubleprod = (double)a * (double)b;
doubled_longprod = (double)longprod;
I think the rest of the function is probably irrelevant, as far as your
question goes.
Jean-Paul
--
http://mail.python.org/mailman/listinfo/python-list
