Bitshifts and "And" vs Floor-division and Modular

[Steven D'Aprano]

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