July 1, 2007 will

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.

Use Markdown for formatting
*Italic* **Bold** `inline code` Links to [Google](http://www.google.com) > This is a quote > ```python import this ```
your comment will be previewed here
gravatar
Paddy3118

I have extended the example with another set of timings that in one case beat pyglets timing.

Check my blog entry

gravatar
nirs

Note the double qouting - v |= v >> 4

gravatar
Will

Yeah, I know. I need a better syntax highlighting solution. :-(

gravatar
Bill Mill

Pygments rocks for blog syntax highlighting.

Also, I always wondered if bit-twiddling was worthwhile in Python; thanks for timing it.

gravatar
Will

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*

gravatar
...
Can't next_power_of_2 be modified so it works with long ints?
gravatar
Will McGugan
The bitwise version would have to be. No need for the math version.
gravatar
e
how about this?

 def next_power_of_2(n):
    """
    Return next power of 2 greater than or equal to n
    """
    n -= 1 # greater than OR EQUAL TO n
    shift = 1
    while (n+1) & n: # n+1 is not a power of 2 yet
        n |= n >> shift
        shift *= 2
    return n + 1