Is Rust stack-efficient yet?
arewestackefficientyet.com
arewestackefficientyet.com
I was writing something in Rust and I wanted to create a new boxed object.
Box::new(...)
I don’t want to rely on compiler optimizations to make my code work. Or alternatively, find a way to deliver those optimizations in debug builds.
The idea of using a Vec would be nice—if only the boxed item were an array! It’s a struct, you see…
For example this is why there was a `box` operator in early rust.
And e.g. placement-in like APIs had been in the works for years, it's just that no satisfying and sound solution has been found (but multiple solutions which initially seems sound).
Which is why we currently are in a "hope the optimizer does the right thing" situations (through it is pretty much guaranteed to do the right thing for a lot of cases around Box).
But then it also isn't the highest priority as it turns out a log of "big" data structures (lists, maps, etc.) tend to grow on the heap anyway, the the situation that someone run into debug builds crashing because of a big data-structure is pretty rare, and it also crashing of release build is even rarer. Some of the most likeliest ways to have a too-big data-structure on the stack is: Having some very deep type nesting. But then such types are (in the rust ecosystem) often seen as an abuse of the type system and an anti-pattern anyway. Through it can be a fun puzzel, and some people are obsessed which bending the type system to their will to create DSLs or encode everything possible in the type system. But I have yet to see commercial projects with mixed skill level team members where using such libraries didn't lead to productivity reduction on the long run (independent of programming language).
Mixed skill team or not, I really don’t see why Box<[u8; 1024 * 1024]> should be something the language struggles with.
Vec<u8> has {usize length, usize capacity, void* data}. Box<[u8]> has {usize length, void* data}. Box<[u8;N]> has {void* data}.
(without trying to be too argumentative) right? Or?
Edit since I've been throttled:
For example it can make a difference between passing values per register or per
stack in some situations. … But then for some fields where C++ is currently very
prevalent it might matter all the time.
In some situations "optimizing smart pointers" to just be a single pointer size (Box<[T; N]>) instead of two pointer sizes (Box<[T]>) or instead of three pointer sizes (Vec<T>) can make a difference.
For example it can make a difference between passing values per register or per stack in some situations.
Or it could make the difference of how many instances of the boxed slice fit efficiently into the stack part of a smallvec. Which if it's the difference between the most common number fitting or not fitting can make a noticeable difference.
Through for a lot of fields of programming you likely won't opt. to do such optimizations as there are more important things to do/better things to spend time optimizing at. But then for some fields where C++ is currently very prevalent it might matter all the time.
vec![0u8; 1024*1024].into_boxed_slice().try_into().unwrap()
isn't that terrible to use
her as a function:
fn calloc_buffer<const N: usize>() -> Box<[u8; N]> {
vec![0u8; N].into_boxed_slice().try_into().unwrap()
I you want to rely a bit less on the optimizer using `reserve_exact()` + `resize()` can be a good choice. I guess it could be worthwhile to add a helper method to std.
Yes, you can give examples of cases where unusual code (like deep type nesting) can create these large data structures, and you can call it an anti-pattern. But Rust is also pitched as a C++ replacement for greenfield projects, so you have all of these C++ programmers who are used to being able to “new” something into existence of any size, and then initialize it. A series of design decisions in Rust has broken that for objects which don’t fit on the stack.
I’m satisfied with the explanation that “no satisfying and sound solution has been found” and I’m also satisfied with “Rust developers haven’t gotten around to addressing this issue”. I’m not really interested in hearing why some people who run into the same issue are making bad decisions.
In addition to inlining it also does also remove debug info.
It feels like a better way to do that directly with Box is Box::<MyType>::new_zeroed() which will make you a Box<MaybeUninit<MyType>> full of zero bytes. If MyType is definitely valid when made entirely of zero bytes and you're sure of that, you can unsafely assume_init() to have the MaybeUninit resolve to an actual MyType.
[[ If you lied, now everything is on fire, I did warn you that you need to be sure and it is an unsafe function ]]
If MyType is very much not valid if consisting entirely of zero bytes well, new_uninit() gives you memory in unspecified (must not be read) state, you can properly initialise it and then assume_init() as before - but all the extra work kinda sucks, and in either case clearly it would be nicer to just write what you meant and have it work.
Maybe that will work in the future—I don’t use nightly Rust, so for now, new_zeroed() won’t work. The basic problem is “I want to allocate something large on the heap” and it doesn’t seem like I should need to use nightly builds or unsafe{} to do it.
That's a completely fair observation. The main thing I want stabilised is a single niche for custom types. I would take more if offered but experience says that every extra little thing doubles the discussion time, so, one niche is all I need, and Rust guarantees this exists in some form so even if a later mechanism does - say - fancy non-contiguous niches, I just want one value ASAP.
https://github.com/rust-lang/rfcs/pull/3334
> “I want to allocate something large on the heap” and it doesn’t seem like I should need to use nightly builds or unsafe{} to do it.
The former makes sense to me, the latter (a requirement to use unsafe) I can see there can be cases where the compiler has to do a lot of contortions to safely but optimally mint the type in place in the heap and just writing the unsafe case is reasonable. I don't know anything about your type so I can't judge.
let heap_value = vec![the_struct];
Vectors of length 1 are still vectors :)
All the major C++ compilers support some variation on the idea of "Release with debug symbols". If you are using cmake or another meta build there are usually default set of options for this. If you are making your own build scripts then you might just add -d and -O2 to your Gcc of Clang flags.
The debug symbols will still consume space which will impact performance, but that is not likely to be a huge issue in all but the tightest performance regimes. And all the optimizations should be there.
Many optimizations are in practice unreliable—they are buried in the depths of a compiler and not part of the docs, it may be difficult to find out what conditions are necessary for the optimization to work, you may find that an optimization stops working when you update your compiler, you may find that changing a seemingly-unrelated piece of code breaks the optimization (maybe some function is no longer inlined for various reasons), or you may use a different compiler.
So I prefer to write code that works correctly without optimizations. It’s not a hard rule, but in this scenario, I would prefer to rewrite the code—and this happens to be annoying here.
This is bbeing fixed in clang I think at least. It will be treated as an intrinsic not as a function and I recall for forward something similar.
https://github.com/rust-lang/rust/issues/27779#issuecomment-...
https://www.reddit.com/r/rust/comments/xxhp3s/perhaps_not_a_...
r#box!(make_my_elem())
https://github.com/kvark/copyless
Box::alloc().init(make_my_elem())Maybe in another ten years the language will mature.
It seems crazy to you because your spectacular misdescription of the problem is simply incorrect.
If constructing the object doesn't have side effects, however, then we should be able to hoist the allocation at the optimizer level.
Don't do that, then? :)
LLVM can already do heap-to-stack, so people don't seem to feel too strongly that exactly preserving heap allocations is worth it. And what does that mean on multi-core, anyway?
https://github.com/nu11ptr/flexstr/blob/master/flexstr/src/b...
UPDATE: As I'm thinking about it, it is starting to come back to me a little:
1. I create the buffer
2. I do some op against it to fill it
3. I consume it and transform it into a final immutable flexstr
For #1, the 'new' function moves the buffer back to the caller (memcpy). Using it in #2 I think was fine as I think it is typically passed by mutable ref. For #3, the buffer was moved again (passed by `self`) so it could be consumed and reused without a language level copy (but was copying in the generated code). Replacing #1 and #3 with macros kept the stack buffer in the local stack frame and greatly sped up my code in benchmarks, and that is what those two macros do I linked to if I'm recalling correctly.
This seems to be mainly about measuring the change of stack efficiency of rust compared to a C++ base line.
Given who the author is I'm pretty sure they know that e.g. having more stack movement can be better then having more heap allocations.
But there is a list of ways you can reduce stack memory movement as compiler optimizations without allocating heap memory, and AFIK rust doesn't yet fully take advantage of many of them.
Additionally sometimes trading a lot of stack movements with a single allocation can be quite a bit faster, e.g. why anyhow does a thin-pointer + inlined vtable optimization.
So I think the side is mainly for tracking improvements in compiler code generation and secondary if rustc uses some thin-pointer optimizations in places where it does yield some benefits.
Trying to skip that first step, so the compiler just does unverified shit behind the scenes, I think will just end up with inflexibility and disappointment. Be the tortoise not the hare.
unsafe fn new_in_place(out: &mut MaybeUninit<MyType>)
For it to be safe to call the type system would have to encode the invariant that &out is initialised after the call. It becomes even more complicated if the operation can fail.
If one doesn't want to deal with imperative programming in all its glory, go write Haskell or something. (I do that too.)
For panicking, I think we would want to switch to a model where borrower not borowee runs destructor for &mut; that way we can support "moving out of &mut temporarily" too.
For an example I've seen myself: using a custom GC pointer library, calling `Gc::allocate(SomeBigStruct{...})` constructed the SomeBigStruct on stack and copied it around using memcpy 4 times before it actually landed in the allocated heap memory. The equivalent code compiled with a C++ compiler would have probably optimized the program enough to fill the struct in-place on heap without any issues.
(this example is from over a year ago; it's not as bad anymore, but it still generates suboptimal assembly with too much copying)
For my particular example: https://godbolt.org/z/8GvYzYj5h
You can see we're trying to put a 1kB object on heap, but the compiler generates two `memcpy` calls - first to copy it on stack to build the wrapper struct, second to actually copy the entire struct onto allocated memory.
In "real programs", you just need to look at the program's assembly. Or even more generally, I originally noticed this when observing the unusually high amount of time spent in some functions when profiling.
Also rustc code has been written in different times than the majority of clang code. That might as well affect the copying patterns. Move semantics is actually a quite modern thing in C++ (and not default like in Rust).
eh? Rust doesn't have placement-new or specify copy elision. nothing at all to do with backends or "code style".
In C++, copies are much more heavy, because they need to preserve the original, so copy elision matters a lot more. Also a developer is free to put arbitrarily complex stuff into a copy constructor. In Rust, those heavy copies are explicit so the developer can fully control when they happen.
Nevertheless - it could be all those reasons together. It's good someone is looking into it.
But it's very different. In Rust there are no move-constructors. A move is simply a memcpy. And the moved-from object doesn't have to be in "a valid, but unspecified state". You cannot use it, because the borrow checker prevents you from doing so. So it can actually be in any state, giving the compiler more room for optimization.
Shrinking the size of my library's Error struct seemed to help a lot - I wonder if it's because an error "E" smaller than the Result<T, E>'s "T" can be returned in-place, but a larger one needs a copy...?
Many of the post C# 7 features have been used to improve .NET performance in techpower benchmarks, and rewrite runtime code from C++ into C#.
I wonder if it might be simpler to track stack sizes statically instead of using runtime instrumentation. What I mean is, for example on x86_64, the function prologue has a stack reservation in the form of `sub rbp, 0x168`. So we can easily tell that the function uses 0x168 bytes of stack space. Just add those numbers up for every function in a crate, and you have a score. Track that number over time for a set of common crates.
It would also solve some practical problems mentioned in the page like the complexity of the setup and the speed of statistics gathering.
What's happening here is that C++ is the inheritor of decades of ponderous analysis about how code works with temporary results such that it can usually (.../often/sometimes/under-the-right-astrological-sign) optimize them away or arrange to have them magically appear in the right place. The return value optimization and all the move semantics nonsense is aimed at this space.
As a result, C++ tends to put things on the stack "where they want to go", where I guess Rust is a little naive and needs to build them in one place just to copy them where they need to be.
Yes, but optimizing compilers are decently good at using registers instead, which is unfortunately not true for less popular targets (which usually means anything other than amd64 and arm64). I think that's what GP was referring to.
>> Does this mean Rust is slower than C++?
> No. You can always write your Rust code carefully to avoid copies. Besides, all of this only comes out to a small percentage of the total instruction count. That being said, it's something we should fix, and which I'm working on.
People are acting like this graph they saw for the first time today means that Rust is running at sub-Ruby speeds, when even with these excess copies we already know, and have known for years how rust programs have been performing in real life.
That there is room for improvement here does not mean that the status quo was not already excellent.
Well, this is no different of how Rust people talk about C++ as if it was as unsafe as if you were writing inline assembly :)
Due to some mix of:
* Rust code relying more on copies than C++ (for esample, harder to make something uninitialized and fill it in)
* LLVM missing optimizations that rust relies on heavier than C++
* No real guarantees around RVO / NRVO
Rust code often will put something on the stack, and then just instantly copy it somewhere else on the stack, even in optimized code. I've observed this happening sometimes pretty blatantly myself.
Shouldn’t Rust in theory have a lot more freedom in defining its calling conventions than C++ has? I wonder if there’s anything that prevents doing RVO by default, or if just hadn’t been a priority yet.
Specifically, if `e` and `b(d)` are huge, you probably would want to evaluate `c(e)` first and then `b(d)`.
" a = A::new(...);
return a; "
Create a on the stack, and immediately copy a into the stack region the caller was expecting it in. This seemed to get worse as struct size got larger, so I'm guessing there was so much IL the optimizer had to churn through it just gave up at some point.
> Why do we care about stack memory moves?
> Memory moves to the stack frequently represent wasted computation. For the most part, they're CPU cycles that are spent shuffling data from one place to another instead of performing useful work. Stack-to-stack memory moves in particular are very likely to represent pure overhead; non-stack-to-stack memory moves are sometimes genuinely useful and necessary but frequently also represent waste.
It's essentially a critique that the optimizer is missing opportunities.
It's just rust being slightly less efficient: it spends instructions doing unnecessary stack-to-stack copies, and has larger stackframes (to hold the redundant copies, which can be an issue both with deep recursion and for inlining).
buf = malloc(size)
init(buf)
Rust's safe abstraction for initialization and heap allocation instead passes structs by value (you can't misuse a buffer pointer if it doesn't exist), and relies on the optimizer to remove all unnecessary copies. The optimizer doesn't always do that, which is what this site tries to measure and fix.