Are we stack-efficient yet?

Q&A

What is this?

This is a set of graphs that shows the fraction of stack memory move CPU instructions in a sample of Rust code and C++ code. Lower numbers are better.

What's a stack memory move?

A stack memory move is a pair of instructions that loads a value from memory and stores it to the CPU stack. A stack-to-stack memory move loads a value from the stack and stores it to the stack. An non-stack-to-stack memory move loads a value from some place other than the stack and stores it to the stack.

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.

How did you perform these measurements?

Using this branch of LLVM. You can reproduce them for yourself by building this branch of LLVM, linking Clang and/or rustc against the resulting library, and building code with LLVM_STACK_COPY_STATS=1. CSV data will be dumped to stderr for you to aggregate as you like.

What workloads were tested?

The C++ code in question is LLVM and Clang. The Rust code in question is rustc. I chose these two because they were similar workloads by dint of being compilers. The CPU architecture is x86-64.

What versions of the compilers did you use?

Trunk Clang and nightly rustc as of the given date, both linking against trunk LLVM.

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.

Can we add optimizations so that Rust can do better in the future?

Absolutely, and this page serves to track that progress.

How often is this page updated?

Manually, when I land changes that I think will improve things. Very few people are working in this area, so I don't think CI would be worth it right now.

Are there any caveats to these numbers?

Yes:

• I stopped measuring around 20 million instructions, because the statistics gathering is very slow and it would take forever to measure all of LLVM and Clang. I don't think measuring more than 20M instructions would be likely to produce much of a change in the overall numbers.
• I'm not measuring memcpy or memmove calls yet, only loads and stores.
• The way flow sensitivity is handled is to consider multiple live-in registers to a basic block as "coming from the stack" if any of them come from the stack. This may result in overestimating the true number of stack-to-stack copies in some cases.
• I only count the number of stores, not the number of load-store pairs. Arguably this means the true number of wasted instructions could be as much as twice the fractions listed here.