5 ms·
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 com
by 1932812267 2y ago
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)?
- pclmulqdq 2y agoAtomics 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.
- 1932812267 2y agoSure! 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/423e46fe204718785af99a2d68a52092463d0167/crossbeam-deque/src/deque.rs#L444-L481 https://github.com/crossbeam-rs/crossbeam/blob/423e46fe20471...
- pclmulqdq 2y agoRun 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.
- 1932812267 2y agoI'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&edition=2024&gist=b9a84b823c023f13f65b4e23ddf38e3b 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)
- pclmulqdq 2y agoAh, 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.
- zozbot234 2y ago> 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.
- pclmulqdq 2y agoI 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.
- janwas 2y agoYep, 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?
- jandrewrogers 2y agoFWIW, work stealing can be pretty expensive. It is only efficient under a narrow set of assumptions about the workload.