How to speed up the Rust compiler in 2020

https://blog.mozilla.org/nnethercote/2020/04/24/how-to-speed-up-the-rust-compiler-in-2020/

by est31 • 6 years ago

247 115 6 years ago

blog.mozilla.org

ChrisSD2• 6 years ago

...giving incremental compilation speed-ups of up to 13% across many benchmarks. It also added a lot more comments to explain what is going on in that code, and removed multiple uses of unsafe.

I wanted to emphasize that last point because there's sometimes a misconception that using `unsafe` always means speeding up the code. In truth you can have speed and safety. Where unsafe is needed is when it's necessary to break from Rust's memory model or to otherwise write code that Rust cannot reason about.

I mention this because I've noticed even people familiar with Rust who sometimes imply `safe == slow` and `unsafe == fast`. At the extreme end you get some new users who think merely adding an `unsafe` block around code will provide a speed boost. It will not. In fact `unsafe` doesn't do anything itself. It simply allows calling some functions and performing a few other operations that would otherwise be forbidden. Sometimes this is indeed necessary but often it isn't.

petr_tik2• 6 years ago

It's great you emphasise it and I would generalise it even further. Any perf optimisation should be considered after reliably measuring (controlling for hot/cold cache, overall system load among others) its effect, instead of blindly adding unsafe everywhere.

Similar to people who sprinkle their Cpp code with inline thinking it will force the compiler to inline.

In fact, sometimes you can improve perf by adding an additional safe operation to your code! http://troubles.md/rust-optimization/#assert-conditions-befo...

The key takeaway from all perf optimisation articles to me is the methodology used for realiably verifying the effect of suggested changes. It's awesome to see the author include failed experiments.

dirtydroog2• 6 years ago

In modern C++, inline is used to prevent 'multiple-definitons' errors, not to actually inline the function.

coldpie• 6 years ago

It is shocking how often people suggest dubious code changes to "improve performance" with exactly zero benchmarks, or solely artificial benchmarks. Computers and compilers are far more complicated than your naive code analysis implies, you _must_ prove any performance changes with robust, real-world benchmarks, especially if your changes make the code more unsafe or harder to understand.

bjoli7• 6 years ago

On a similar note: some people seem to think immutable is slower than mutable. I have seen this many times, especially in my language of choice (scheme). A lot of people coming from python or c write loops using (while ...) and mutation, which in most schemes (and in many dynamic languages) is a nice way to get boxing penalties. Instead, a recursive function is almost always preferred. I have since since long preferred recursion.

Which (not strictly relevant) leads me to my biggest gripe (which is pretty small) with rust. I like rust. I really do. But a couple of times a week I have to use loop when tail recursion would have been a lot clearer. In debug builds , rust disables sibling recursion (a less general form of tail recursion) which means I have to either use a trampoline macro (simple and slow) or some kind of syntax rewriting macros (complex and fast). Neither seem like a good idea.

Should I just accept the ugliness of loop+mutation or is there a nice alternative?

jfkebwjsbx3• 6 years ago

Recursive functions should be avoided whenever reasonably possible, for several reasons (performance, safety, optimizer shenanigans...).

Immutable may be slower or faster than mutable, depending on what one is writing and optimizer.

kzrdude• 6 years ago

Rust has controlled mutable state, which is sort of a best of both worlds (vs pervasively everything-is-mutable and functional approaches)

nicoburns• 6 years ago

Consider contributing to the RFC process. This has been proposed a number of times, and I don't think anyone's against it. It's just not been considered priority.

I would advise that TCE will probably be more acceptable to the Rust community with an explicit opt-in syntax. And that `become` is a reserved keyword in Rust that is semi-earmarked for this purpose.

jfkebwjsbx3• 6 years ago

Unsafe does not imply fast, but safe does restrict what you can do.

In other words, the optimal safe solution can be slower than the optimal unsafe one.

wtetzner2• 6 years ago

On the other hand, it's possible that safe code gives the compiler more guarantees, so it has more room to optimize.

Whether your code is safe or unsafe can have a performance impact, but what the impact is depends on the specific situation.

lidHanteyk3• 6 years ago

So why is `unsafe` even in the language, then? It would seem to me that it simultaneously undermines safety guarantees, and it can't even ensure performance improvements.

conradludgate• 6 years ago

Unsafe can't ensure performance improvements, but you can sometimes get performance boosts using it.

It should be a last resort if you have a bottle neck that is a result of memory restrictions.

It's also how FFI works. If you're calling a c library, you cannot guarantee memory safety anymore since its outside of rusts domain, so it needs to be unsafe.

ChrisSD2• 6 years ago

At some point a Rust program does have to run on a real platform. Anything interacting with that platform will be `unsafe` because Rust cannot reason about things outside itself. You'd usually wrap these unsafe things in safe functions. Note this isn't about performance at all.

Also in Rust's model there are only unique or shared pointers (and the owned resource that they point to). This can't be used to represent all data structures. You need some unsafe code (ideally wrapped as Safe structures) to create these structures.

And as noted, `unsafe` can be used for performance improvements if benchmarking shows that breaking out of Rust's model does indeed improve performance. But you can't simply assume safe Rust incurs a performance hit or that your unsafe code will optimize better than the safe code.

In short, my point was one of emphasis and framing. When thinking about `unsafe` it shouldn't be thought of as a performance feature per se. That may be one effect of using certain features in certain situations but its an effect that needs to be proved by robust benchmarking.

alpaca128• 6 years ago

`unsafe` is in the language for compatibility, not performance. Rust programs run between countless other chunks of software, most of which do not have comparable safety features, same as the communication channels inbetween. But you still want Rust programs to be fully compatible with that "outside world" when needed.

umanwizard2• 6 years ago

Because performance improvements are not why `unsafe` exists. It exists to disable various conservative compile-time checks in order to let you write code that the compiler is unable to prove correctness properties about.

One reason to do this might be performance. An example: if you can prove lifetime properties but the compiler can’t, you might be able to just use raw pointers without the borrow checker, which is unsafe. This can let you avoid the performance penalty of smart pointers or cloning.

But there are other reasons to do it, too. Some things simply can’t be reasoned about by the compiler, like calling external C code, so they always need `unsafe`.

_pmf_• 6 years ago

So why is `unsafe` even in the language, then?

Because you cannot do "Hello world" without unsafe code somewhere in the middle.

jandrewrogers• 6 years ago

Using 'unsafe' isn't about improving performance, though it may be required to enable some performance improvements. It allows you to use constructs that the Rust safety checking infrastructure can't reason about. Memory used as a DMA target (ubiquitous in database engines) is an example.

Sammi• 6 years ago

There's a great new talk by on Gjengset on youtube that tackles just this question:

Rust NYC: Jon Gjengset - Demystifying unsafe code

https://www.youtube.com/watch?v=QAz-maaH0KM

giovannibajo1• 6 years ago

unsafe lets you exit the small subset of code patterns whose safety the compiler can prove.

Not everything that you write in unsafe is necessarily unsafe: it only means that the compiler can't prove it. Another way of thinking: if unsafe let you only write unsafe code, then it would be useless because that unsafe code would eventually segfault.

k__• 6 years ago

I heard that C/C++ game engine devs would throw everything on the stack and do their own thing in terms of memory management.

How does this approach play with Rust?

est31• 6 years ago

You can do this in Rust as well, and it's in fact being done in the compiler: https://github.com/rust-lang/rust/search?p=2&q=TypedArena&un...

https://docs.rs/rustc-ap-arena/655.0.0/rustc_ap_arena/struct...

In general, there is bad support in the standard for custom allocators, but there are crates that provide generic custom containers.

jononor• 6 years ago

No problem at all with using the stack a lot? But it would be explicit in most cases. Much less chances of memory corruption issues than in C/C++ thanks to lifetime tracking. And much less copying due to default move semantics, and the assurances given by lifetime tracking.

m12k• 6 years ago

Not a Rust dev, but from what I understand, the lifetime tracking of Rust means you can safely give out references to stack allocated memory without worrying about corruption/segfaults/use-after-free errors or the like, because the compiler will catch it if that is possible, whereas in C++ you'd usually want to do defensive copying in situations like that. So in some cases, Rust actually allows you to fearlessly do things the most efficient way in a way you'd not be able to do in C++.

MegaDeKay• 6 years ago

Reading the article made me wonder when the remove of unsafe was due to refactoring the code and when it was enabled by enhancements to the language since the code was originally written.

remcob• 6 years ago

Adding unsafe can even slowdown your code. The unsafe block prevents the compiler from making certain assumptions, which can prevent some optimizations from happening.

'unsafe' is like telling the compiler 'trust me on this', and the compiler (not fully understanding what is going on in there) wisely decides not mess with what you wrote.

steveklabnik12• 6 years ago

Adding an unsafe block changes nothing about compiler assumptions. Some unsafe constructs do not have the same optimization potential as their safe counterparts.

david_draco• 6 years ago

I love that they include a "Failures" section. It is most interesting to learn from.

yinyang_in• 6 years ago

Can you share the link of Failures section, couldn't find in articles website.

dwaltrip• 6 years ago

It's at the bottom of the post.

mkj2• 6 years ago

"The size of rlibs on disk has also shrunk by roughly 15-20%."

This is very welcome! The size of building a few rust projects on a laptop disk is fairly incredible sometimes. I guess cargo needs to learn clean up prior-to-latest deps directories too.

Benmcdonald__• 6 years ago

A 'cargo clean' every once in a while helps

mkj2• 6 years ago

Yeah, but then you have to wait 5 minutes to build the deps again. If it cleared the stale ones it'd be fine.

jonny383• 6 years ago

How much slower is rust as opposed to C or C++ for production sized builds?

Traditionally people have thrown more hardware at these kinds of problems. As someone who has yet to use rust for anything more than small hobby sized projects, I am naive about rustic in terms of speed

PudgePacket• 6 years ago

From what I've heard they're roughly comparable, some projects will swing one way, some the other.

Rust has solid incremental compilation now though so you shouldn't be paying the price of a full rebuild often.

DougBTX• 6 years ago

I had a quick search, but finding examples where the same project has been implemented in C++ and Rust with reported compile times seems to be rare...

There is a benchmark from way back in 2016 here: https://users.rust-lang.org/t/are-there-any-compilation-time...

Dev build was 2.91s for Rust vs 8.48s for C++, release build was 5.97s for Rust vs 9.79s for C++.

Would need to find much more recent examples for the comparison to be worthwhile.

slavik81• 6 years ago

That's a somewhat misleading comparison even for the time. All his C++ files could be compiled in parallel and recompiled incrementally, and his need for -flto to get good performance is really just due to how he structured his program. He seems to regard cpp files as the default location for functions and inlining as an optimization, but IMO it's the opposite. An empty function goes in the header, and every function starts off empty. You move it to a cpp file once it requires including a header. Moving a heavy function from a header to a cpp file is an action to optimize the compile time of your program.

On the other hand, it could be worse. There are some monstrously slow template libraries out there, and he's not using any of them. His code isn't very optimized, but it's sane.

steveklabnik12• 6 years ago

The Rust compiler was far different in 2016, across a number of fronts. It's gotten significantly faster, as well as added a number of features to tweak compile times in various scenarios, like incremental compilation.

WilliamEdward2• 6 years ago

https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

This is a handy resource, though no benchmarks are ever perfect. Rust comes out faster on about half the algorithms. They're pretty close though.

sambe4• 6 years ago

I don't know why people feel the need to downvote instead of clarify, but this page is about runtime speed. The article is about compilation speed.

Kenji• 6 years ago

In my personal experience, Rustc is not slower than GCC or Clang. If anything, it may even be faster. If you transition from C++ to Rust, you don't need to worry about compile times. Obviously C compiles much faster than both C++ and Rust.

flohofwoe• 6 years ago

I think the range of compilation times for C and different styles of C++ is so huge that this question cannot be answered without going into a lot of details about how the C or C++ project is structured.

You can compile hundreds-of-thousands of lines of "user-side" C++ code in a few seconds, or in a few hours. The range is much smaller in most C projects, but can also differ by orders of magnitude.

In short, splitting a C++ project into many small source files (e.g. "one file per class") combined with using a lot of C++ stdlib headers in each small source file is the worst case for a C++ project because of all the complex stdlib template code that needs to be compiled over and over again. This can increase the "under-the-hood" line count by several hundred times (in Google Chrome, the amount of "project C++ code" is only 0.125% of all the code the compiler needs to compile when rebuilding the project because of included headers):

https://randomascii.wordpress.com/2020/03/30/big-project-bui...

AFAIK Rust solves part of this problem with its module system, but the compilation time problems lurk elsewhere.

Here's an interesting webpage which looks at compilation time of C++ stdlib headers and some popular 3rd-party libs:

https://artificial-mind.net/projects/compile-health/

ashtonkem• 6 years ago

IF I understand correctly, the borrow checker comes with some pretty severe compilation costs, since it requires a pretty wide level of code analysis, and might be single threaded.

IshKebab6• 6 years ago

I have a question about LEB128. I use a similar format in my code, but with two changes:

1. It's big endian.

2. The "last byte" bit is inverted (so it's 00001 instead of 11110).

I changed the last byte flag so that it is easy to count the number of values in an array - you just do this:

  let mut count = 0;
  for byte in bytes {
    count += byte >> 7;
  }

And the reason I used big endian is because it makes decoding simpler. Encoding is more difficult but data is only ever encoded once, and is commonly decoded multiple times.

  let mut value = 0;
  for byte in bytes {
    value = (value << 7) | (byte & 0x7F);
    if value & 0x80 != 0 {
       return value;
    }
  }

Vs the original implementation which has do to this basically:

  let mut value = 0;
  let mut shift = 0;
  for byte in bytes {
    value |= (byte & 0x7F) << shift;
    if value & 0x80 != 0 {
      return value;
    }
  }

Here is the generated assembly in both cases: https://godbolt.org/z/6FbX_E

No idea if it would be faster than the new code but surely it is faster than the old code?

KMag3• 6 years ago

You should put all of those "has another byte" bits together, so you can look at just the first two bytes to figure out what to do, and then perform your load. In your most common case, you can perform an 8-bite MOVBE, an LZCNT/BSR, and if the number of leading 0s/1s < 8, just shift and mask to get your value.

Have a look at how UTF-8 is encoded for a similar scheme. The space taken is exactly the same as LEB128, but your code is less branchy and needs fewer masks and shifts.

IshKebab6• 6 years ago

The space taken is exactly the same as LEB128

No because values under 128 (very common in my data) take 2 bytes instead of 1. Unless I'm misunderstanding you.

timerol• 6 years ago

I would guess that Rust wants to stick to one standard encoding, and LEB128 is already in WebAssembly, DWARF, and LLVM. Adding BEB128 would add more complexity. Also, since Rust is generating a bunch of output files, it's definitely possible that it encodes more often than it decodes.

You missed a "shift += 7;" in your original implementation code, though it's present at the godbolt link.

It's not clear what point 2 is supposed to specify. LEB128 sets the 0x80 bit if there's a continuation. I'm not sure what "(00001 instead of 11110)" is supposed to specify. Does BEB128 leave the top bit clear when there's a continuation? Or does it set the lowest bit when there's a continuation? The code for counting would work for LEB128, but the text around it makes it seem like it's an improvement over LEB128.

IshKebab6• 6 years ago

Yeah I mean the continuation bit is just inverted so 0=continue, 1=end-of-value. You can still count values efficiently with 1=continue, 0=end-of-value, but you have an extra subtraction at the end (`return number_of_bytes - number_of_bytes_with_top_bit_set;`)

Good point about not adding another format. I guess they want to avoid confusion.

brandmeyer2• 6 years ago

I think its widely understood that a little-endian prefix VarInt decodes much faster as the leading alternative to LEB128. You can implement the whole thing without a loop, thus you don't have to exercise branch and loop prediction resources at all.

- count leading zeros (or ones, depending on the first byte's tagging preference)

- Unaligned load expressed as memcpy. Let the compiler's instruction scheduler peephole it out into a single unaligned load instruction.

- shift the loaded value by an amount indicated by the leading zero count.

- Zig-zag decode for signed integers

IshKebab6• 6 years ago

What do you mean by "little-endian prefix varint"? Like this?

``` enum VarInt { Byte(u8), Short(u16), Long(u32), LongLong(u64), } ```

I.e. one byte tag followed by the value? It's definitely an option for me but the main issue is that values under 128 now take 2 bytes instead of 1. I guess I could do something like what CBOR does and use 0-251 = literal value, 252 = u8 follows, 253 = u16 follows, 254 = u32 follows, 255 = u64 follow.

sysk• 6 years ago

Stupid question but could Rust skip monomorphization during development builds and use dynamic dispatch? I heard generics were often to blame for slow builds.

Ygg2• 6 years ago

It's a tradeoff. Do you want your code to run as if it was written by hand (i.e. duplicated by hand)? Then monomorphization is best.

For Rust, it makes a lot of sense to pay for some compile speed penalty to not have any performance penalty.

crazyjncsu• 6 years ago

during development builds

That's the key phrase in his statement.

I'm not familiar with Rust, but if compilation speed is a major issue, and there are aspects of the compilation that are avoidable to trade-off for runtime performance, it seems to be a good idea to make those configurable per-build-type. Does Rust not offer this?

cryptonector• 6 years ago

Do you want your code to run as if it was written by hand (i.e. duplicated by hand)? Then monomorphization is best.

That's not always true because monomorphization where the vast majority of the object code is the same in all actual cases means bloating the text of the program, which means putting pressure on the Icache, which means more cache misses, which... is slow.

oconnor6634• 6 years ago

In some cases maybe, but I don't think it could work in all cases. One of the things that monomorphization does for you, is statically determine the size of your types. For example, if you have a `Vec<u32>` and a `Vec<u64>`, the implementation of `Vec` needs to multiply by the size of the element type (4 bytes vs 8 bytes) to figure out the offset of each element. I don't think regular dynamic dispatch provides size information, so the compiler might need to "invent" a new flavor of dynamic dispatch internally if it wanted to do this?

steveklabnik12• 6 years ago

With dynamic dispatch, they'd all be fat pointer sized. It would move to Vec<Box<dyn SomeTrait>> where SomeTrait is auto-generated and implemented for u32 and u64.

Rusky• 6 years ago

It could potentially do that, but there are a lot of things that "normal" monomorphized generic code can do (and does routinely) that would be very very difficult to implement dynamically.

This post goes into a lot of detail on the subject: https://gankra.github.io/blah/swift-abi/

There are perhaps other tradeoffs that could be made instead, like doing more implicit boxing in debug builds, but it's not clear to me that those would be any easier to reconcile with all of the low-level details that Rust exposes. E.g. what happens to `mem::size_of` when an object of a polymorphic type has been boxed?

Related to this area is ongoing "polymorphization" work to detect pieces of generic code that actually do not depend on their type parameters, to avoid duplicating it: https://github.com/rust-lang/rust/pull/69749

This could potentially be made into a much finer-grained analysis to reduce the duplication further, though that may or may not actually help compile times depending on how expensive the analysis is.

swsieber• 6 years ago

Somebody wrote a macro for the simple cases: https://llogiq.github.io/2019/05/18/momo.html

vhbit• 6 years ago

when all of those changes will be in stable? will it be 1.44 or more likely 1.45?

steveklabnik12• 6 years ago

Depends on the change. The earliest one looks to be in 1.41, the latest one landed two days ago, so should be 1.45.

How to speed up the Rust compiler in 2020

Related Stories