Profiling bit-twiddling in Python
After my previous post regarding the the is_power_of_2 and next_power_of_2 functions, Richard Jones pointed out that Pyglet has an implementation that used the bit-twiddling method. Since I had something to do a direct comparison with, I wrote a script to test the run time of the two methods.
#!/usr/bin/env python setup_1 = """ from math import log, ceil def is_power_of_2(n): return log(n, 2) % 1.0 == 0.0 def next_power_of_2(n): return (2 ** ceil(log(n, 2))) """ setup_2 = """ def next_power_of_2(v): v -= 1 v |= v >> 1 v |= v >> 2 v |= v >> 4 v |= v >> 8 v |= v >> 16 return v + 1 def is_power_of_2(v): return (v & (v - 1)) == 0 """ from timeit import Timer t1 = Timer("is_power_of_2(128)", setup_1) t2 = Timer("is_power_of_2(128)", setup_2) t3 = Timer("next_power_of_2(125)", setup_1) t4 = Timer("next_power_of_2(125)", setup_2) print "float math is_power_of_2:", t1.timeit() print "bit-tiwddling is_power_of_2:", t2.timeit() print print "float math next power of 2:", t3.timeit() print "bit-twiddling next power of 2:", t4.timeit()
This produced the following results on my humble PC.
float math is_power_of_2: 3.79312203087 bit-tiwddling is_power_of_2: 1.11348704933 float math next power of 2: 4.90055467944 bit-twiddling next power of 2: 2.99615733285
The results are conclusive - bit-twiddling is still a big win in Python. I figured that the bit-twiddling is_power_of_2 function would be faster than the float math version, but I was surprised by the next_power_of_2 result. It pays to profile!
I also tested it with Psyco, and got the following results.
float math is_power_of_2: 4.33070460072 bit-tiwddling is_power_of_2: 0.037652550813 float math next power of 2: 5.66786840227 bit-twiddling next power of 2: 0.0600607060395
Wow! The bit-twidding times improved astronomically with Psyco - almost 50 times faster, by my calculations. What is surprising is that the float versions are actually a little slower with Psyco.
Conclusion? If you need to calculate the nearest power of 2 for billions of numbers in a hurry, use Psyco.
I have extended the example with another set of timings that in one case beat pyglets timing.
Check my blog entry
Note the double qouting - v |= v >> 4
Yeah, I know. I need a better syntax highlighting solution. :-(
Pygments rocks for blog syntax highlighting.
Also, I always wondered if bit-twiddling was worthwhile in Python; thanks for timing it.
Pygments does indeed rock. But I'm using wordpress, and every time I switch between editing code and wysywig mode it messes up anything in a <pre> tag. *sigh*