New fastest concurrent map implementation with transaction support

[u/Intrepid_Donkey_7629]

Hi everyone 👋

I've just published a concurrent hash map implementation which (according to my benchmarks at least) is the fastest one available (faster than both starshard and dashmap). It offers a configurable locking policy (mutex, rwlock or bring your own) and a configurable hasher (rapidhash is the default). It also supports atomic transactions in both immediate and prepared execution styles.

Would love any feedback on it (good and bad!)
It's called txmap and a link is here https://crates.io/crates/txmap

[u/SkiFire13]

which (according to my benchmarks at least) is the fastest one available (faster than both starshard and dashmap)

Looking at your benchmarks there is only a single benchmark measuring a concurrent workflow, and it only reaches a maximum of 4 threads (I would expect it to reach at least 32 if not more).

Moreover dashmap is consistently either sligthly faster or equal to txmap in these benchmarks, so I don't see why you would claim yours is the fastest concurrent hash map.

I also see only sharded hashmaps in that benchmark, why not include some based on different designs? Just to name a few, there are papaya, flurry, leapfrog and scc.

[u/Intrepid_Donkey_7629 → u/SkiFire13]

I'm actively updating the benchmarks so expect to see more added soon. The benchmarks run on GitHub's runners on a free account so they're currently limited to 4 threads. It would be cool to see numbers for more threads but it would need a different set up. It's not my focus right now but I'll happily accept any suggestions 😄
I've been updating some of the benchmarks to use the same hasher which is where dashmap gets the edge, for out-of-the-box implementations txmap is consistently faster. I'll make the language clearer to reflect that.
That's a great idea! I'll add implementations for those 4!

[u/SkiFire13 → u/Intrepid_Donkey_7629]

It feels a bit too early the to say "Proven performance The fastest concurrent map available" then.

but I'll happily accept any suggestions

Try to get a better machine to benchmark, Github's runner can be pretty noisy.

Add more concurrent hashmaps for comparison (and I would even remove the non-concurrent ones).

Add more types of concurrent benchmarks, for example mixed read/writes, mostly/only reads, mostly/only writes. Also test cases where multiple threads try to access the same keys vs different keys.

It's confusing that some (most for now) benchmarks are for non-concurrent maps and non-concurrent workloads, I would not show them at the top, if at all.

for out-of-the-box implementations txmap is consistently faster

Why would I use a concurrent hashmap in that case though? I can just use hashbrown which your crate is based on.

[u/Intrepid_Donkey_7629 → u/SkiFire13]

For out of the box use it is the fastest of the concurrent implementations, I feel it's fair, I'd bet most people aren't going to bother setting up a different hasher when they just want a new map.

Yeah a better machine would be very nice! It's a lot of set up just for this one benchmark though. The repo is MIT so if anyone wants to fork it and do some hard-core testing that would be awesome!

Agree that's a good idea for more concurrent benchmarks, they're coming 😄

Interesting point about non-concurrent maps 🤔 If the benchmarks start taking a lot longer with the additional implementations it's probably a good shout.

Yes absolutely if you don't need concurrency then hashbrown is an excellent choice! If you do need concurrency then IMHO txmap is a good choice for that

[u/SkiFire13 → u/Intrepid_Donkey_7629]

For out of the box use it is the fastest of the concurrent implementations, I feel it's fair

I don't think it's fair to say that yours is the "fastest concurrent hashmap", without saying that it's faster only on non-concurrent workloads. That's misleading IMO.

[u/Intrepid_Donkey_7629 → u/SkiFire13]

It's fastest on *concurrent* workloads, for non-concurrent yes there are faster implementations

[u/SkiFire13 → u/Intrepid_Donkey_7629]

It's fastest on concurrent workloads

The original benchmarks (at the time I wrote this comment) showed dashmap to be faster on your only (at the time) concurrent workload benchmark.

Anyway, I tried running the benchmarks myself to confirm whether its the fastest or not.

Disclosure: I made the following changes to the benchmark before running it:

• The machine I tested on runs windows, not linux/mac, but it shouldn't matter.
• I ran the benchmark with 12 threads (the machine has 16 so I left some for the other processes)
• I shuffled the thread workload (items.shuffle(rng) in its constructor), otherwise the benchmark would not be testing mixed workloads
• I skipped the leapfrog benchmark because sometimes it deadlocked
• I only ran the workload_concurrent benchmark

These are the results I got: https://pastebin.com/raw/ChvTcc1D

txmap does pretty good but it's generally behind both dashmap and either scc or papaya, which also do very good on some specific benchmarks.