6 ms·

Making a parallel Rust workload 10x faster with (or without) Rayon

123 points by lukastyrychtr 2y ago

jvanderbot 2y ago
I've seen this over and over. One of the main issues pointed out by TFA is that there's too many small tasks allocated for parallel execution. Rayon is not going to magically distribute your work perfectly, though it very often does a decent job. If your algorithm is the equivalent of a couple of nested iterations, you have essentially three options: parallelize outer, inner, or both. In the vast majority of the cases I've run into, you want thread/task level parallelism on the outer loop (only), and if required, data/simd parallelism on the inner loop(s). It's a rule of thumb, but it biases towards batches of work assigned to CPUs for a decent amount of time, allowing cache locality and pipelining to kick in. That's even before SIMD.
- cogman10 2y ago
  The rule of thumb also keeps you from doing a lot of task switching. It isn't free enqueue and dequeue tasks. It is better if you have a million things to do to have a smaller set of tasks. Especially if the runtime for those tasks are somewhat uniform.
  - mcronce 2y ago
    For sure. Context switching tasks is certainly a lot cheaper than context switching threads, but it isn't free.
- dboreham 2y ago
  Larger grain size better.
- menaerus 2y ago
  > One of the main issues pointed out by TFA is that there's too many small tasks allocated for parallel execution Valid concern but I don't think this was the OP case though? From my understanding, author gained the most benefits by dumbing down the generic rayon implementation to the same kind (thread-pool with task queues) but with different work-stealing algorithm. > Rayon is not going to magically distribute your work perfectly, though it very often does a decent job. Work-stealing by definition kinda makes distributing the work "correctly" a difficult task, doesn't it?
  - jvanderbot 2y ago
    Well, sure, in practice work stealing makes correct distribution difficult, but in theory, work stealing is to repair an incorrect work distribution, right? If every CPU is 100% utilized without needing context switch (and running the right number of worker threads without switching those), then work stealing is not required. But my comment is solidly "Rule of thumb". I claim no theoretical basis other than "Giving fewer longer tasks to fewer threads, (still >= number of worker threads), is better than giving more shorter ones"
ModernMech 2y ago
Per the article's "Using the right profiling tools", I have gone through a similar profiling journey in Rust and found this tool very useful: https://superluminal.eu/rust/ https://superluminal.eu/rust/ Works on Windows, has a great GUI, shows pretty flame charts, really pleasant to use. Costs money but worth it.
- yazzku 2y ago
  Superluminal is a sampling profiler for the most part. It works great for what it does, sure. But in the author's own words: > So far, we’ve only used perf to record stack traces at a regular time interval. This is useful, but only scratching the surface. For cache hits and other counters, you're gonna have to go deeper than just sampling.
  - datadeft 2y ago
    How would you go about cache hits instead of using a sampling profiler? Would you use eBPF / BCC?
    - freeone3000 2y ago
      The article describes using strace and perf in the paragraph after.
- datadeft 2y ago
  > Superluminal is the new industry-standard profiling tool. Never heard of it and I do a lot of performance related work. Is Superluminal really that popular?
  - ModernMech 2y ago
    I don't think it's popular but it really worked great for me!
- mgoetzke 2y ago
  Sadly only for windows though
ciupicri 2y ago
I don't understand why is he running it under Docker when one of the touted benefits of Rust is that all you need to do is just copy & run the binary on the destination machine.
- duped 2y ago
  > one of the touted benefits of Rust is that all you need to do is just copy & run the binary on the destination machine is it? I've heard that about Go, not so much Rust. cargo doesn't statically link system dependencies by default, only other rust dependencies.
  - 01HNNWZ0MV43FF 2y ago
    Go statically links C deps? Like gtk?
    - password4321 2y ago
      I think the point is Go doesn't have C deps by default like Rust does.
      - m0shen 2y ago
        I thought it depended on libc by default?
        mirashii 2y ago
        You might find https://mt165.co.uk/blog/static-link-go/ https://mt165.co.uk/blog/static-link-go/ useful, but a quick tl;dr: Go binaries are statically linked by default if they do not call out to any C functions. Go will automatically switch to dynamic linking if you need to call out to C functions. There are some parts of the standard library that do this internally, and so many folks assume that go is dynamically linked by default.
      - jeroenhd 2y ago
xnorswap 2y ago
I'm confused by the before / after graph, this is how I'm reading the graphs: The "before" graph shows a ~300ms wall-clock time which drops to ~150ms parallelised. The "after" graph shows a ~27ms wall-clock time which drops to ~17ms when parallelised. Isn't all the improvement still outside of the parallelisation then? There's an awful lot of discussion about parallelisation and the behaviour of schedulers given there wasn't any improvement of how parallelisable the end result was?
- meheleventyone 2y ago
  The reported benefit of using the custom threading implementation over rayon was 20% according to the article. So not nothing but not the biggest win. If they were able to rejig the algorithm so they could parralelize the outer loop there's probably a bigger win to be had.
imtringued 2y ago
I think this article jumped the gun by abandoning Rayon too quickly.

123 points by lukastyrychtr 2y ago

I've seen this over and over. One of the main issues pointed out by TFA is that there's too many small tasks allocated for parallel execution. Rayon is not going to magically distribute your work perfectly, though it very often does a decent job. If your algorithm is the equivalent of a couple of nested iterations, you have essentially three options: parallelize outer, inner, or both. In the vast majority of the cases I've run into, you want thread/task level parallelism on the outer loop (only), and if required, data/simd parallelism on the inner loop(s). It's a rule of thumb, but it biases towards batches of work assigned to CPUs for a decent amount of time, allowing cache locality and pipelining to kick in. That's even before SIMD.

cogman10 2y ago
The rule of thumb also keeps you from doing a lot of task switching. It isn't free enqueue and dequeue tasks. It is better if you have a million things to do to have a smaller set of tasks. Especially if the runtime for those tasks are somewhat uniform.
- mcronce 2y ago
  For sure. Context switching tasks is certainly a lot cheaper than context switching threads, but it isn't free.
dboreham 2y ago
Larger grain size better.
menaerus 2y ago
> One of the main issues pointed out by TFA is that there's too many small tasks allocated for parallel execution Valid concern but I don't think this was the OP case though? From my understanding, author gained the most benefits by dumbing down the generic rayon implementation to the same kind (thread-pool with task queues) but with different work-stealing algorithm. > Rayon is not going to magically distribute your work perfectly, though it very often does a decent job. Work-stealing by definition kinda makes distributing the work "correctly" a difficult task, doesn't it?
- jvanderbot 2y ago
  Well, sure, in practice work stealing makes correct distribution difficult, but in theory, work stealing is to repair an incorrect work distribution, right? If every CPU is 100% utilized without needing context switch (and running the right number of worker threads without switching those), then work stealing is not required. But my comment is solidly "Rule of thumb". I claim no theoretical basis other than "Giving fewer longer tasks to fewer threads, (still >= number of worker threads), is better than giving more shorter ones"

ModernMech 2y ago

Per the article's "Using the right profiling tools", I have gone through a similar profiling journey in Rust and found this tool very useful: https://superluminal.eu/rust/ https://superluminal.eu/rust/ Works on Windows, has a great GUI, shows pretty flame charts, really pleasant to use. Costs money but worth it.

yazzku 2y ago
Superluminal is a sampling profiler for the most part. It works great for what it does, sure. But in the author's own words: > So far, we’ve only used perf to record stack traces at a regular time interval. This is useful, but only scratching the surface. For cache hits and other counters, you're gonna have to go deeper than just sampling.
- datadeft 2y ago
  How would you go about cache hits instead of using a sampling profiler? Would you use eBPF / BCC?
  - freeone3000 2y ago
    The article describes using strace and perf in the paragraph after.
datadeft 2y ago
> Superluminal is the new industry-standard profiling tool. Never heard of it and I do a lot of performance related work. Is Superluminal really that popular?
- ModernMech 2y ago
  I don't think it's popular but it really worked great for me!
mgoetzke 2y ago
Sadly only for windows though

ciupicri 2y ago

I don't understand why is he running it under Docker when one of the touted benefits of Rust is that all you need to do is just copy & run the binary on the destination machine.

duped 2y ago
> one of the touted benefits of Rust is that all you need to do is just copy & run the binary on the destination machine is it? I've heard that about Go, not so much Rust. cargo doesn't statically link system dependencies by default, only other rust dependencies.
- 01HNNWZ0MV43FF 2y ago
  Go statically links C deps? Like gtk?
  - password4321 2y ago
    I think the point is Go doesn't have C deps by default like Rust does.
    - m0shen 2y ago
      I thought it depended on libc by default?
      - mirashii 2y ago
        You might find https://mt165.co.uk/blog/static-link-go/ https://mt165.co.uk/blog/static-link-go/ useful, but a quick tl;dr: Go binaries are statically linked by default if they do not call out to any C functions. Go will automatically switch to dynamic linking if you need to call out to C functions. There are some parts of the standard library that do this internally, and so many folks assume that go is dynamically linked by default.
    - jeroenhd 2y ago

xnorswap 2y ago

I'm confused by the before / after graph, this is how I'm reading the graphs: The "before" graph shows a ~300ms wall-clock time which drops to ~150ms parallelised. The "after" graph shows a ~27ms wall-clock time which drops to ~17ms when parallelised. Isn't all the improvement still outside of the parallelisation then? There's an awful lot of discussion about parallelisation and the behaviour of schedulers given there wasn't any improvement of how parallelisable the end result was?

meheleventyone 2y ago
The reported benefit of using the custom threading implementation over rayon was 20% according to the article. So not nothing but not the biggest win. If they were able to rejig the algorithm so they could parralelize the outer loop there's probably a bigger win to be had.

imtringued 2y ago

I think this article jumped the gun by abandoning Rayon too quickly.