Skip to content

Instantly share code, notes, and snippets.

Created June 3, 2012 05:43
Show Gist options
  • Save anonymous/2862091 to your computer and use it in GitHub Desktop.
Save anonymous/2862091 to your computer and use it in GitHub Desktop.
simulated hash vtable call
%cython
cdef extern from *:
void* malloc(long)
void free(void*)
double sin(double)
from random import randint
from time import clock
cdef struct table_t:
long m
long r1
long r2
long r3
void *funcs[64]
cdef double times3(double x): return 3*x
cdef double times4(double x): return 4*x
cdef double times5(double x): return 5*x
cdef double times6(double x): return 6*x
cdef double times7(double x): return 7*x
cdef void populate_table(table_t* table):
table.m = 0x3F
table.r1 = randint(0, 58)
table.r2 = randint(0, 58)
table.r3 = randint(0, 58)
for i in range(64):
k = sin(i*i) * 5 + 5
if k < 2:
table.funcs[i] = &times3
elif k < 4:
table.funcs[i] = &times4
elif k < 6:
table.funcs[i] = &times5
elif k < 8:
table.funcs[i] = &times6
else:
table.funcs[i] = &times7
cdef inline double zero_table_lookup(double value, long h, table_t *table, long k):
cdef long slot = h & table.m
cdef double (*func)(double)
func = <double (*)(double)>table.funcs[slot]
return func(value)
cdef inline double one_table_lookup(double value, unsigned long h, table_t *table, long k):
cdef long slot = (h >> table.r1) & table.m
cdef double (*func)(double)
func = <double (*)(double)>table.funcs[slot]
return func(value)
cdef inline double two_table_lookup(double value, unsigned long h, table_t *table, long k):
cdef long slot = ((h >> table.r1) ^ (h >> table.r2)) & table.m
cdef double (*func)(double)
func = <double (*)(double)>table.funcs[slot]
return func(value)
cdef inline double three_table_lookup(double value, unsigned long h, table_t *table, long k):
cdef long slot = ((h >> table.r1) ^ (h >> table.r2) ^ (h >> table.r3)) & table.m
cdef double (*func)(double)
func = <double (*)(double)>table.funcs[slot]
return func(value)
def time_table_lookup(int n, double x, int shift=1):
cdef unsigned long* hs
cdef table_t table
cdef double value = 0
try:
populate_table(&table)
hs = <unsigned long*>malloc(sizeof(unsigned long) * n)
for k in range(n):
hs[k] = randint(0, 0xFFFFFFFFFFFFFFFF)
t = clock()
if shift == 0:
for k in range(n):
value += zero_table_lookup(x, hs[k], &table, k)
elif shift == 1:
for k in range(n):
value += one_table_lookup(x, hs[k], &table, k)
elif shift == 2:
for k in range(n):
value += two_table_lookup(x, hs[k], &table, k)
elif shift == 3:
for k in range(n):
value += three_table_lookup(x, hs[k], &table, k)
return (clock() - t) / n, value
finally:
free(hs)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment