Junction HashMaps: Lessons to be learned?

[lilianmoraru]

There is no gitter set-up so I decided to open an issue.

Jeff Preshing(people might know him from his blog Preshing on Programming or his CppCon presentation) has announced a new lock-free concurrent HashMap library called Junction.
His benchmarks indicate that it outperforms the other C++ concurrent HashMaps.

Are there lesson to be learned from it?
Crossbeam doesn't yet have a HashMap implementation, so I wanted to post to provide some inspiration.

[oblitum]

I also had learned about that and also got curious about this :-)

[aturon]

FWIW, my current plan is to start with a simple skiplist-based map, to focus first on the end-user API (which, in Rust, is not as straightforward as you might think). But in the long run, Rust needs a very high-perf hashmap, and I'd love to draw from the state of the art here!

[schets]

I'm interested in how this does with many concurrent modifying threads. I'll run some of the benchmarks and look at the source later, but typically concurrent hashmaps suffer badly during the resize phase. Some more detailed benchmarking will reveal how the read/write performance scales individually - if the read performance is good, which I expect, leapfrog or grandpa would be well suited to a read-focused map. If write performance scales well I would be pleasantly surprised, but looking at the posted benchmark it's less than linear for a mix of read/writes so either something isn't scaling or he's using hyperthreads. Also, these use QBSR for a performance boost, something which doesn't really belong in a general purpose api.

The leapfrog table also appears exceptional for a single writer scenario. I think having a single-writer map api as well as a general one would be really great since the performance is so much higher for both for reads and writes and it's a common scenario.

As a side note on possible map datastructures, hash tries scale very well with multiple writers (almost linearly with real cores!), and I believe have wait-free reads, but suffer from lower read throughput and worse write throughput with few writers.

All in all, I don't think that Rust should just have one high-performance map. There should be a standard ConcurrentMap that has good read/write scalability and no performance surprises, but also a few different options like read-focused, single writer, or consistent latency for example.

[schets]

I've been reading through the source for the leapfrog table - it looks like it would be really good for a reader-oriented table. The modification I would make is that readers won't assist in a table migration - this will make the writers/migration slower for the writers, but will allow the reads to be wait-free and O(1).

I'll look into the grandpa and leapfrog table write-heavy performance when I get home, but I have some doubts about how well they will scale and the latency properties. This ctrie paper shows Cliff Click's nonblocking hash table having good mixed performance in a read-heavy scenario, but awful raw insert performance. I expect these tables to follow a similar pattern since they use a similar resize mechanism.

[schets]

I've got some benchmarks running -

Here's the ops/second plot with a 4:1 read:write ratio (the same ratio shown in the announcement),

a 1:1 read:write ratio:

and an 16:1 read:write ratio

Looks like my suspicions were more/less accurate - although I will say this is way better than many concurrent hash tables which have absolutely disastrous many-writer performance.

I expect the read performance to get even better when read operations can't get roped into the resize phase, although they are pretty good as is for the 16:1 case - hopefully that will improve things for the other cases as well and get controllable read latencies, albeit further worsening write performance.

For a reader-oriented hashtable or a single-writer table, that seems like a great tradeoff.

[alexandermerritt]

You may want to take a look at libcuckoo https://github.com/efficient/libcuckoo (EuroSys'14 paper) which is a concurrent hash table. It seems to be quite scalable -- multiple concurrent readers and writers. It does suffer during resizing, however, as the entire table must be locked, a new table allocated, and all items moved.

There are also many studies on concurrent data structures from recent conferences, e.g. Asynchronized Concurrency (ASPLOS'15) which has implementations of hash tables, lists, trees and one of their earlier papers on synchronization mechanisms -- Everything you Always Wanted to Know About Synchronization (SOSP'13).

I'm very interested in learning about such structures in Rust (maybe even building).

Let's close this in favor of crossbeam-rs/rfcs#32.