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

21–30 of 53 posts

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

#21

Post by corysama »

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!

Fun note: Because of this line in the article

> Because MDBM gives you raw pointers into the DB’s data, you have to be very careful about making sure you don’t have array over-runs, invalid pointer access, or the like.

Someone wrote a Rust binding http://erickt.github.io/blog/2014/12/13/rust-and-mdbm/

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

#22

Post by dryman »

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…

Thanks for pointing out. I used std::string mainly because I suck at C++ :(. In C I can easily define the key length to be a variable passed to the constructor, but I don't know how to do the same with C++.

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

#23

Post by dryman »

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…

When I first see "sorted array", my first impression is it is sorted by the "original key". If we look for the hashed value in hash table, all hash tables are "sorted array" with this definition.

Also there's a finial mod in linear probing h(k, i) = (k + i) mod N. With this mod you may have different key/probe combination that messed up the order.

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

#24

Post by searchfaster »

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 can find the code and repost it.

Here it is.. https://github.com/yahoo/mdbm

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

#25

Post by faitswulff »

This note about his other project (that the robin hood hash table depends on) is quite curious:

> This robin hood hashing is implemented using my project Object Persistence In C (OPIC). OPIC is a new general serialization framework I just released. Any in-memory object created with OPIC can be serialized without knowing how it was structured. Deserializing objects from OPIC only requires one mmap syscall. That’s say, this robin hood implementation can work not only in a living process, the data it stored can be used as a key-value store after the process exits.

> Right now, the throughput of OPIC robin hood hash map on small keys (6bytes) is 9M (1048576/0.115454). This is way better than most NoSQL key-value stores. The difference might come from write ahead logs or some other IO? I’m not sure why the performance gain is so huge. My next stop is to benchmark against other embedded key-value store like rocksdb, leveldb and so forth.

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

#26

Post by dryman »

corysama wrote: post #21
dryman wrote: post #8

Earlier quoted context omitted.

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

Fun note: Because of this line in the article > Because MDBM gives you raw pointers into the DB’s data, you have to be very careful about making sure you don’t have array over-runs, invalid pointer access, or the like. Someone wrote a Rust binding http://erickt.github.io/blog/2014/12/13/rust-and-mdbm/

Wow that's a very interesting post! Maybe I should try to bring a rust binding to my project as well..

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

#27

Post by frankmcsherry »

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. 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 really useful, btw. A RHH lets you get the perf of a good hash map for random access, and the throughput of a sorted list for merges / bulk processing.

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

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.

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

#28

Post by dryman »

faitswulff wrote: post #25

This note about his other project (that the robin hood hash table depends on) is quite curious: > This robin hood hashing is implemented using my project Object Persistence In C (OPIC). OPIC is a new general serialization framework I just released. Any in-memory object created with OPIC can be serialized without knowing how it was structured. Deserializing objects from OPIC only requires one mmap syscall. That’s say,…

Thanks for raising this up. I spent way way more time on OPIC (almost a year) than robin hood hash map (2 weeks to complete the POC). Glad to see people noticing this project :)

The other comment pointed out MDBM, which I didn't know about. From their performance number I think this may show that why OPIC robin hood is quite optimal. https://yahooeng.tumblr.com/post/104861108931/mdbm-high-spee...

MDMB gives users raw access to the mmaped data and pointers. And from its benchmarks it results 10x faster than rocksdb and leveldb. The design of OPIC has even less overhead (may not be a good thing) than MDBM, and it also works on a mmaped file (or anonymous swap). There's no lock, transaction, or WAL in OPIC. OPIC just brings you the raw performance a hash table can gives you.

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

#29

Post by jsnell »

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 memory usage testing, and probably also has a major effect on the speed tests.

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

#30

Post by adrianN »

oconnor0 wrote: post #14
nom wrote: post #9

Earlier quoted context omitted.

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.

But that's what profiling is for.
Post reply on HN