While it's true that par_iter() uses a concurrent data structure under the hood, it's specifically designed to use work-stealing to avoid needing threads to communicate.

Why would putting a lock over a global workqueue be faster than per-thread workqueues that don't require inter-thread communication (except in the case where work-stealing is required)?

Atomics are very expensive operations. Lock/unlock is two atomics. Many concurrent data structures will end up doing many more atomic operations than you expect.

The general wins of concurrent data structures come when you really are accessing them truly concurrently - as in when many threads on many cores are heavily contending for access and you need to make global progress.

Sure! However, the work-stealing queue in rayon [1] uses three atomic operations instead of the two atomic operations for a mutex for a global lock. The difference, however, is the three atomic operations for the thread-local queue should be uncontended, whereas a global lock on a global work queue would experience contention from every thread trying to access it for jobs.

Between the choices of "single work sharing queue with a big mutex on it that all threads access for work" vs "per-thread work-stealing queue that's uncontended for the cost of one extra atomic," in what situations would the work-sharing queue with the global mutex outperform? Perhaps if there's a small number of jobs, and there's not enough time for the work-stealing algorithm to distribute jobs to the worker threads before the work-sharing algorithm has already finished.

[1]: https://github.com/crossbeam-rs/crossbeam/blob/423e46fe20471...

Run a benchmark. With low contention, the lock will outperform. Atomics are very expensive assembly instructions.

Fedor Pikus has a good talk on this at cppcon 2019.

I've seen the talk! The issue with using a global lock on a global work queue is that, unless the work items have drastically different compute times, there _will_ be high contention on the lock.

I ran a benchmark [1], which shows that this is correct:

Results on quad-core Intel Linux box:

$ hyperfine target/release/testit 'env USE_RAYON=1 target/release/testit' Benchmark 1: target/release/testit Time (mean ± σ): 2.526 s ± 0.139 s [User: 4.709 s, System: 11.425 s] Range (min … max): 2.391 s … 2.730 s 10 runs

Benchmark 2: env USE_RAYON=1 target/release/testit Time (mean ± σ): 174.1 ms ± 0.9 ms [User: 212.1 ms, System: 121.1 ms] Range (min … max): 173.1 ms … 175.4 ms 16 runs

Summary env USE_RAYON=1 target/release/testit ran 14.51 ± 0.80 times faster than target/release/testit

Results on M1 Pro:

$ hyperfine target/release/testit 'env USE_RAYON=1 target/release/testit' Benchmark 1: target/release/testit Time (mean ± σ): 692.2 ms ± 8.3 ms [User: 491.4 ms, System: 5693.6 ms] Range (min … max): 683.2 ms … 704.5 ms 10 runs

Benchmark 2: env USE_RAYON=1 target/release/testit Time (mean ± σ): 63.0 ms ± 2.1 ms [User: 97.7 ms, System: 47.0 ms] Range (min … max): 61.0 ms … 71.2 ms 44 runs

Summary env USE_RAYON=1 target/release/testit ran 10.99 ± 0.39 times faster than target/release/testit

[1]: https://play.rust-lang.org/?version=stable&mode=debug&editio... (I'm just using the rust playground as a pastebin; the actual benchmarks were run locally)

Ah, yes. It's good that you ran a benchmark. However, if I read the code correctly, your version with a lock does an extra memcopy. When the work function is as short as AES encoding of a block of memory, that memcopy is quite a big cost and the queue is going to be quite heavily contended.

> Atomics are very expensive operations.

Atomics are very expensive when contended - which is also the case where locks would introduce blocking and reduced performance. Uncontended atomics are relatively cheap.

I suggest you run a microbenchmark. Uncontended atomics are some of the most expensive assembly instructions out there. They also acquire global system locks on certain stages of execution.

Yep, including draining the store buffer.

We've gotten our ThreadPool barrier+wait to use only acq/rel, but not yet the work stealing. Does anyone have experience with that already?

FWIW, work stealing can be pretty expensive. It is only efficient under a narrow set of assumptions about the workload.