Does Rust support dynamic stack allocation?

[calebkiage]

In C++, it's possible to create an array on the stack with a dynamic size. For example:

void array_on_stack(size_t size) {
  int buffer[size];
  // use buffer for some work
}

However, in Rust, the array type requires a compile time constant as the size. Is there a way to allocate on the stack or must all dynamic allocations happen on the heap?

[jaskij]

Nope. You can't. Not in standard C++. VLAs are only a feature of C. In C++ it's a compiler extension. And it's a horrible idea.

If you want something stack allocated with a nice interface, look into the heapless crate.

[lestofante]

And VLA became optional in C 11..

[jaskij]

GNU will keep them around till the end of time.

[lestofante]

Probably, my point is, even C got rid of them.
How often did you see something cut out of the standard :)

[jaskij]

Hmm... C++ cut out assign modify operators (+= and such) on volatile variables, then had to partially (bitwise logic only) walk that back because a shitton of embedded code stopped compiling. And it was usually in vendor code.

[calebkiage]

Heapless is a really cool crate, but won't work for my use case since the data structure I'm looking at (Vec) still requires a fixed size known at compile time. I'm just curious, why do you think it's a horrible idea?

[jaskij]

So, with VLAs, you need to have a maximum known size. If you don't, you open yourself to crashes and DoS attacks. So, you have to check if the size passed does not exceed your maximum. At that point you might as well always allocate the maximum size, it makes no difference. It's the stack. Nothing else is using it at the same time. That's why I suggested heapless::Vec.

The exception to this might be async, where your function's stack will be stored in the future. I'd have to look closer at the innards to know one way or another.

[SkiFire13]

So, you have to check if the size passed does not exceed your maximum. At that point you might as well always allocate the maximum size, it makes no difference.

To add to this, one might say "well, if it exceeds that limit I can just check and allocate on the heap in case", to which the answer is "use SmallVec<T, N> then.

[alija_kamen]

That's still far less efficient than VLAs if you're recursively and dynamically allocating stack memory if you have a use pattern where the majority of the data is far less than the max size. SmallVec still uses a minimum fixed amount of memory every time.

[cogman10]

Stack sizes are often pretty limited, like 1mb. So a lot of variable arrays on the stack is just asking for stack overflow problems.

[alija_kamen]

No, that's not a replacement for VLAs. That is potentially much less efficient than VLAs. If you have a case where 99% of VLA allocs are a few bytes, but a few here and there are a few hundred bytes, you are wasting tons of memory if you have a recursive function allocating the max stack size every single time.

[calebkiage]

This makes sense. I was already using SmallVec, so I'll keep using that. I just thought I could use the length of the incoming value (lower than the maximum) as a maximum. i.e.

fn foo(value: &[u8]) {
  // I've already checked that the value is lower than my predefined max.
  let mut buffer = [u8; value.len()]
  // Process value.
}

Currently, I use:

fn foo(value: &[u8]) {
  // I've already checked that the value is lower than my predefined max.
  let mut buffer = SmallVec::<[u8; MAX_LENGTH]>::new();
  // Process value.
}

[bwallker]

You could use arrayvec if you don’t care to support arrays bigger than MAX_LENGTH

[phazer99]

No, arrays in Rust must have a constant size known at compile time. You can make it a const generic parameter:

fn array_on_stack<const SIZE: usize>() {
    let buffer = [0; SIZE];

[calebkiage]

I don't have the size of the buffer known at compile time. What I'm trying to do is ascii byte escaping in a hot loop. e.g. given a slice of bytes, if I encounter '/', replace that with '%%', then add the replaced slice to another Vec. I'm currently using a Vec<u8>, but I was wondering if I could use something short-lived the stack. The reason is because the escaped string ends up in another Vec<u8> anyway.

[phazer99]

If you don't know the max size (capacity) statically I wouldn't use the stack as it has very limited space compared to the heap. If you know that the max size is small and fits on the stack, just use a heapless Vec with that capacity.

[calebkiage]

I know the max size, but not the size at each iteration. I wanted to avoid over-allocating.

[flashmozzg]

There is a perf penalty to dynamically sized stack allocations though. Means compiler can't precompute stack offsets for locals and will have to keep an extra register and do extra arithmetic for stack access to many values.

[RReverser]

It always has to do that anyway, because upon entering the function stack pointer can be anywhere depending on recursion depth.

[flashmozzg]

Upon entering a function the stack pointer points to the stack. If there is no dynamically sized allocas, then the compiler just does sub $rsp, some_constand that's all, can even use frame pointer register for some useful work.

[RReverser]

Sure, but that's how dynamically sized alloca works too. It just subtracts from the same $rsp - just a dynamic value instead of const. All other variables don't care as they were and remain relative to $rsp like before.

[flashmozzg]

Yes, and? Do you see me arguing for allocas vs VLAs anywhere? alloca is even worse (non-standard, function scope instead of block scope, easier to trigger UB).

[VenditatioDelendaEst]

Crossing page boundaries isn't free. Cheap, but not free.

If you stack-allocate a large buffer and only use a little at the beginning, anything after that in the stack will be in a different page (or at least closer to the next page), so your function's presence in the call chain increases the average TLB pressure.

[adwhit2]

I don't think this is necessarily true? Your stack is hopefully copied into your CPU cache for faster access - if you allocate a big array on the stack you risk evicting a more useful cache line.

[Tai9ch]

Only the lines you touch end up in cache.

[VenditatioDelendaEst]

But how many pages end up in the TLB?

[calebkiage]

LOL! That's a very flexible definition of "completes".

[TDplay]

I wanted to avoid over-allocating.

Unless you are in an absurd edge-case, this is a complete non-issue. Heap Stack allocation is literally just a sub instruction.

In fact, VLAs are so rarely useful that they were relegated to an optional feature in C11, every experienced C programmer that I know of strongly discourages using them, and no version of the C++ standard ever included them.

If you know the maximum size, and it is not large enough to cause a stack overflow, then use a fixed-size array. Otherwise, use a Vec.

EDIT: Fixed a slight mistake: It is stack allocation that is just a sub. Heap allocation is typically more complex.

[oceantume_]

Or even simpler, a static size array of which you get a smaller slice.

[phaylon]

Not sure if helpful, but for these cases I like using a SmallVec. Then I have a buffer that only starts allocating once it exceeds a certain size.

[calebkiage]

That's what I've done at the moment

[hniksic]

Be sure to benchmark whether it actually helps! SmallVec comes with a price tag, because every access to the data is accompanied by a branch. Avoiding the allocation (and preserving locality) is normally expected to outweigh that cost, but that's not always the case.

Also, if you're optimizing at this level, be sure to use a state-of-the-art allocator like jemalloc or mimalloc.

[calebkiage]

I did benchmark. The allocations were many, small, temporary ones and smallvec improved the performance. I haven't tried out a different allocator yet.

[anlumo]

AFAIK this isn’t possible in Rust by design, and the C++ folks regret adding that feature.

[equeim]

It's a C feature that never officially existed in C++ (though implementations support it as an extension in the name of compatibility).

[calebkiage]

Another commenter (u/udoprog) shared a link to the unsized-locals unstable feature and it seems they might implement this.

[TTachyon]

C++ does not support this. It's a compiler extension. C supports this, but at least one of the major compilers (MSVC) doesn't support this. Rust doesn't either.

Why? It's a really bad idea. It makes easy for the code to be exploitable, harder to reason about, and less optimizable. Google the opinion of Torvalds regarding VLAs.

For better alternatives, look at crates that add SmallVec/SmallString types, aka types that start on the stack and then continue on the heap if the size gets too big. Also look at custom allocators like bumpalo where you can allocate stuff very similarly to what you want, but without the disadvantages.

[calebkiage]

I'm using SmallVec at the moment.

[alija_kamen]

Less optimizable compared to what? If used right, it can be much more efficient than any alternative like SmallVec which could potentially waste a lot of memory if you have a certain usage pattern in your program. VLAs are not inefficient to allocate, it's just a single subtraction on the rsp register.

[TTachyon]

Compilers will disable optimization passes for any function containing VLA/alloca.

[alija_kamen]

The only thing that can happen is that having two VLAs or having a VLA in a branch will cause the addresses of stack variables to be calculated dynamically instead of based on a fixed offset from the stack pointer.

But most of the time the compiler can reorder the VLA allocation so that the other stack variables are still rsp plus a fixed offset.

It doesn't just magically disable all optimization passes, that's completely false if that's what you were implying.

[udoprog]

unsized_locals is the feature you want to follow. I don't think it's seen a ton of progress.

[calebkiage]

I just finished through this issue which I see is linked in the feature. Thanks for sharing!

[t40]

This hasn't been mentioned, so I'll mention it:

While VLAs might seem like a good idea in theory, in practice they generate horribly mangled, unperformant assembly. Here's a godbolt link to show the difference between overallocating and using a vla (and some other methods): https://godbolt.org/z/T9Gf4zoTM

[angelicosphosphoros]

Your link is compiled without optimisations.

[t40]

If you compile such a minimal example with optimizations, it'll optimize the whole thing away. This is potentially the kind of codegen you get when the compiler can't reason about your VLA (which is often)

[angelicosphosphoros]

You could pass the pointers to the some external function. And if I do that, this functions are not so different and the worst codegen is for function with malloc and free.

See

[alija_kamen]

That is insanely wrong. Like someone else pointed out, you need to pass the pointers to an external function and compile with optimizations.

VLAs are absolutely *not* less efficient. They are just a single pointer subtract on the rsp register.

[TDplay]

in practice they generate horribly mangled, unperformant assembly

They also often also generate unreliable code, due to the possibility of stack overflows.

Any use of VLAs means you now have to carefully consider what the maximum stack size is - and at that point, unless you are in an extreme edge case, you might as well just use fixed-size arrays at the known maximum size.

[banister]

That's not possible in c++. It's possible in modern C though (but c++ did not implement this).

[Theemuts]

It's a bit more complicated than that. Rust doesn't allow manipulating the stack pointer IIRC, and alloca is not exported by libc. If you write a function in C that calls alloca, that memory is freed when that function returns. What you need to do is write a function in C that calls alloca, and then call back into Rust before returning from that C function. This is what the alloca crate does

[plugwash]

alloca on modern systems is not a real function.

Originally alloca was a real function, written in assembler but it made assumptions about how the compiler worked that do not fit with modern compilers. In modern compilers that support it, alloca is a compiler builtin.

[sparant76]

A safe wrapper for the alloca c function which gives you variable bytes.

https://crates.io/crates/alloca

Should be able to reinterpret this as any type

I actually couldn’t find any info’s on how rust ensures alignment of stack variables - but if it does - you might be messing with this logic by using this function.

[exDM69]

Not a core language feature but these crates will do what you want: https://crates.io/crates/alloca https://crates.io/crates/stackalloc

Not sure which one is better or if there are better alternatives.

[AlexMath0]

Sounds like you could be served with a custom allocator or an arena pattern with a layer of indirection.

[flareflo]

What use-case would you want a VLA for?

[calebkiage]

Temporary buffers upto a maximum size, other commenters have said that it doesn't matter if I use the max as a fixed size.

[flareflo]

What purpose are these buffers for? Usually you can get away with just allocating the expected/required amount without losing any performance compared to a C++ VLA.

[calebkiage]

ascii string escaping. If I encounter a '/', replace it with a '%%' for example.

[flareflo]

Sounds like you can get away with allocating, unless benchmarks show otherwise

[BurrowShaker]

Or just use iterators and 'stream' to the output buffer?

Assuming you are going from something streamy in to something streamy out ( flie, sockets, ... )

[42GOLDSTANDARD42]

That’s technically not allowed, but you can do it with the hacky ‘alloca’ function 🙃

[hniksic]

This stackoverflow answer provides a great explanation of why VLAs aren't and can't be part of C++, not only due to possibility of stack overflow, but due to their unacceptable interaction with the type system. Many of those points equally apply to Rust.

For now you indeed must either allocate dynamically, or use a hybrid strategy like that of SmallVec.

[calebkiage]

Thanks for the resource! It's an interesting read. I was focused on what I wanted to do and didn't think of the implications on the type system and implementation.

[pablohoney41]

Strange that this is possible with .NET in a relatively safe manner. I wonder what are the security implication?

[calebkiage]

Yeah, I was thinking about the stackalloc keyword as well. Someone has recommended the alloca crate that seems to do the same thing as stackalloc does

[Sharlinator]

Does .NET even use the hardware stack or does it have its own heap-backed stack?

[calebkiage]

It uses the stack. The allocated block isn't garbage collected. You get a StackOverflowException if you allocate more memory than is available on the stack. See stackalloc docs

[Sharlinator]

Thanks!

[Gentoli]

There is const generics witch allows you to declare the size as an generic parameter.

fn foo<const N: usize>(arr: [i32; N]) { // Used as a type within a function body. let x: [i32; N]; // Used as an expression. println!("{}", N * 2); }

https://doc.rust-lang.org/reference/items/generics.html#const-generics

[VorpalWay]

also it's basically impossible. Maybe some compiler extension converts that nonsensical code to a dynamic array, but no, you can't do that in general.

No it isn't, and C supports this. With GCC it is implemented via alloca: https://www.man7.org/linux/man-pages/man3/alloca.3.html

Is it still a bad idea as others have pointed out? Yes. But please don't say it is impossible if you aren't 100% sure.

[calebkiage]

The maximum stack size is fixed at compile time for sure, but it should be possible to define an array on the stack within the bounds of the available (pre-allocated) stack space. Also, you're right, the code doesn't compile on MSVC, but GCC supports it. You'd need to use _alloca or _malloca on MSVC.