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
_______________________________________________
cython-devel mailing list
cython-devel@python.org
http://mail.python.org/mailman/listinfo/cython-devel
