Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Perfect Hashes and faster than memcmp

blogs.perl.org

Post reply on HN
Print view View original

1–10 of 19 posts

Re: Perfect Hashes and faster than memcmp

#2

Post by dpayne »

One caveat of perfect hash functions, including CMPH, is that for a very large amount of keys the data structs they use internally become very large. In the case of CMPH when I tried with around 30 million keys the result was several MBs which caused it to not fit in L3 cache. For large dictionaries, hash functions like xxhash and farmhash are usually a better option than the perfect hash functions.

Re: Perfect Hashes and faster than memcmp

#3

Post by hurin »

dpayne wrote: post #2

One caveat of perfect hash functions, including CMPH, is that for a very large amount of keys the data structs they use internally become very large. In the case of CMPH when I tried with around 30 million keys the result was several MBs which caused it to not fit in L3 cache. For large dictionaries, hash functions like xxhash and farmhash are usually a better option than the perfect hash functions.

I don't know much about the topic but I was under the impression a minimal 1 to 1 mapping is usually possible. ref: http://www.burtleburtle.net/bob/hash/perfect.html

Re: Perfect Hashes and faster than memcmp

#4

Post by t1m »

dpayne wrote: post #2

One caveat of perfect hash functions, including CMPH, is that for a very large amount of keys the data structs they use internally become very large. In the case of CMPH when I tried with around 30 million keys the result was several MBs which caused it to not fit in L3 cache. For large dictionaries, hash functions like xxhash and farmhash are usually a better option than the perfect hash functions.

You can combine perfect hashing with string compression (Huffman, prefix tries) and de-duplication techniques to vastly improve memory usage for a wide variety of use cases. DiscoDB does this to good effect (http://discodb.readthedocs.org/en/latest/).

Re: Perfect Hashes and faster than memcmp

#6

Post by ot »

cmph is not the fastest library for MPHF, mostly because it uses a slow ranking function to turn a PHF into a MPHF.

I wrote a small library some time ago that performs much faster, both for in-memory construction and lookups, [1, see the linked paper for benchmarks], unfortunately I have no time to maintain it but I recently found out that some projects are using it, so it wasn't all wasted time :)

[1] https://github.com/ot/emphf

Re: Perfect Hashes and faster than memcmp

#7

Post by ot »

dpayne wrote: post #2

One caveat of perfect hash functions, including CMPH, is that for a very large amount of keys the data structs they use internally become very large. In the case of CMPH when I tried with around 30 million keys the result was several MBs which caused it to not fit in L3 cache. For large dictionaries, hash functions like xxhash and farmhash are usually a better option than the perfect hash functions.

If you use a fast hash function you still have to look up a hash table, so the memory access is still there. If you use some clever probing strategy you might be able to have only 1 cache line access per lookup on average, while most perfect hashing functions, which use the MWHC scheme, do 3 random accesses.

However, these 3 random accesses are independent, so the CPU can mostly pipeline them, and the perceived latency is that of a single random access.

Re: Perfect Hashes and faster than memcmp

#8

Post by dchichkov »

If anyone is interested, I have a cute nearly-minimal perfect hashing algorithm designed to have good cache-friendly properties. It works very well in practice and in my particular application was performing faster and more consistently (no long tail) than anything found in CMPH.

Briefly, it is somewhat similar to hopscotch (or robin-hood) hashing, only you pre-calculate positions of the elements to put them into optimal spots by solving the assignment problem (via Hungarian assignment problem solver or such). Works for up to about 50k elements. It feels like it might have good theoretical properties, might be even optimal (after all, we pretty much calculating optimal positions of the elements based on the costs of our memory/cache accesses and probabilities of each element), but it was a while since I've taken the algorithms class.

If anyone is interested to do a writeup and publish clean source code - you'd be welcome, ping me via e-mail.

Re: Perfect Hashes and faster than memcmp

#9

Post by rurban »

fake-name wrote: post #5

For the love of FSM, please don't call your library "phash". "phash" is already in wide use for "perceptual hash", or the hashing mechanisms used for things like fuzzy image searching.

Oh, I am on HN :)

Okay, point taken. I didn't know about this name. "pperf" maybe then. Note that this is still work in progress, I just had to finish another project, and will come back to this one soon.

EDIT: I've renamed the frontend to "pperf" now https://github.com/rurban/Perfect-Hash/commit/b475886f37d9

But the memcmp trick with unrolling of the comparisons beforehand for constant keys is already usable, and I believe someone already considered that optimization for gcc and llvm. If I remember I even saw a patch already. It should be used for switch statements with constant keys.

Re: Perfect Hashes and faster than memcmp

#10

Post by rurban »

ot wrote: post #6

cmph is not the fastest library for MPHF, mostly because it uses a slow ranking function to turn a PHF into a MPHF. I wrote a small library some time ago that performs much faster, both for in-memory construction and lookups, [1, see the linked paper for benchmarks], unfortunately I have no time to maintain it but I recently found out that some projects are using it, so it wasn't all wasted time :) [1] https://github…

Excellent. I'll take it :)
Post reply on HN