Bitshifts and "And" vs Floor-division and Modular
Steven D'Aprano
steve+comp.lang.python at pearwood.info
Thu Sep 6 22:00:54 EDT 2012
On Thu, 06 Sep 2012 17:01:12 -0700, jimbo1qaz wrote:
> Is it faster to use bitshifts or floor division?
Does it matter?
If you ever find yourself writing an application where the difference
between 0.0476 microseconds and 0.0473 microseconds matters to you,
Python is probably the wrong language.
py> from timeit import Timer
py> min(Timer('456789 // 8').repeat(repeat=35))
0.04760909080505371
py> min(Timer('456789 >> 3').repeat(repeat=35))
0.047319889068603516
> And which is better, & or %?
Depends what you want to do. If you want to perform bitwise-and, then I
strongly recommend you use &, the bitwise-and operator. If you want to
perform modulus, then the modulus operator % is usually better.
> All divisors and mods are power of 2, so are binary operations
> faster?
As the MiddleMan says, "specificity is the soul of all good
communication". Python has many binary operations, e.g.:
+ - * / // % == is < <= > >= ** & ^ |
Some of them are faster than some other things, so would you like to be
more specific?
My *guess* is that you mean *bitwise* operators, compared to numeric
operators like * and // (integer division). The runtime cost is mostly
dominated by the object-oriented overhead -- Python is not C or assembly,
and the integers are rich objects, not low-level bitfields, so the
difference between division and bitshifting is much less than you might
expect from assembly language.
But, in principle at least, there *may* be some tiny advantage to the
bitwise operators. I say "may" because the difference is so small that it
is likely to be lost in the noise. I do not believe that there will be
any real world applications where the difference between the two is
significant enough to care about. But if you think different, feel free
to use the profile module to profile your code and demonstrate that
divisions are a significant bottleneck in your application.
> And are they considered bad style?
Absolutely. Using & when you mean to take the remainder is a dirty
optimization hack only justified if you really, really, really need it.
I'm pretty confident that you will never notice a speed-up of the order
of 0.1 nanoseconds.
"More computing sins are committed in the name of efficiency (without
necessarily achieving it) than for any other single reason — including
blind stupidity." — W.A. Wulf
"We should forget about small efficiencies, say about 97% of the time:
premature optimization is the root of all evil. Yet we should not pass up
our opportunities in that critical 3%. A good programmer will not be
lulled into complacency by such reasoning, he will be wise to look
carefully at the critical code; but only after that code has been
identified" — Donald Knuth
"Bottlenecks occur in surprising places, so don't try to second guess and
put in a speed hack until you have proven that's where the bottleneck
is." — Rob Pike
"The First Rule of Program Optimization: Don't do it. The Second Rule of
Program Optimization (for experts only!): Don't do it yet." — Michael A.
Jackson
--
Steven
More information about the Python-list
mailing list