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

31–40 of 53 posts

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

#31

Post by pubby »

frankmcsherry wrote: post #27
pubby wrote: post #15

Earlier quoted context omitted.

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. I haven't seen an article explain it so succinctly though. It's not. Importantly, it leaves spaces so that you avoid what would be ~sqrt(n) probe lengths had you tightly packed everything. Also, it is a bit out of order as you wrap around the limits of the array (less of a big deal). The sortedness property is rea…

>When the values are sorted (modulo empties and wrapping) you don't need to store the probe length. You just maintain the invariant that things are sorted. Maybe I'm missing some detail of your implementation, but mine sure don't bother storing it.

Storing the probe count allows the lookup function to have 2 branches per loop as opposed to 3. The probe count also contains enough information to distinguish occupied buckets from unoccupied ones. I'm convinced that combining the probe count with the hash is objectively the best way to implement such tables.

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

#32

Post by frankmcsherry »

pubby wrote: post #31
frankmcsherry wrote: post #27

Earlier quoted context omitted.

> 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. It's not. Importantly, it leaves spaces so that you avoid what would be ~sqrt(n) probe lengths had you tightly packed everything. Also, it is a bit out of order as you wrap around the limits of the array (less of a big deal). The sortedness property is rea…

>When the values are sorted (modulo empties and wrapping) you don't need to store the probe length. You just maintain the invariant that things are sorted. Maybe I'm missing some detail of your implementation, but mine sure don't bother storing it. Storing the probe count allows the lookup function to have 2 branches per loop as opposed to 3. The probe count also contains enough information to distinguish occupied bu…

Can I convince you to downgrade to being subjectively convinced?

Storing hashes or probes wasn't faster for the use cases I evaluated. I can see reasons why you might like it, for your uses and perhaps "generally", but not in my case at least (small keys where storage bloat was worse than `fnv` recompute, and values which had invalid states which can be used to represent empties)

Edit: I'm re-reading my first response and it reads like "you never need/want the probe length", and I totally retract that position; it wasn't intended.

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

#33

Post by posnet »

dryman wrote: post #8
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.

Thanks for the reference. I'm collecting a list of embedded key-value store to benchmark against. I'll tryout with this one first!

https://github.com/pmwkaa/engine.so

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

#34

Post by lorenzhs »

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.

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

#35

Post by glandium »

jsnell wrote: post #29
glandium wrote: post #17

I only skimmed over, but about memory overhead: > The input is 8 M key-value pairs; size of each key is 6 bytes and size of each value is 8 bytes. The lower bound memory usage is (6+8)⋅2^23= 117MB In many case, hash table implementation won't (can't) assume fixed size of keys and values, and use pointers. On 64-bit architectures, this can mean there's an uncompressible overhead of 8 * 2 = 16 bytes (one pointer for ea…

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 platforms.

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.

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

#36

Post by arjie »

adrianN wrote: post #30
oconnor0 wrote: post #14

Earlier quoted context omitted.

Using a sequence instead of a map is fine if you know it will never be more than some small number of entries, but so often we are wrong about how many entries will be in a table that the N-squared use of a sequence as a map kills performance unexpectedly.

But that's what profiling is for.

That argument favours hashmaps by default, though. After all, they're all right at small sizes and much better at big sizes.

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

#37

Post by dom0 »

dryman wrote: post #8
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.

Thanks for the reference. I'm collecting a list of embedded key-value store to benchmark against. I'll tryout with this one first!

LMDB

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

#38

Post by tawayway »

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?

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

#39

Post by usefulcat »

adrianN wrote: post #30
oconnor0 wrote: post #14

Earlier quoted context omitted.

Using a sequence instead of a map is fine if you know it will never be more than some small number of entries, but so often we are wrong about how many entries will be in a table that the N-squared use of a sequence as a map kills performance unexpectedly.

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.

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

#40

Post by dryman »

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.
Post reply on HN