simulated hash vtable call

gistfile1.py

%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)