Designing a Fast Concurrent Hash Table
ibraheem.ca
ibraheem.ca
I have a strategy for benchmarking such data-structures, I call it the "birthday benchmark".
Unfortunately I'm not proficient enough in Rust to have put it into practice there, but the strategy is this:
Generate a stream of random bytes, pre-generation is advised to avoid dominating the benchmark.
Consume the stream in blocks of n bytes.
Try to find a duplicated block.
Given the "birthday paradox / birthday attack", this is actually much quicker than it might first appear. Simple single-thread basic hashset can find duplicates at a 6-byte length match in around 3 seconds on my hardware, and a specialised data-structure takes this to less than a second.
A good concurrent hashtable should improve that greatly even further, because this ought to be a very parallelizable problem, especially if you're not constrained to finding the first such duplicate in the stream, but allow yourself to find any duplicate, nor are constrained to keep track of both sides of the pair, and are content with simply knowing you have found one.
Current PRNGs are pretty fast. The Xoroshiro RNG "shootout" benchmark [0] lists some self-reported speeds. They claim 8+ GB/s for even their slowest, highest-quality PRNG. The general-purpose one they recommend is 10GB/s, and 32GB/s when vectorized.
The vectorized versions get close to current DRAM speeds. I think I'd prefer that over reading from a giant table, given that the table reads will have significant implications for caching and disrupt that aspect of the benchmark.
My domain is c#, where it's perhaps unsurprising that it's a lot faster to have an array in memory than go via the default Random, which is I believe is Xoroshiro ( at least in .net 6+ ). It certainly can generate data quickly with Random.GetBytes(), but repeated calls to Random.NextInt64() are much slower.
Another issue I found with generating random numbers and trying to multi-thread is thread safety / synchronisation. If each thread is doing it's own random generation then it's difficult to compare results between using 1 thread and 2 threads, because it's no longer the same single stream of random data measured across each benchmark, so the meta-randomness of how early you "should" hit a dupe becomes a factor.
Having pre-generated numbers and single thread responsible for handing out those numbers makes it easier, you can either have a thread-safe counter, or can increment a larger increment plus an offset for each thread number. The first "real" dupe is still in the same place in the original pre-generated data.
You can then compare the incremental gains, for example, of each thread having their own hashtable would get you logarithmic gains (I think that's the right way to express it, but essentially it's gaining just by having First Dupe = Min(First Dupe across N threads) vs an actual thread-safe concurrent hash-table, where you should[1] still see First dupe but sped up by a greater factor than just a naive work but not state sharing.
I recognise there are potential memory caching issues at play with the pregeneration approach, but for larger bit counts the actual work should hopefully dominate, particularly since look-up values aren't revisited by design.
[1] "Should", because there's a small chance in many algorithms that due to concurrency and race conditions you actually miss the duplicate. Either multiple runs should be tried looking for bi-modal data, or accept that the next dupe shouldn't be so long after the first, and be happy the speed-up is greater than the slow-down caused by very occassional race condition misses. The chance of a such a race condition is absolutely minuscule at the 48bit level, if we assume we are using say, 8 threads, and assume for a race condition to occur, the same 48-number would have to be concurrently being handled/generated by 2 different threads.
Most modern RNGs support a "jump" operation that takes care of this; PCG has the best standard API I've ever seen. Alternatively, with any RNG you can interleave (call `next` numthreads times before selecting a number) but that's slower.
Xoshiro I believe is in .NET 6, close cousin
https://blogs.siliconorchid.com/post/coding-inspiration/rand...
It's an interesting benchmark, but the kind of people who would want to use Papaya probably wouldn't be very interested in it.
https://lib.rs/crates/concurrent-map
I am using it for a transactional in-memory key-value store experiment.
> This is an ordered data structure, and supports very high throughput iteration over lexicographically sorted ranges of values. If you are looking for simple point operation performance, you may find a better option among one of the many concurrent hashmap implementations that are floating around. Pay for what you actually use :)
So just use a DBMS, but if you don't want, perhaps this ordered concurrent map.
You said you were using it for a "key-value store". If all you need is a key value lookup, all you need is a hash map.
When it comes to concurrency the difference is even more pronounced because hash maps can have lots of concurrent IO due to working on different parts of memory that are mostly independent of each other while a sorted data structure is going to have to move things around, which means more atomic swapping, which means more chances for collisions or race conditions where other threads are going to have to retry their compare and swaps or back off and try parts of their operation again.
I wonder whether it's possible to achieve similar performance but with a simpler design that uses scalable reader-writer locks. They can be made a lot more efficient than what's commonly out there using the C-SNZI lock-free data structure:
https://people.csail.mit.edu/mareko/spaa09-scalablerwlocks.p...
Can I reason about it in a concurrent scenario the same way I'd reason about it in a single-threaded scenario?
You can reason about its safety/ correctness the same way as the stdlib container types and this will be true for all of (safe) Rust.
The performance considerations have a new dimension for multi-threading though. In single threading you don't need to care whether doing similar operations "at the same time" could affect the performance of what you're doing, but in a concurrent system that's a consideration. Accordingly you would need to benchmark this carefully for your specific usage - just because it's correct doesn't mean it's fast or even acceptable.
For example: Count / size() can be imprecise in the realm of concurrency. No need to exactly count the HashTable.
It's impossible to get the size of this table exactly, because the shards are each at best one atomic and no shared lock exists between them. Adding up their individual counts (even if implemented as seq-cst atomics) is incorrect as an atomic is only globally correct within its own atomic operation. And there's no way to atomically gather all the shards sizes without a global lock.
Feature complete would similarly be: all the features you'd expect, except those annoying low performance ones.
I find the last bit particularly objectionable. If you're in some language slanging objects around all day, then sticking a untyped, bespoke substitute for an object probably isn't the right move. But on the long path down my programming career, I recognize objects make so many things harder and more confusing than necessary. I definitely prescribe to Rich Hickey saying I would rather have 1 data structure and 100 functions that operate on it far easier to work with and understand than 10 data structure and 10 functions. Clojure absolutely is a joy to work with and reason about, and it only gets better the faster you get out of typed object land. Hashmaps are the purest abstraction over an associative data structure, and I will take one over a pile of classes with brittle, snowflake interfaces any day.
That is exactly the opposite experience that I have, to the point I feel like it's from a different universe.
Perhaps difference in domain, but every time I have to use Python or JS I hate the lack of explicit types with defined interfaces as discoverability during coding is zero. And you end up with code that, after dependency updates or similar, you never know if it'll crash until you run it.
I agree type hints are a godsend for discoverability, but please, show me all operations this type can be a parameter for.
I want "discoverability" on the argument lists of all libraries.
and I find lsp with type hints useful for that.
and multi methods! can I have multiple dispatch? but first parameter based dispatch "oop" only? meh.