March 12, 2024
It occurred to me some time ago, after publishing the previous article on key value stores, that I was using chaining hash tables, and I really ought to be using open addressing.
Well I didn’t know really what open addressing was, before exploring myself, and it’s a bit of a shame. Previously, I thought chaining made the fastest hash tables possible (obviously), and textbooks mentioned open addressing as an alternative if you didn’t wan to chain. Turns out for allocation reasons, open addressing is far faster, although you lose pointer stability.
I went ahead and implemented a few different open addressed tables (thanks to Max Slater’s article), and the results are pretty interesting - on uint64_t keys, the open addressed table is around 4x faster, and on 30 char string keys, they’re around 2x faster overall. That means in accordance to my previous article, I’d be hitting around 6 million operations on a single thread. Not bad!
For multithreading, we have similar results. It’s more difficult to do fancy things like Robinhood Hashing, or backshifts when we have multiple threads, but we can still do simple linear/quadratic probing nonetheless. I went ahead and did this, but because atomic operations are so unforgivingly slow (or I implemented them wrong), the performance wasn’t much better, par with 6 cores, 5x slower with 1 core (not even good scaling). Perhaps more scaling would help, since I’m limited to ~6 performance cores on an M2 max.
Raw Data - I’m pretty sure clear is lazy on all my tables (using page tables). Times are in ns, erase does 10000 operations, while N is 1000000. The table size is also 1000000. Mixed mean 50% are missing, 50% present, random gives a random order and we’ll have more cache misses. Code can be found on the github.
(the raw data is supposed to be here but it seems pollen does not play well with markdown tables, so it is ommitted. email me if you really want the numbers, important ones are uint64 chaining = 43ns, uint64 open = 9ns, random ver gives 48ns, 20ns, respectively.)