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.
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.
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)
> 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).
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.
NRVO is a completely transparent optimization that Rust tries to do whenever possible. I don’t know what sort of case you can get into with object identity but I suspect it’s obviated by making moved-out-of values untouchable at compile time.
using array = std::array<int, 10>;
array make(array* y) {
array result = {...};
assert(&result != y);
return result;
}
array x = make(&x);
Normally in C++ distinct objects (result and x) have distinct addresses, so the assert would be guaranteed not to fire. But NRVO is explicitly allowed in the standard to violate this guarantee, so result can overlap with x. In rust you likely cannot get the address of the not-yet-constructed x, but it might be possible to construct equivalent examples.
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.
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).
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.
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.
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.
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.
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...
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.
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
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.
Your link there is compiling in debug mode, using opt-level=0 (the default), which is why it produces 1800 lines of output. If you do opt-level=3 (which corresponds to `cargo build --release`), it becomes 300 lines of output:
28 comments
[ 3.0 ms ] story [ 62.5 ms ] threadUPDATE: 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.
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.(everything I said could be wrong, I'm not a compiler guy, I just didn't feel like qualifying every single statement)
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).
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.
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.
The Rust Performance Book (2020) - https://news.ycombinator.com/item?id=32147999 - July 2022 (9 comments)
Also:
The Rust Performance Book - https://news.ycombinator.com/item?id=34877528 - Feb 2023 (1 comment)
The Rust Performance Book - https://news.ycombinator.com/item?id=25122178 - Nov 2020 (19 comments)
* This is in the FAQ: https://news.ycombinator.com/newsfaq.html.
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.
I resorted to similar techniques in optimizing 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/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.
https://godbolt.org/z/aYKMne5Wq