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

11–20 of 53 posts

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

#11

Post by pubby »

Not to disgrace the author (it's a good article), but I've spent a lot of time studying hashtable performance recently and I groan whenever I see benchmarks against libraries like std::unordered_map or libcuckoo. No shit your hash table performs better; it's like claiming you're good at running because you can beat a crippled child in a race.

For a test to be meaningful it needs to include comparisons to linear probing (both regular, robin-hood variants, and SSE variants), and other low-cost hash tables like coalesced hashing or separate chaining with a memory pool.

Speaking of robin hood hashing, pretty much all of the existing articles about it are missing some crucial facts about it. Don't take what blog authors say for granted.

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

#12

Post by johnfn »

pubby wrote: post #11

Not to disgrace the author (it's a good article), but I've spent a lot of time studying hashtable performance recently and I groan whenever I see benchmarks against libraries like std::unordered_map or libcuckoo. No shit your hash table performs better; it's like claiming you're good at running because you can beat a crippled child in a race. For a test to be meaningful it needs to include comparisons to linear probi…

> pretty much all of the existing articles about it are missing some crucial facts about it.

Would you mind expanding on those facts?

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

#13

Post by dryman »

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.

I found some performance numbers from Yahoo. https://yahooeng.tumblr.com/post/104861108931/mdbm-high-spee... It has random read time 0.45 μs. On my late 2013 iMac, i5 cpu, I got 0.089 μs random read. I yet to have a benchmark that measures sequential read, but the API supports it.

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

#14

Post by oconnor0 »

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.

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.

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

#15

Post by pubby »

johnfn wrote: post #12
pubby wrote: post #11

Not to disgrace the author (it's a good article), but I've spent a lot of time studying hashtable performance recently and I groan whenever I see benchmarks against libraries like std::unordered_map or libcuckoo. No shit your hash table performs better; it's like claiming you're good at running because you can beat a crippled child in a race. For a test to be meaningful it needs to include comparisons to linear probi…

> 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 the time) and then go on to ignore the fact that they cannot beat the performance of linear probing when it comes to successful searches. One guy I saw spent hours trying to optimize his hash table for the K-nucleotide benchmark without realizing that a trivial 5-minute implementation of linear probing would beat it because searches in that benchmark never fail.

3) There's a simple 40 year old bitwise trick by Knuth which allows one to combine the probe distance and the hash into a single value. This saves up to 4 bytes per table entry, but I haven't seen anyone use it.

There's also a few articles that get deletion straight-up wrong, but meh. That doesn't bother me too much.

Also, for double hashing I'm pretty sure a SSE/AVX variant is optimal. I haven't tried implementing one though.

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

#16

Post by dryman »

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) I don't see why a linear probing robin hood is a sorted array? Can you explain more?

Robin hood hashing doesn't limit which probing scheme you use. I end up with quadratic probing which gives me both good cache locality and good probe distributions. The probing schemes I tried was omitted in this post because it would bring too much noise. But I can give you some quick summary here:

1. linear probing: probing distribution has high medium and high variance. Performance is not that great either because of the high probing numbers.

2. quadratic probing: probing distribution is not the best, but the medium sicks to 2 probes. Since the first two probes are very close in quadratic probing, its overall performance wins.

3. When probing, hash the key with the probe added to the seed. This gives very good hash distribution, but hash on each probe is very slow. Also you cannot do deletion using this scheme.

4. rotate(key, probe). This is somewhat like rehash, but way faster. The probe distribution is also very good, but items goes too far away so we lost the cache locality.

5. Combination of different schemes listed above. Still, the quadratic probing gives me best performance.

I also tried to use gcc/clang vector extension to speed up probing, but it actually slows down for 30%! I guess I have to hand tune the SSE intrinsics and measure it carefully with IACA to get the optimal performance.

Deletion itself is quite complicated and deserves its own post.

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

#17

Post by glandium »

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 each key and value) for each item.

In fact, a quick look at the OP's benchmark code shows he's using std::string as keys and uint64 as values. With e.g. std::unordered_map, while pointers won't be used for the values, there obviously will be pointers for the key.

It's actually worse than pointers, since the std::string memory layout is a size_t and a char* pointer. And it looks like his hash table essentially uses the equivalent of char[6] as keys. So a fairer memory overhead comparison should use char[6] as keys, instead of std::string...

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

#18

Post by pubby »

dryman wrote: post #16
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) I don't see why a linear probing robin hood is a sorted array? Can you explain more? Robin hood hashing doesn't limit which probing scheme you use. I end up with quadratic probing which gives me both good cache locality and good probe distributions. The probing schemes I tried was omitted in this post because it would bring too much noise. But I can give you some quick summary here: 1. linear probing: probing dist…

I was actually working on a blog post about this a few months ago, but never published it because I wasn't happy with it. Here it is, anyway: https://goo.gl/W1KZ2t

What I found in testing was that linear probing beat everything when it had a sufficiently good hash function and a sufficiently low load factor. The load factor was pretty important. Even when factoring in cache misses, page faults, and the cost of allocations, a linearly probed table with a low load factor always beat more space-efficient designs.

>I also tried to use gcc/clang vector extension to speed up probing, but it actually slows down for 30%! I guess I have to hand tune the SSE intrinsics and measure it carefully with IACA to get the optimal performance.

They're only advantageous when the hash is perfect and the data is in the cache. Otherwise the performance should be the same as regular code. To clarify what I meant by SSE with double hashing, I really meant search an entire cacheline before incrementing by the second hash value. SSE can be used for this in some cases but regular code works just as well.

>Deletion itself is quite complicated and deserves its own post.

That's why I prefer the linear variant; deletion is easy!

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

#19

Post by valarauca1 »

dryman wrote: post #16
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) I don't see why a linear probing robin hood is a sorted array? Can you explain more? Robin hood hashing doesn't limit which probing scheme you use. I end up with quadratic probing which gives me both good cache locality and good probe distributions. The probing schemes I tried was omitted in this post because it would bring too much noise. But I can give you some quick summary here: 1. linear probing: probing dist…

It's a sorted array because your sorting by 2 keys (A,B). A is the hash, normally a u32 or u64. B is the probe count, also normally the same sized b/c system ints are easy.

Strictly speaking the Robin Hood "sort" isn't purely lexiconally ordered. A larger A value maybe replaced a smaller A, with a much larger B.

But this relation nonetheless is just a weird solution to build a cmp function one. One that arguably doesn't work in a strict sense. But one that _nearly_ works.

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

#20

Post by dastbe »

valarauca1 wrote: post #19
dryman wrote: post #16

Earlier quoted context omitted.

1) I don't see why a linear probing robin hood is a sorted array? Can you explain more? Robin hood hashing doesn't limit which probing scheme you use. I end up with quadratic probing which gives me both good cache locality and good probe distributions. The probing schemes I tried was omitted in this post because it would bring too much noise. But I can give you some quick summary here: 1. linear probing: probing dist…

It's a sorted array because your sorting by 2 keys (A,B). A is the hash, normally a u32 or u64. B is the probe count, also normally the same sized b/c system ints are easy. Strictly speaking the Robin Hood "sort" isn't purely lexiconally ordered. A larger A value maybe replaced a smaller A, with a much larger B. But this relation nonetheless is just a weird solution to build a cmp function one. One that arguably does…

So if A is the hashed-to index into your table, then B is a function of A. When you are doing your linear probe and you see a value along with its probe count, it either

1. Has a higher probe count, this means it's hash is further away than yours => less than yours

2. Has a lower probe count than yours. This means its hash is closer than yours => greater than yours

3. Is equal in probe count to yours. That means it's in the same bucket => equal to yours.

Post reply on HN