5 ms·

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

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]

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]