5 ms·
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 differe
by 1932812267 1y ago
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/423e46fe204718785af99a2d68a52092463d0167/crossbeam-deque/src/deque.rs#L444-L481 https://github.com/crossbeam-rs/crossbeam/blob/423e46fe20471...
- pclmulqdq 1y 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 1y 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 1y 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.