25 ms·
Is Rust stack-efficient yet?
- goodpoint 4y ago
- PaulHoule 4y agoThat's why I like AVR8 assembly better than C for Arduino. You have this big register file and the one C wants to use the most is the stack pointer.
- ajross 4y agoThat's not the optimization in question here, though. C uses the stack pointer a lot if you use a lot of stack-local variables. Mark all your stuff "static" and it will use immediate addresses instead (which may or may not help you -- putting all the "local" stuff in a block referenced by one pointer is usually a good thing!). 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.
- unsafecast 4y ago> C uses the stack pointer a lot if you use a lot of stack-local variables. Mark all your stuff "static" and it will use immediate addresses instead 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.
- ape4 4y agoHonest question - does this mean Rust isn't ready for production yet?
- msbarnett 4y agoNo. TFA points out there isn’t a gigantic performance sink or anything, just an infelicity in the code they’re generating. >> 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.
- tialaramex 4y agoAs pointed out elsewhere in this comment tree, things living on the stack when they needn't can mean they don't fit and thus the program doesn't work, so the optimisation can matter for that reason, and this is a particular reason to worry about it for larger objects where the optimiser is more likely not to see what's going on.
- msbarnett 4y agoAnd yet, real world production rust programs exist and measured performance is generally excellent. 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.
- germandiago 4y ago> People are acting like this graph they saw for the first time today means that Rust is running at sub-Ruby speeds 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 :)
- 4y ago
- klodolph 4y agoThis affects the way you write code, too. I was writing something in Rust and I wanted to create a new boxed object. Box::new(...) Boom! Program crashes. The object I’m putting in the heap is too large for the stack. Rustc does this by instantiating the object on the stack, and then copying it to the box. I don’t really want to fuss with nightly or stuff like Box::new_uninit just to deal with this. C++ has both regular `new` and placement `new`, both of which put objects in memory which is already allocated. I had assumed that the Rust compiler could optimize out a move, since that’s such a prominent feature in C++ compilers.
- sitkack 4y agoBox::new allocating on the stack and moving is only true in debug builds, in release builds it directly allocates on the heap. Not apologizing, just explaining. It is being fixed, the interim solution is to use a Vec.
- klodolph 4y agoThere’s a broader problem here, which also applies to the C++ ecosystem, which is that debug builds are far less usable than they should be. C++ compilers in common debug configurations will emit a function call for std::move(), which is not in any way useful for typical debugging tasks and can make the program significantly slower. 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…
- codeflo 4y agoHaving been bitten by that exact problem in C++, I think the original sin is to treat stuff like copy elision as a mere optimization, instead of a semantic guarantee.
- klodolph 4y agoThe C++ committee recognized this problem. As of C++17, copy elision is mandatory. Several forms of it, at least.
- Ericson2314 4y agoWe need &out and &in, so we can safely write this stuff by hand. Then we can worry about the compiler automatically optimizing to use &out behind the scenes (using ABI flexibility). 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.
- wmanley 4y agoEasier said than done. You can already have: unsafe fn new_in_place(out: &mut MaybeUninit<MyType>) But you require unsafe code both to implement it (to project MaybeUninit) and to call it. 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.
- Ericson2314 4y agoYes, you do. This is the cost of doing business. I'm OK with it. If one doesn't want to deal with imperative programming in all its glory, go write Haskell or something. (I do that too.)
- Ericson2314 4y agoAs a stepping stone. we could worry just about the panic=abort case, where this is all easier. 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.
- fb03 4y agoI'd appreciate if the graphs showed a larger span instead of every 4 hours and at most from a day ago (showing a flat line). It'd be very cool to see it spanning from months so that we could get a sense of the tendency of the line
- ChadNauseam 4y agoOP mentioned on reddit that he’s planning on updating the graph with new data as he makes improvements
- infogulch 4y agoNote that the author mentions they will update the page manually, not through CI.
- deleted 4y ago[deleted]
- dathinab 4y agoFor easy to miss context: 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.
- mywittyname 4y agoBut why are these operations slow in Rust?
- ravi-delia 4y agoThey are precisely the same speed in every language, seeing as they're going to be the same instructions. The linked site points out that Rust does more of them.
- pornel 4y agoSafe Rust prevents access to uninitialised memory, so a pattern like: buf = malloc(size) init(buf) is too risky, because init could read the uninitialized memory or fail to overwrite all of it causing a heartbleed-like leak elsewhere (most programmers may think it's just garbage bytes who cares — Rust cares.) 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.
- MrBuddyCasino 4y agoApparently not: ERR_CONNECTION_TIMED_OUT
- je_bailey 4y agoI don’t understand the point of this. Is there a trade off in being stack efficient and speed?
- masklinn 4y ago> Is there a trade off in being stack efficient and speed? 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).
- vgatherps 4y agoThe main goal is removing replacing pointless stack-to-stack copies with simply mutating in-place on the stack correctly in the first place. 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.
- codeflo 4y ago> No real guarantees around RVO / NRVO 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.
- vgatherps 4y agoI think in theory it could, but something was definitely getting clogged in the optimizer. I'd see code like " 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.
- pkolaczk 4y agoIt would be more informative if the stack metrics were paired with heap metrics. You can trivially avoid stack to stack copies by allocating on the heap and passing pointers / references. But that is often actually slower, because heap allocation is more costly than copying data within the stack.
- adrian17 4y agoThis is not about a heap-vs-stack tradeoff, this is about the compiler routinely generating very inefficient code that copies data around on stack for no good reason. 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)
- CapmCrackaWaka 4y agoIf you don't mind me asking - how do you witness these low level memory allocations? Specific program, plugin to vs code?
- spacechild1 4y agoYou look at the generated assembly.
- adrian17 4y agoThe simplest way to make quick experiments for me is with https://godbolt.org/ https://godbolt.org/ . For my particular example: https://godbolt.org/z/8GvYzYj5h 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.
- deleted 4y ago[deleted]
- throwup 4y agoI've run into frustrating stack overflows in seemingly trivial non-recursive code, so I appreciate this effort! 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.
- bjourne 4y agoThis won't work since you also need to track the maximum number of stack frames (e.g recursive calls) which is undecidable.
- Murfalo 4y agoIt's not clear to me how this would track stack<->stack and memory<->stack copies. Can you explain?
- throwup 4y agoMy suggestion would not measure the copies themselves, but it would count how many bytes are the source/destination of copies (of course incl. other things like parameters/etc). It's not the exact same metric, but it does still help answer the question in the title. I would expect the two numbers to be highly correlated when building the same binary with different versions of the compiler. It would also solve some practical problems mentioned in the page like the complexity of the setup and the speed of statistics gathering.
- toxik 4y agoIf you copy between stack regions, you need more stack memory, so the stack allocation should be larger. Of course, this would undercount cases that copy to the same region many times which seems likely.
- the_mitsuhiko 4y agoI like tracking this or at least having a way to track this. It's incredibly common that you only discover a crash too late in production due to running out of stack size and at least knowing a histogram over some test runs about how close something went to the (configured) limit would already be incredibly helpful for service stability.
- yawgmoth 4y agoI would love to see this for C#. Avoiding heap allocations was something I had to tackle as part of a simulation software. C# has a handful of GC generations, and GC gen1 is very fast, but it's still faster to pool things ahead of time.
- lynzrand 4y agoYou can access C#'s GC metrics through `System.GC.GetTotalAllocatedBytes` and similar APIs. Maybe you can make a benchmark and tracker for it yourself!
- insanitybit 4y agoThis isn't related to heap allocations. It's about removing the cost of a stack variable being moved into another stack variable.
- yawgmoth 4y agoI became interested in stack performance specifically because I had to avoid heap allocations.
- insanitybit 4y agoI mean, it's tangentially related, sure. It's also related to ML because computers run ML algorithms and computers run programs with stacks.
- deleted 4y ago[deleted]
- yawgmoth 4y agoWhile I want to understand your point and welcome enlightenment, so far this conversation has just been kinda weirdly hostile.
- pjmlp 4y agoUsing structs, stack allocations (safe since C# 7.x) and native heap go a long way. 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#.
- nu11ptr 4y agoI noticed in one of my crates that Rust often cannot optimize "moves" away. I was in the unusual situation where I had to move around a very large stack buffer(typically in Rust they live on the heap). Instead of passing it back and forth between moving functions as I originally designed, I had to redesign it to use macros which significantly improved my benchmarks. Further attention to optimizations here would be very welcome.
- redanddead 4y agoHow did you implement those macros?
- nu11ptr 4y agoTbh it was like a year ago and I forget the specifics. You are welcome to look at the code, however: https://github.com/nu11ptr/flexstr/blob/master/flexstr/src/builder.rs#L194 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.
- kibwen 4y agoPrior discussion with the author on Reddit: https://www.reddit.com/r/rust/comments/yw57mj/are_we_stack_efficient_yet/ https://www.reddit.com/r/rust/comments/yw57mj/are_we_stack_e...
- mkj 4y agoThis looks like a good metric to track. Looking at some generated asm when I was optimising a no_std program for size, I was surprised how much stack shuffling was going on. Also iirc it had runs of load/store where it seemed like a loop might be better. 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...?