6 ms·

The Rust Performance Book (2020)

84 points by cwaffles 3y ago

cwaffles 3y ago
There's a good discussion on minimizing heap allocations: https://nnethercote.github.io/perf-book/heap-allocations.html https://nnethercote.github.io/perf-book/heap-allocations.htm...
- adam_arthur 3y ago
  How do people feel about large-ish arrays on the stack? e.g. 30k element array. I profiled something like this in Rust, and using a Vec on the heap was actually faster than the array on the stack. I'm sure there was some benchmarking issue/caching affecting the result, but I found it surprising following the (perhaps incorrect) intuition that stack local variables are faster than heap.
  - nu11ptr 3y ago
    I have done a bit of work with large arrays on the stack and in general this can be a problem area for Rust atm (or was a year ago when I looked into it). The reason is Rust uses a lot of move semantics, but under the covers I discovered many of these are not being optimized away and were actually mem copies. If you can keep your stack buffer in one spot and only pass refs to it I suspect you might be fine, but "moving" it is likely to incur a large performance penalty in some cases if not optimized away into a no-op. UPDATE: I should probably add that just about everything that is a move could turn into a copy, and Rust uses the move paradigm so often that is is easy to not even see what might turn into a copy. For small vars, it is no big deal, but for huge stack arrays it could add up. For example, if you init your buffer in a block and then return it as a binding, it will often be copied which can be painful. let my_buffer = { let buffer: [u8; 1_000_000] = [0; 1_000_000]; // Do stuff to init buffer here buffer // This might end up mem copying the buffer out of the block }; UPDATE 2: I had a very atypical use case for doing this. In general, I would agree large buffers should be put on the heap, but for my use case it made sense. To this day, I use a "large" (128K) buffer on the stack in my crate for performance reasons. I solved the above issues by using macros. My benchmarks are now solidly faster than heap allocation without the moves.
    - pkulak 3y ago
      Isn't this the entire reason you shouldn't use the stack for large amounts of data? Stacks unwind, so you can't pass around pointers to it. And the stack is fast because it's often mostly in CPU cache, but that won't be true if you have 100 megs sitting there. This is what the heap is for, it has nothing to do with Rust itself. (everything I said could be wrong, I'm not a compiler guy, I just didn't feel like qualifying every single statement)
      - jvanderbot 3y ago
        I agree to a point. There was a "stack is faster" sentiment taught in school which is obviously an oversimplification for actual working programs.
      - nu11ptr 3y ago
        > Isn't this the entire reason you shouldn't use the stack for large amounts of data No, the risk of stack overflow would be the typical reason > Stacks unwind, so you can't pass around pointers to it Sure you can, you just can't _return_ a reference to something on the stack, but within the data's lifetime you can pass refs to it to other functions > And the stack is fast because it's often mostly in CPU cache, but that won't be true if you have 100 megs sitting there The stack is also fast because allocation is free (pointer bump) vs. calling a free list allocator (aka malloc). Cache hits for a large buffer would likely be about the same. If the buffer were small, I would agree on the likelihood of it being in CPU cache. > This is what the heap is for, it has nothing to do with Rust itself. In many scenarios moves can and are optimized away, so yes, this has something to do with Rust. I will admit my use case was very contrived and is not a typical use case, but it was very valid (even if not typical).
    - gpderetta 3y ago
      So generally you have to copy arrays, you can't meaningfully move them (you can move each element of course). For vectors with heap allocated backing store of course you only need to copy the pointer to heap. For this particular example it seems that the rust compiler is failing to implement the equivalent of NRVO though, so it is not necessarily related to mives. Do rust semantics allow NRVO? There are no copy/move constructors with side effects, so the only issue is object identity. Disclaimer: I'm just a c++ programmer, I know very little about rust.
  - pdpi 3y ago
    The thing that makes the heap expensive is the allocator calls. If you allocate a big vector once and never resize it, there's not much of a cost.
  - addaon 3y ago
    If you're doing large stack allocations like this (or even if you're not, but care about correctness), you should be doing static analysis to prove absence of stack overflows. One of the main advantages of heap allocation over stack allocation is that failure is reliably detectable; with a large stack allocation, especially with sparse access patterns, you're well on the way to shipping broken code.
    - kibwen 3y ago
      One difficulty is that stack size is platform-dependent, so it's hard to prove that a stack won't overflow on every possible platform. At least with Rust, a stack overflow is a mandatory segfault at runtime (appears scary at first, but it's guaranteed not to wreak any havoc) on all major platforms, thanks to guard pages (which are present on every platform) and stack probes (which are supported in LLVM for major targets).
      - gpderetta 3y ago
        Is it a straight up sigsegv or a catchable panic? I guess having to deal with exceptions at every memory op would be too big a burden on the optimizer, but maybe the exception could be restricted to the function prologue.
        kibwen 3y ago
        It's not a panic and not recoverable in any way. I'm fuzzy on the details but AFAIK the specifics of LLVM means that it deliberately generates an illegal CPU instruction which manifests as a segfault.
      - addaon 3y ago
        Yeah, it's pretty rare to have a program that's correct regardless of the behavior (and defects) of the layers below it -- supporting multiple platforms of course involves performing your verification activities on all of them. As you hint at, guard probes without stack probes don't provide guaranteed segfaults -- sparse access to stack allocations can skip the guard and smash another stack (or whatever) easily enough. And stack probes for large sparse allocations firmly make stack allocations more expensive than heap allocations (since pages must be allocated for the whole allocation, even if it's unused), which is a pretty huge downside.
  - CyberDildonics 3y ago
    This is a terrible idea. There shouldn't be any advantage in speed because a single allocation is outweighed by the time it takes to deal with those 30,000 elements. It is a large risk for no pay off.
- deleted 3y ago
  [deleted]
kibwen 3y ago
Note that nnethercote is probably the world's foremost expert on Rust performance (in addition to being the maintainer of Valgrind). See also his long-running blog series where he discusses his efforts to improve the performance of the Rust compiler itself: https://nnethercote.github.io/2023/03/24/how-to-speed-up-the-rust-compiler-in-march-2023.html https://nnethercote.github.io/2023/03/24/how-to-speed-up-the...
asicsp 3y ago
Previous discussions: https://hn.algolia.com/?dateRange=all&page=0&prefix=false&query=https%3A%2F%2Fnnethercote.github.io%2Fperf-book%2F&sort=byPopularity&type=story https://hn.algolia.com/?dateRange=all&page=0&prefix=false&qu...
- dang 3y ago
  Yes, thanks! Reposts are fine after a year or so* but as there was a significant thread 9 months ago, the current repost counts as a dupe. The Rust Performance Book (2020) - https://news.ycombinator.com/item?id=32147999 https://news.ycombinator.com/item?id=32147999 - July 2022 (9 comments) Also: The Rust Performance Book - https://news.ycombinator.com/item?id=34877528 https://news.ycombinator.com/item?id=34877528 - Feb 2023 (1 comment) The Rust Performance Book - https://news.ycombinator.com/item?id=25122178 https://news.ycombinator.com/item?id=25122178 - Nov 2020 (19 comments) * This is in the FAQ: https://news.ycombinator.com/newsfaq.html https://news.ycombinator.com/newsfaq.html.
  - nindalf 3y ago
    The 9 comment thread looks pretty bare, unlike this one. What made it significant?
    - dang 3y ago
      It got 200 upvotes and was on HN's front page for 9 hours.
peoplearepeople 3y ago
Is there a printed version?
- xeonmc 3y ago
  https://nnethercote.github.io/perf-book/print.html https://nnethercote.github.io/perf-book/print.html
cmrdporcupine 3y ago
One thing I've been curious about -- but not enough to actually run through the disassembly yet -- is the performance of Rust matching on enums vs C/C++ switch statement -- in particular in e.g. a 'bytecode' interpreter loop. C compilers do a pretty good job of optimizing these into something pretty efficient, and I imagine it helps that the size of the case values is constant, and it can be turned by the compiler into either a jump table lookup or an unrolled jmp depending on size, etc. Rust enums, in contrast, can be variable sized at match time. And the elements can be nested a few levels deep. The obvious way to write an opcode execution loop in Rust -- a pattern match over an enum of opcodes -- I'm curious if this can be made to perform as well as in C/C++. (I've been writing a virtual machine interpreter loop and so have a modest interest in seeing how this kind of thing, though I'm not optimizing for performance yet, so) Don't see any explicit mention of this in this document.
- __s 3y ago
  1. C compilers don't do a good job, & thus even CPython, which has historically stuck to rather vanilla C, uses computed goto, as described in https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e... I resorted to similar techniques in optimizing Befunge: https://github.com/serprex/Befunge https://github.com/serprex/Befunge (See bejit.c & marsh.c/marsh.h) 2. Rust enums are not variable sized, think of them as tagged C unions, where the Rust compiler can sometimes apply tricks, for example making Option<Vec<T>> the same size as Vec<T> 3. match can specialize for straight forward cases, when in doubt use https://godbolt.org https://godbolt.org
  - cmrdporcupine 3y ago
    Neat (re: godbolt). But the output is super bloated for Rust -- even with no_std and the panic handler stubbed out. https://godbolt.org/z/nW79G1o71 https://godbolt.org/z/nW79G1o71 Also my old 6502 then 68000 brain never learned to read x86 assembly. :-) I find ARM/Aarch64 easier to grock. I might do this same test on the M1 Mac I have handy here, but fiddle with compiler until I can get an absolutely tiny binary and then compare to C. Some day.

84 points by cwaffles 3y ago

There's a good discussion on minimizing heap allocations: https://nnethercote.github.io/perf-book/heap-allocations.html https://nnethercote.github.io/perf-book/heap-allocations.htm...

adam_arthur 3y ago
How do people feel about large-ish arrays on the stack? e.g. 30k element array. I profiled something like this in Rust, and using a Vec on the heap was actually faster than the array on the stack. I'm sure there was some benchmarking issue/caching affecting the result, but I found it surprising following the (perhaps incorrect) intuition that stack local variables are faster than heap.
- nu11ptr 3y ago
  I have done a bit of work with large arrays on the stack and in general this can be a problem area for Rust atm (or was a year ago when I looked into it). The reason is Rust uses a lot of move semantics, but under the covers I discovered many of these are not being optimized away and were actually mem copies. If you can keep your stack buffer in one spot and only pass refs to it I suspect you might be fine, but "moving" it is likely to incur a large performance penalty in some cases if not optimized away into a no-op. UPDATE: I should probably add that just about everything that is a move could turn into a copy, and Rust uses the move paradigm so often that is is easy to not even see what might turn into a copy. For small vars, it is no big deal, but for huge stack arrays it could add up. For example, if you init your buffer in a block and then return it as a binding, it will often be copied which can be painful. let my_buffer = { let buffer: [u8; 1_000_000] = [0; 1_000_000]; // Do stuff to init buffer here buffer // This might end up mem copying the buffer out of the block }; UPDATE 2: I had a very atypical use case for doing this. In general, I would agree large buffers should be put on the heap, but for my use case it made sense. To this day, I use a "large" (128K) buffer on the stack in my crate for performance reasons. I solved the above issues by using macros. My benchmarks are now solidly faster than heap allocation without the moves.
  - pkulak 3y ago
    Isn't this the entire reason you shouldn't use the stack for large amounts of data? Stacks unwind, so you can't pass around pointers to it. And the stack is fast because it's often mostly in CPU cache, but that won't be true if you have 100 megs sitting there. This is what the heap is for, it has nothing to do with Rust itself. (everything I said could be wrong, I'm not a compiler guy, I just didn't feel like qualifying every single statement)
    - jvanderbot 3y ago
      I agree to a point. There was a "stack is faster" sentiment taught in school which is obviously an oversimplification for actual working programs.
    - nu11ptr 3y ago
      > Isn't this the entire reason you shouldn't use the stack for large amounts of data No, the risk of stack overflow would be the typical reason > Stacks unwind, so you can't pass around pointers to it Sure you can, you just can't _return_ a reference to something on the stack, but within the data's lifetime you can pass refs to it to other functions > And the stack is fast because it's often mostly in CPU cache, but that won't be true if you have 100 megs sitting there The stack is also fast because allocation is free (pointer bump) vs. calling a free list allocator (aka malloc). Cache hits for a large buffer would likely be about the same. If the buffer were small, I would agree on the likelihood of it being in CPU cache. > This is what the heap is for, it has nothing to do with Rust itself. In many scenarios moves can and are optimized away, so yes, this has something to do with Rust. I will admit my use case was very contrived and is not a typical use case, but it was very valid (even if not typical).
  - gpderetta 3y ago
    So generally you have to copy arrays, you can't meaningfully move them (you can move each element of course). For vectors with heap allocated backing store of course you only need to copy the pointer to heap. For this particular example it seems that the rust compiler is failing to implement the equivalent of NRVO though, so it is not necessarily related to mives. Do rust semantics allow NRVO? There are no copy/move constructors with side effects, so the only issue is object identity. Disclaimer: I'm just a c++ programmer, I know very little about rust.
- pdpi 3y ago
  The thing that makes the heap expensive is the allocator calls. If you allocate a big vector once and never resize it, there's not much of a cost.
- addaon 3y ago
  If you're doing large stack allocations like this (or even if you're not, but care about correctness), you should be doing static analysis to prove absence of stack overflows. One of the main advantages of heap allocation over stack allocation is that failure is reliably detectable; with a large stack allocation, especially with sparse access patterns, you're well on the way to shipping broken code.
  - kibwen 3y ago
    One difficulty is that stack size is platform-dependent, so it's hard to prove that a stack won't overflow on every possible platform. At least with Rust, a stack overflow is a mandatory segfault at runtime (appears scary at first, but it's guaranteed not to wreak any havoc) on all major platforms, thanks to guard pages (which are present on every platform) and stack probes (which are supported in LLVM for major targets).
    - gpderetta 3y ago
      Is it a straight up sigsegv or a catchable panic? I guess having to deal with exceptions at every memory op would be too big a burden on the optimizer, but maybe the exception could be restricted to the function prologue.
      - kibwen 3y ago
        It's not a panic and not recoverable in any way. I'm fuzzy on the details but AFAIK the specifics of LLVM means that it deliberately generates an illegal CPU instruction which manifests as a segfault.
    - addaon 3y ago
      Yeah, it's pretty rare to have a program that's correct regardless of the behavior (and defects) of the layers below it -- supporting multiple platforms of course involves performing your verification activities on all of them. As you hint at, guard probes without stack probes don't provide guaranteed segfaults -- sparse access to stack allocations can skip the guard and smash another stack (or whatever) easily enough. And stack probes for large sparse allocations firmly make stack allocations more expensive than heap allocations (since pages must be allocated for the whole allocation, even if it's unused), which is a pretty huge downside.
- CyberDildonics 3y ago
  This is a terrible idea. There shouldn't be any advantage in speed because a single allocation is outweighed by the time it takes to deal with those 30,000 elements. It is a large risk for no pay off.
deleted 3y ago
[deleted]

kibwen 3y ago

Note that nnethercote is probably the world's foremost expert on Rust performance (in addition to being the maintainer of Valgrind). See also his long-running blog series where he discusses his efforts to improve the performance of the Rust compiler itself: https://nnethercote.github.io/2023/03/24/how-to-speed-up-the-rust-compiler-in-march-2023.html https://nnethercote.github.io/2023/03/24/how-to-speed-up-the...

asicsp 3y ago

Previous discussions: https://hn.algolia.com/?dateRange=all&page=0&prefix=false&query=https%3A%2F%2Fnnethercote.github.io%2Fperf-book%2F&sort=byPopularity&type=story https://hn.algolia.com/?dateRange=all&page=0&prefix=false&qu...

dang 3y ago
Yes, thanks! Reposts are fine after a year or so* but as there was a significant thread 9 months ago, the current repost counts as a dupe. The Rust Performance Book (2020) - https://news.ycombinator.com/item?id=32147999 https://news.ycombinator.com/item?id=32147999 - July 2022 (9 comments) Also: The Rust Performance Book - https://news.ycombinator.com/item?id=34877528 https://news.ycombinator.com/item?id=34877528 - Feb 2023 (1 comment) The Rust Performance Book - https://news.ycombinator.com/item?id=25122178 https://news.ycombinator.com/item?id=25122178 - Nov 2020 (19 comments) * This is in the FAQ: https://news.ycombinator.com/newsfaq.html https://news.ycombinator.com/newsfaq.html.
- nindalf 3y ago
  The 9 comment thread looks pretty bare, unlike this one. What made it significant?
  - dang 3y ago
    It got 200 upvotes and was on HN's front page for 9 hours.

peoplearepeople 3y ago

Is there a printed version?

xeonmc 3y ago
https://nnethercote.github.io/perf-book/print.html https://nnethercote.github.io/perf-book/print.html

cmrdporcupine 3y ago

One thing I've been curious about -- but not enough to actually run through the disassembly yet -- is the performance of Rust matching on enums vs C/C++ switch statement -- in particular in e.g. a 'bytecode' interpreter loop. C compilers do a pretty good job of optimizing these into something pretty efficient, and I imagine it helps that the size of the case values is constant, and it can be turned by the compiler into either a jump table lookup or an unrolled jmp depending on size, etc. Rust enums, in contrast, can be variable sized at match time. And the elements can be nested a few levels deep. The obvious way to write an opcode execution loop in Rust -- a pattern match over an enum of opcodes -- I'm curious if this can be made to perform as well as in C/C++. (I've been writing a virtual machine interpreter loop and so have a modest interest in seeing how this kind of thing, though I'm not optimizing for performance yet, so) Don't see any explicit mention of this in this document.

__s 3y ago
1. C compilers don't do a good job, & thus even CPython, which has historically stuck to rather vanilla C, uses computed goto, as described in https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e... I resorted to similar techniques in optimizing Befunge: https://github.com/serprex/Befunge https://github.com/serprex/Befunge (See bejit.c & marsh.c/marsh.h) 2. Rust enums are not variable sized, think of them as tagged C unions, where the Rust compiler can sometimes apply tricks, for example making Option<Vec<T>> the same size as Vec<T> 3. match can specialize for straight forward cases, when in doubt use https://godbolt.org https://godbolt.org
- cmrdporcupine 3y ago
  Neat (re: godbolt). But the output is super bloated for Rust -- even with no_std and the panic handler stubbed out. https://godbolt.org/z/nW79G1o71 https://godbolt.org/z/nW79G1o71 Also my old 6502 then 68000 brain never learned to read x86 assembly. :-) I find ARM/Aarch64 easier to grock. I might do this same test on the M1 Mac I have handy here, but fiddle with compiler until I can get an absolutely tiny binary and then compare to C. Some day.