Dag Sverre Seljebotn <d.s.seljeb...@astro.uio.no> wrote:
>On 06/06/2012 11:16 PM, Robert Bradshaw wrote: >> On Wed, Jun 6, 2012 at 1:57 PM, Dag Sverre Seljebotn >> <d.s.seljeb...@astro.uio.no> wrote: >>> 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. >> >> Nice. I'm surprised that the indirection on d doesn't cost us much; > >Well, table->d[const & const] compiles down to the same kind of code as > >table->m1. I guess I'm surprised too that displace2 doesn't penalize. > >> hopefully its size wouldn't be a big issue either. What kinds of >> densities were you achieving? > >The algorithm is designed for 100% density in the table itself. (We can > >lift that to compensate for a small space of possible hash functions I >guess.) > >I haven't done proper simulations yet, but I just tried |vtable|=128, >|d|=128 from the command line and I had 15 successes or so before the >first failure. That's with a 100% density in the vtable itself! (And >when it fails, you increase |d| to get your success). > >The caveat is the space spent on d (it's small in comparison, but >that's >why this isn't too good to be true). > >A disadvantage might be that we may no longer have the opportunity to >not make the table size a power of two (i.e. replace the mask with "if >(likely(slot < n))"). I think for that to work one would need to >replace >the xor group with addition on Z_d. Strike this paragraph; don't know what I was thinking... Dag > >> Going back to the idea of linear probing on a cache miss, this has >the >> advantage that one can write a brain-dead provider that sets m=0 and >> simply lists the methods instead of requiring a table optimizer. >(Most >> tools, of course, would do the table optimization.) It also lets you >> get away with a "kind-of good" hash rather than requiring you search >> until you find a (larger?) perfect one. > >Well, given that we can have 100% density, and generating the table is >lightning fast, and the C code to generate the table is likely a 300 >line utility... I'm not convinced. > >We should however make sure that *callers* can do a linear scan and use > >strcmp if they don't care about performance. > >Dag >_______________________________________________ >cython-devel mailing list >cython-devel@python.org >http://mail.python.org/mailman/listinfo/cython-devel -- Sent from my Android phone with K-9 Mail. Please excuse my brevity. _______________________________________________ cython-devel mailing list cython-devel@python.org http://mail.python.org/mailman/listinfo/cython-devel
