Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Calculate the execution times of popcount functions
# coding: utf-8
def dummy(n):
return 0
def popcnt0(n):
c = 0
for i in range(64):
c += (n >> i) & 1
return c
def popcnt1(n):
return bin(n).count("1")
def popcnt2(n):
return "{:b}".format(n).count("1")
#https://qiita.com/ocxtal/items/01c46b15cb1f2e656887
def popcnt3(n):
c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
return c
#http://www.valuedlessons.com/2009/01/popcount-in-python-with-benchmarks.html
POPCOUNT_TABLE8 = [0] * 2**8
for index in range(len(POPCOUNT_TABLE8)):
POPCOUNT_TABLE8[index] = (index & 1) + POPCOUNT_TABLE8[index >> 1]
def popcnt4(v):
return (POPCOUNT_TABLE8[ v & 0xff] +
POPCOUNT_TABLE8[(v >> 8) & 0xff] +
POPCOUNT_TABLE8[(v >> 16) & 0xff] +
POPCOUNT_TABLE8[(v >> 24) & 0xff] +
POPCOUNT_TABLE8[(v >> 32) & 0xff] +
POPCOUNT_TABLE8[(v >> 40) & 0xff] +
POPCOUNT_TABLE8[(v >> 48) & 0xff] +
POPCOUNT_TABLE8[ v >> 56 ])
POPCOUNT_TABLE16 = [0] * 2**16
for index in range(len(POPCOUNT_TABLE16)):
POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]
def popcnt5(v):
return (POPCOUNT_TABLE16[ v & 0xffff] +
POPCOUNT_TABLE16[(v >> 16) & 0xffff] +
POPCOUNT_TABLE16[(v >> 32) & 0xffff] +
POPCOUNT_TABLE16[(v >> 48) ])
import gmpy2
popcnt6 = gmpy2.popcount
if __name__ == "__main__":
import random
def randloopf(f):
return lambda: f(random.getrandbits(64))
for n in range(100000):
rand = random.getrandbits(64)
assert popcnt0(rand) == popcnt1(rand) == popcnt2(rand) == popcnt3(rand) == popcnt4(rand) == popcnt5(rand) == popcnt6(rand)
import timeit
number=1000000
#timeit.timeit(randloopf(popcnt0), number=number) # warm up
print("dummy:", timeit.timeit(randloopf(dummy), number=number))
print("popcnt0:", timeit.timeit(randloopf(popcnt0), number=number))
print("popcnt1:", timeit.timeit(randloopf(popcnt1), number=number))
print("popcnt2:", timeit.timeit(randloopf(popcnt2), number=number))
print("popcnt3:", timeit.timeit(randloopf(popcnt3), number=number))
print("popcnt4:", timeit.timeit(randloopf(popcnt4), number=number))
print("popcnt5:", timeit.timeit(randloopf(popcnt5), number=number))
print("popcnt6:", timeit.timeit(randloopf(popcnt6), number=number))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment