Performance degradation for high numbers of threads in Rust

Question

I'm creating a latch-free concurrent HashMap in Rust. The throughput curve looks as I would expect up to around 16 threads, at which point performance beings to drop.

Throughput (MOps/sec) vs. Num threads

I used a Google Cloud instance with 48 vCPUs and 200GB RAM. I tried enabling/disabling hyperthreading but it had no noticeable result.

Here's how I'm spawning the threads:

for i in 0..num_threads {
    //clone the shared data structure
    let ht = Arc::clone(&ht);

    let handle = thread::spawn(move || {
        for j in 0..adds_per_thread {
            //randomly generate and add a (key, value)
            let key = thread_rng().gen::<u32>();
            let value = thread_rng().gen::<u32>();
            ht.set_item(key, value);
        }
    });

    handles.push(handle);
}

for handle in handles {
    handle.join().unwrap();
}

I'm out of ideas; is my Rust code correct for multithreading?

"latch-free"? I think you mean lock-free, unless you have a specific technical meaning in mind that I'm not aware of. Anyway, if all your threads spend all their time hammering on your lock-free data structure, yes you'll get contention once you have enough threads that PRNG time isn't a factor, and maybe start hitting more CAS retries and stuff like that. This is not the normal use-case for lock-free data structures; usually your code does significant work *other* than hammering on these. — Peter Cordes, Dec 14 '19 at 19:38
*is my Rust code correct for multithreading* — yes, it starts multiple threads and doesn't generate memory unsafety, so it seems **correct**. If this were a an answer instead of a comment, would you accept it? If not, please consider reviewing your post and see if you are asking the question you want to and if you've provided enough information in the post for it to be answered. — Shepmaster, Dec 14 '19 at 19:39
I don't see code for your hashmap so perf analysis of its design isn't possible. Unless this is a standard library implementation? I don't know Rust well at all, maybe I'm missing something in your code that shows which HashMap you're using. — Peter Cordes, Dec 14 '19 at 19:41
@PeterCordes no, Rust does not offer a lock-free implementation in the standard library. OP also states "I'm creating", which I take to mean that they are writing the code from scratch. The code does really provide any useful information; it's not even clear how the threads are being spawned as no imports are shown. — Shepmaster, Dec 14 '19 at 19:44
@PeterCordes thanks, I think that is the answer I was looking for. I am doing this as part of a research project, so right now my benchmarks are a bit contrived. I can edit to include the actual data structure itself but it is basically a Rust port of a C++ implementation that is well-studied. — Jack Truskowski, Dec 14 '19 at 19:57
(I made a couple edits just as you accepted the answer. I think it's more correct now.) — Peter Cordes, Dec 14 '19 at 20:24

Peter Cordes · Accepted Answer · 2019-12-14T20:23:40.893

If all your threads spend all their time hammering on your lock-free data structure, yes you'll get contention once you have enough threads. With enough writers they'll contend for the same cache line in the table more often. (Also, possibly time spent in the PRNG doesn't hide contention for shared bandwidth to cache or DRAM).

Instead of just a plateau, you'll maybe start hitting more CAS retries and stuff like that, including any contention backoff mechanism. Also, threads will suffer cache misses and even memory-order mis-speculation pipeline clears from some atomic reads; not everything will be atomic RMWs or writes.

This is not the normal use-case for lock-free data structures; usually you use them with code that does significant work other than hammering on them, so actual contention is low. Also, real workloads for a hashmap are rarely write-only (although that can happen if you just want to deduplicate something).

Read scales very well with number of readers, but write will hit contention.

Performance degradation for high numbers of threads in Rust

1 Answers1