[Cython] Hash-based vtables

[Dag Sverre Seljebotn]

On 06/06/2012 10:41 PM, Dag Sverre Seljebotn wrote:
> On 06/05/2012 12:30 AM, Robert Bradshaw wrote:
>> I just found http://cmph.sourceforge.net/ which looks quite
>> interesting. Though the resulting hash functions are supposedly cheap,
>> I have the feeling that branching is considered cheap in this context.
>
> Actually, this lead was *very* promising. I believe the very first
> reference I actually read through and didn't eliminate after the
> abstract totally swept away our home-grown solutions!
>
> "Hash & Displace" by Pagh (1999) is actually very simple, easy to
> understand, and fast both for generation and (the branch-free) lookup:
>
> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.69.3753&rep=rep1&type=pdf
>
>
> The idea is:
>
> - Find a hash `g(x)` to partition the keys into `b` groups (the paper
> requires b > 2n, though I think in practice you can often get away with
> less)
>
> - Find a hash `f(x)` such that f is 1:1 within each group (which is
> easily achieved since groups only has a few elements)
>
> - For each group, from largest to smallest: Find a displacement
> `d[group]` so that `f(x) ^ d` doesn't cause collisions.
>
> It requires extra storage for the displacement table. However, I think 8
> bits per element might suffice even for vtables of 512 or 1024 in size.
> Even with 16 bits it's rather negligible compared to the minimum-128-bit
> entries of the table.
>
> I benchmarked these hash functions:
>
> displace1: ((h >> r1) ^ d[h & 63]) & m1
> displace2: ((h >> r1) ^ d[h & m2]) & m1
> displace3: ((h >> r1) ^ d[(h >> r2) & m2]) & m1
>
> Only the third one is truly in the spirit of the algorithm, but I think
> the first two should work well too (and when h is known compile-time,
> looking up d[h & 63] isn't harder than looking up r1 or m1).
>
> My computer is acting up and all my numbers today are slower than the
> earlier ones (yes, I've disabled turbo-mode in the BIOS for a year ago,
> and yes, I've pinned the CPU speed). But here's today's numbers,
> compiled with -DIMHASH:
>
> direct: min=5.37e-09 mean=5.39e-09 std=1.96e-11 val=2400000000.000000
> index: min=6.45e-09 mean=6.46e-09 std=1.15e-11 val=1800000000.000000
> twoshift: min=6.99e-09 mean=7.00e-09 std=1.35e-11 val=1800000000.000000
> threeshift: min=7.53e-09 mean=7.54e-09 std=1.63e-11 val=1800000000.000000
> displace1: min=6.99e-09 mean=7.00e-09 std=1.66e-11 val=1800000000.000000
> displace2: min=6.99e-09 mean=7.02e-09 std=2.77e-11 val=1800000000.000000
> displace3: min=7.52e-09 mean=7.54e-09 std=1.19e-11 val=1800000000.000000
>
>
> I did a dirty prototype of the table-finder as well and it works:
>
> https://github.com/dagss/hashvtable/blob/master/pagh99.py

The paper obviously puts more effort on minimizing table size and not a 
fast lookup. My hunch is that our choice should be

((h >> table.r) ^ table.d[h & m2]) & m1

and use 8-bits d (because even if you have 1024 methods, you'd rather 
double the number of bins than those 2 extra bits available for 
displacement options).

Then keep incrementing the size of d and the number of table slots (in 
such an order that the total vtable size is minimized) until success. In 
practice this should almost always just increase the size of d, and keep 
the table size at the lowest 2**k that fits the slots (even for 64 
methods or 128 methods :-))

Essentially we avoid the shift in the argument to d[] by making d larger.

Dag