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

Writing a Very Fast Hash Table with Tiny Memory Footprints

idryman.org

Post reply on HN
Print view View original

41–50 of 53 posts

Re: Writing a Very Fast Hash Table with Tiny Memory Footprints

#41

Post by dgacmu »

One nit, as one of the authors of libcuckoo: Of the tested tables, libcuckoo is the only one that's a concurrent hash table. I'm glad that without modification, our single-threaded performance is still doing well, but this isn't the primary use case of libcuckoo.

If you want to compare it against a thread-unsafe table, it's a bit more honest to use the locked_table class, which grants ownership to all locks in the table in advance. It's a fair bit faster.

It doesn't change the memory use - I've created a stripped-down version in the past that elides all the locks, which is better for memory efficiency - but that's not really our goal.

For more on using the locked_table interface, see: https://github.com/efficient/libcuckoo/blob/master/tests/uni...

(Also, for hashing strings, please make sure you've got libcuckoo configured to use cityhash for string hashing, as you had "opic", to make the comparison equivalent.)

In fairness to the OP, however, it's worth noting that this is a pretty new addition to libcuckoo (February), and we haven't documented or pushed it hard.

Re: Writing a Very Fast Hash Table with Tiny Memory Footprints

#42

Post by dgacmu »

dryman wrote: post #40
lorenzhs wrote: post #34

If you're interested in truly space-efficient hash tables—as in "at every point in time, at least 97% of the space of the table is used for elements"—check out this paper by a colleague of mine: https://arxiv.org/pdf/1705.00997.pdf (the relevant plots are on pages 10 and 11). He's going to publish the code soon-ish as well.

In my experiments using linear probing in robin hood doesn't give good results as well. I hope the author has tried robin hood with quadratic probing. But it's a good reference. I didn't dive deep in the cuckoo route. This paper gives me more confidence to try it out.

If you're curious about blending some of the "don't increase by a power of two" memory efficiency gains, I implemented this in a cuckoo hash table for TensorFlow, also using Lemire's trick: https://github.com/tensorflow/tensorflow/blob/master/tensorf...

I never back-ported it to libcuckoo, because it adds a fair bit of complexity (and requires an extra bit), but if there's demand for non-2^k tables, I'd love to know more, either externally or internally. (dga@, for various values of cs.cmu.edu and google)

Re: Writing a Very Fast Hash Table with Tiny Memory Footprints

#43

Post by luckydude »

tawayway wrote: post #38
luckydude wrote: post #7

Look up MDBM. I spent a lot of time with a logic analyzer watching the cache misses go across the bus. I'd be pretty surprised if someone has done better. I can find the code and repost it.

Out of curiosity, what kind of logic analyzer are you using that can see events that fast?

I dunno, it was a long time ago at SGI, maybe 23 years ago? The CPUs were 200mhz MIPS chips. One of the hardware guys heard me talking about trying to optimize this code and he set up the analyzer and taught me how to use it.

Re: Writing a Very Fast Hash Table with Tiny Memory Footprints

#44

Post by dryman »

dgacmu wrote: post #41

One nit, as one of the authors of libcuckoo: Of the tested tables, libcuckoo is the only one that's a concurrent hash table. I'm glad that without modification, our single-threaded performance is still doing well, but this isn't the primary use case of libcuckoo. If you want to compare it against a thread-unsafe table, it's a bit more honest to use the locked_table class, which grants ownership to all locks in the ta…

Thanks for pointing out the thread-unsafe alternative. I'll update the benchmark with it and double I configured it with cityhash. (will update in a day or two).

Speaking of cityhash, have you tried farmhash as well? I'm not sure what I did wrong, but farmhash's performance wasn't good as cityhash in my hash table. Did you experience the same problem?

Re: Writing a Very Fast Hash Table with Tiny Memory Footprints

#45

Post by dgacmu »

dryman wrote: post #44
dgacmu wrote: post #41

One nit, as one of the authors of libcuckoo: Of the tested tables, libcuckoo is the only one that's a concurrent hash table. I'm glad that without modification, our single-threaded performance is still doing well, but this isn't the primary use case of libcuckoo. If you want to compare it against a thread-unsafe table, it's a bit more honest to use the locked_table class, which grants ownership to all locks in the ta…

Thanks for pointing out the thread-unsafe alternative. I'll update the benchmark with it and double I configured it with cityhash. (will update in a day or two). Speaking of cityhash, have you tried farmhash as well? I'm not sure what I did wrong, but farmhash's performance wasn't good as cityhash in my hash table. Did you experience the same problem?

Thanks! Appreciate the responsiveness. :)

We haven't - I had some other issues with Farm. I tried for a while to see if I could get FarmHash included as the standard hash for TensorFlow instead of the murmur-like homebrewed one it uses, but the cross-platform build issues became too complicated to justify it. We ended up sticking with the murmur-like one for "fast but unsafe", and providing SIP via the highwayhash package as the "strong hash".

Re: Writing a Very Fast Hash Table with Tiny Memory Footprints

#46

Post by dryman »

dgacmu wrote: post #42
dryman wrote: post #40

Earlier quoted context omitted.

In my experiments using linear probing in robin hood doesn't give good results as well. I hope the author has tried robin hood with quadratic probing. But it's a good reference. I didn't dive deep in the cuckoo route. This paper gives me more confidence to try it out.

If you're curious about blending some of the "don't increase by a power of two" memory efficiency gains, I implemented this in a cuckoo hash table for TensorFlow, also using Lemire's trick: https://github.com/tensorflow/tensorflow/blob/master/tensorf... I never back-ported it to libcuckoo, because it adds a fair bit of complexity (and requires an extra bit), but if there's demand for non-2^k tables, I'd love to know…

Lemire's fast range works perfectly with cuckoo, as it doesn't require probing (?). The fast mod and scale trick was invented to address this issue.

It's actually pretty funny. I didn't know Lemire's trick until I start to write this article. But I my first try on fixed point arithmetic was exactly the same as his work. Then figured out the lower bits would get omitted with fast range (I named it scaling). Finally I came up with this fast mod and scale idea.

I don't know for other peoples need on non power of 2 tables. My target is to build large scale hash tables and other data structures. The memory and data compactness is quite critical for this goal.

Re: Writing a Very Fast Hash Table with Tiny Memory Footprints

#47

Post by pkhuong »

pubby wrote: post #15
johnfn wrote: post #12

Earlier quoted context omitted.

> pretty much all of the existing articles about it are missing some crucial facts about it. Would you mind expanding on those facts?

1) The linearly-probed robin hood variant is just a sorted array. That's it. It's just a sorted array. I haven't seen an article explain it so succinctly though. 2) The linearly-probed robin hood variant is only faster than regular linear probing for searches that fail. Successful searches have the same average probe count. Too many articles bullshit about how robin hood reduces variance (which is irrelevant 99% of t…

> 1) The linearly-probed robin hood variant is just a sorted array. That's it. It's just a sorted array.

Right. I stumbled on linear probing robin hood hashing as a simplification of Bender, Demaine and Farach-Colton's Packed memory array (http://erikdemaine.org/papers/FOCS2000b/paper.pdf) when inserts are randomised.

> 2) The linearly-probed robin hood variant is only faster than regular linear probing for searches that fail.

The sortedness means Robin Hood should not only be faster in the worst case (that's what reducing variance is all about), even for successful searches, but can also be faster on average, at high enough loads: make sure empty cells compare as greater than any legitimate value, track the maximum displacement, and use binary search (or just use exponential search).

Re: Writing a Very Fast Hash Table with Tiny Memory Footprints

#48

Post by jsnell »

glandium wrote: post #35
jsnell wrote: post #29

Earlier quoted context omitted.

Small string optimization should kick in here, so you're probably not looking at a size_t + pointer + a object with the 6 bytes of payload data. Instead it'd be a single object of about 32 bytes (depending on the implementation). But yes, this means that the author's own hash table implementation is getting a roughly 4-5x density benefit from using a different string representation. That totally invalidates the memor…

Thank you for making me look at the implementation of std::string in GCC's libstdc++... The "small string optimization" indeed makes every std::string at least 1 size_t + 1 pointer + 16 bytes large (for a total of 32 bytes on 64-bits platforms). Strings smaller than 16 bytes are stored in the 16 bytes inline buffer, which means strings larger than that actually take 32 + their length + 1 bytes in memory on 64-bits pl…

> I guess things are not packed further to allow to just directly use the pointer instead of having to do some computation for each access.

There are C++ standard libraries that pack things further. I think clang has a 24 byte std::string, which can store strings of up to 22 bytes inline.

Re: Writing a Very Fast Hash Table with Tiny Memory Footprints

#49

Post by adrianN »

usefulcat wrote: post #39
adrianN wrote: post #30

Earlier quoted context omitted.

But that's what profiling is for.

Profiling won't tell you what the chances are that the collection will someday need to contain more than N elements.

You don't replace every map in your code with a distributed Key-Value store, in case it might need to store terabytes in the future. Most of the time you have a pretty good idea whether a map has to store a hundred, or a hundred thousand elements.

Re: Writing a Very Fast Hash Table with Tiny Memory Footprints

#50

Post by Veedrac »

nom wrote: post #9
skolos wrote: post #2

I see often discussions about hash maps on HN. However they mostly focus on performance (memory and speed) of one huge hash map with millions of records. In my numerical calculations I often need lots of small hash maps (say up to 100 elements). Currently I use unordered_maps from C++ standard library. Does anyone know what is recommended hash map implementation for my scenario?

For very small number of elements, an array or a list can be more efficient than hash maps. My rule of thumb is to avoid hash maps if you know you'll never have more than 100 entries, and then try to find the bottleneck later on. Using hash maps for everything isn't always the best solution.

If you're looking for elements by identity, that's going to be really slow. Hash maps are designed precisely to handle that scenario, and devolving to linear scans is only going to make things worse.
Post reply on HN