Multiplication optimization

[Paul McGuire]

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

[Steven D'Aprano]

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.

[Raymond Hettinger]

[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

[Atanas Banov]

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.

[Peter Otten]

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'
10000000 loops, best of 3: 0.171 usec per loop
$ python -m timeit -s'a=1;b=1234567' 'x = a * b'
1000000 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'
1000000 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'
1000000 loops, best of 3: 0.484 usec per loop

So that is not a good idea, at least in pure Python.

Peter

[Tim Roberts]

"Paul McGuire" <pt***@austin.rr.com> 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, ti**@probo.com
Providenza & Boekelheide, Inc.