simulated hash vtable call

gistfile1.py

cdef extern from *:
    void* malloc(long)
    void free(void*)
    double sin(double)

from random import randint
from time import clock

cdef extern from "time.h":
    cdef struct timespec:
        long tv_sec
        long tv_nsec
    void clock_gettime(int, timespec*)
    int CLOCK_REALTIME

cdef double walltime():
  cdef timespec tv
  clock_gettime(CLOCK_REALTIME, &tv)
  return tv.tv_sec + 1e-9 * tv.tv_nsec



cdef extern from *:
    int likely(int)

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 table_lookup_first_element(double value, long h, table_t *table, long k):
    func = <double (*)(double)>table.funcs[0]
    return func(value)

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 = walltime()
        if shift == -2:
            for k in range(n):
                value += times4(x)
        elif shift == -1:
            for k in range(n):
                value += table_lookup_first_element(x, hs[k], &table, k)
        elif 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 (walltime() - t) / n, value
    finally:
        free(hs)