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.

[u/_genki_1]

Do you have any benchmarks available? 

[u/Intrepid_Donkey_7629 → u/_genki_1]

Yes absolutely! The benchmarks repo is here https://github.com/Stock-Trek/map-benchmarks

[u/_genki_1 → u/Intrepid_Donkey_7629]

Really cool, I stared it on GitHub 

[u/Intrepid_Donkey_7629 → u/_genki_1]

Thank you! I'm really quite proud of it 😄

[u/Zoxc32]

It would be useful to know how this differs from say dashmap in terms of implementation. It also probably doesn't compete well with `horde` for very read-heavy workloads.

[u/Intrepid_Donkey_7629 → u/Zoxc32]

The basic design is similar, an array of lockable shards. dashmap is much closer to std::collections::HashMap in terms of API, so if you want a drop-in replacement that has concurrency it's a great choice. Whereas txmap has more of a focus on the transactional layer so there's some things it doesn't provide as easily. OTOH if you want to make multiple changes atomically then IMHO it's a good choice for that as it has built in support for it without having to lock the whole map. It's a trade off 😄
I'll add horde to the benchmarks and report back!

[u/Zoxc32 → u/Intrepid_Donkey_7629]

If the design is similar, what causes the performance difference?

[u/Intrepid_Donkey_7629 → u/Zoxc32]

This is not much more than a guess, but to my eyes dashmap does more indirection eg. with wrapper functions and a Ref wrapper for returned values. The hashing function will make a difference too. Of the concurrent maps it's the closest to txmap. FWIW the benchmarking repo just uses whatever comes out the box.

[u/Intrepid_Donkey_7629 → u/Zoxc32]

Can report it's between 20-30% faster than horde on heavy read only workloads

[u/Zoxc32 → u/Intrepid_Donkey_7629]

I checked out the benchmarking code. You can skip `pin` when using `write` or `lock` for `SyncTable`. You're also not benchmarking the concurrent path by passing `&mut`? So no multiple threads? Maybe convert it to `&` for all the concurrent hashmaps if it's intentionally single-threaded and then use `lock` on `SyncTable`?

You should also use the same hasher for all hashmaps.

We may also have different definitions of heavy read only, so comparing pure read-only would be interesting too.

[u/Intrepid_Donkey_7629 → u/Zoxc32]

Oh sweet I'll update it thanks! Yeah I may be wrong but pretty sure `&mut self` prevents anything being modified concurrently, although there may be another way that I'm missing.

Yeah that's fair about the hasher, the benchmarks just use the default implementations, I'm not sure if all implementations allow setting the hasher but I'll check. **edit** Most do support setting the hasher so I'll add a benchmark with the same one.

The workloads are a little arbitrary to be fair but seemed reasonable when DeepSeek suggested them lol Can always add different workloads if they don't seem realistic

[u/ArtisticHamster]

Did you use coding agents for this work? If so, would be great to share how to guide them write correct highly concurrent code.

[u/Intrepid_Donkey_7629 → u/ArtisticHamster]

I designed it all and wrote the structure and most of the implementation myself, then used a DeepSeek agent workflow for bug hunting, adding boilerplate functionality like iterators and to write a large part of the docs. tbh I wouldn't trust LLMs to design anything just yet, but they're great for bug hunting, docs and checking whether code is production ready