How to speed up the Rust compiler in 2020
blog.mozilla.org
blog.mozilla.org
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.
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.
Then I found a smarter algorithm, and my qbasic proof of concept was magnitudes faster. Ouch!
This kid learned something about the nature of optimization that day. Now Im an old fart but even older farts than me stumble into this.
My favorite example of that was a memory-bound app where a key function had been implemented in both C and x86 assembly. Someone tested and found that the assembler version had been slight performance loss since (IIRC) after the Pentium Pro, and since nobody had wanted to substantially change the assembly code going C-only meant they actually refactored the data access patterns and saw a substantial improvement.
I hope something like NixOS will enable people to write and publish "reproducible" (in quotes because precise numbers are impossible) benchmarks by enabling you to setup your OS, user space and compilation flags exactly like in the benchmark.
So your benchmark environment could actually be pretty minimal, or if you were sharing a bug reproduction it could be devoid of unrelated packages/config in your usual environment.
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?
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.
Such a proposal would in any way be "future proof" in the sense that general becomes-TCO could be added later in a compatible way.
Sometimes iterators aren't enough though, and if I had reliable sibling recursion in debug mode, most of my use of loop would disappear.
Immutable may be slower or faster than mutable, depending on what one is writing and optimizer.
Scheme implementations usually doesn't even bother doing type inference once you start using set!, and just implicitly boxes everything that you mutate. Of course you _can_ optimize it, but once you have a language with multi-shot continuations you are probably better off encouraging immutability.
There was a proposal many years ago to add a keyword like "return" that guaranteed tail call optimization to rust. Unfortunately that RFC was never accepted and implemented.
In particular it is hard to determine whether the body of your function is slow or whether it is recursing too much.
"become" became reserved before rust 1.0. One could maybe just let it guarantee LLVM sibling recursion as a starting point and maybe extend it with proper TCO later.
As for Scheme, that is a detail of Scheme, not general mutability vs. immutability.
General TCO would be nice as well, say when writing a state machine/recursive descent parser, but that is a hassle, especially if you want C interop. Since many of the rust devs are old ocamlers, I doubt I need to explain the virtues of (tail) recursion to them. Which is also why I never bothered to bring it up: they probably have very good reasons for not supporting it. The reserved "become" keyword is testament to them at least giving it some thought.
In other words, the optimal safe solution can be slower than the optimal unsafe one.
Whether your code is safe or unsafe can have a performance impact, but what the impact is depends on the specific situation.
How does this approach play with Rust?
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.
'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.
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`.
There is a subtle but important distinction here. Unsafe does not disable any compile time checks. It adds additional constructs which are not checked.
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.
Rust NYC: Jon Gjengset - Demystifying unsafe code
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.
Maybe to back this up with a concrete example, let's say I'm parsing something and I have a &[u8] (a string of bytes) which I have already verified contains only ASCII digits. I wanted to get the numerical value of that number. I don't want to write my own number parsing code, but std only has a parsing function for &str (UTF-8 strings), not for &[u8]. I could do
let string = str::from_utf8(bytes);
let value: u64 = string.parse()?;
//SAFETY: `bytes` was already proven to only contain ASCII digits
let string = unsafe { str::from_utf8_unchecked(bytes) };
let value: u64 = string.parse()?;
let (result, len) = match std::str::from_utf8(buf) {
Ok(s) => (s, buf.len()),
Err(err) => match (err.valid_up_to(), err.error_len()) {
(0, Some(_)) => return Err(Error::Utf8(err)),
(0, None) => return Err(Error::NeedMoreData),
(valid_up_to, _) => (
unsafe { std::str::from_utf8_unchecked(buf.get_unchecked(..valid_up_to)) },
valid_up_to,
),
},
};
( * ) Nothing prevents it from doing that, and one of these days I might get around to PRing it.
Isn't there a risk of Rust code having "Don't ever change this" comments?
Because you cannot do "Hello world" without unsafe code somewhere in the middle.
(Also, Java had an unsafe mode for a long time, and its removal caused quite the upheaval, from what I understand.)
There are two main solutions to this:
1. have some sort of "unsafe" language construct so that you can make syscalls yourself.
2. Disallow arbitrary syscalls. put the code for making said syscall inside of some trusted code, whether that be the the runtime or the standard library.
Rust has chosen option #1. Java has chosen #2.
(Also, virtually every language has an "unsafe mode" in whatever C FFI exists. I was referring to sun.misc.Unsafe earlier, but JNI still exists, of course.)
To rephrase my point: including an unsafe mode is an option when designing a language. Your original comment appeared be suggesting that it was a necessity, and that one could not write a Hello World program in a language that lacks an unsafe mode. Which is not the case, of course. JavaScript, for instance.
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.
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.
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;
}
let mut value = 0;
for byte in bytes {
value = (value << 7) | (byte & 0x7F);
if value & 0x80 != 0 {
return value;
}
}
let mut value = 0;
let mut shift = 0;
for byte in bytes {
value |= (byte & 0x7F) << shift;
if value & 0x80 != 0 {
return value;
}
}
No idea if it would be faster than the new code but surely it is faster than the old code?
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.
No because values under 128 (very common in my data) take 2 bytes instead of 1. Unless I'm misunderstanding you.
The obvious implementation fast path is:
1. Check that the current position is at least a 8 bytes from the end of the buffer. Otherwise, go to the short buffer slow path.
2. Count the number of leading 1s (or 0s) using BSR/LZCNT.
3. If the number of leading 1s (or 0s) indicates more than 8 bytes are necessary, use the multi-word slow path.
4. Shift and mask out your value.
5. Increment your position pointer by the length of your varint.
Values less than 128 will have no leading 1s (or no leading zeros, if your scheme uses leading zeroes instead). The shift value is 56 bits. Unless you have a 1-byte optimized path, your calculated mask value is (((uint64_t)-1LL) >> 57). The position pointer is incremented by one byte at the end of the decode.
Maybe it's most clear if I spell out the 19 cases necessary to encode any uint128_t (system using BSR (leading 1s) insteod of LZCNT (leading 0s)).
0 xxxxxxx -> 0 to 127
10 xxxxxx yyyyyyyy -> 128 to 2**14 - 1
110 xxxxx yyyyyyyy zzzzzzzz -> 2**14 to 2**21-1
1110 xxxx yyyyyyyy zzzzzzzz aaaaaaaa -> 2**21 to 2**28-1
11110 xxx yyyyyyyy zzzzzzzz ... 2 more bytes -> 2**28 to 2**35-1
111110 xx yyyyyyyy zzzzzzzz ... 3 more bytes -> 2**35 to 2**42-1
1111110 x yyyyyyyy zzzzzzzz ... 4 more bytes -> 2**42 to 2**49-1
11111110 yyyyyyyy zzzzzzzz ... 5 more bytes -> 2**49 to 2**56-1
11111111 0 yyyyyyy zzzzzzzz ... 6 more bytes -> 2**56 to 2**63-1
11111111 10 yyyyyy zzzzzzzz ... 7 more bytes -> 2**63 to 2**70-1
11111111 110 yyyyy zzzzzzzz ... 8 more bytes -> 2**70 to 2**77-1
11111111 1110 yyyy zzzzzzzz ... 9 more bytes -> 2**77 to 2**84-1
11111111 11110 yyy zzzzzzzz ... 10 more bytes -> 2**84 to 2**91-1
11111111 111110 yy zzzzzzzz ... 11 more bytes -> 2**91 to 2**98-1
11111111 1111110 y zzzzzzzz ... 12 more bytes -> 2**98 to 2**105-1
11111111 1111111 0 zzzzzzzz ... 13 more bytes -> 2**105 to 2**112-1
11111111 11111111 0zzzzzzz ... 14 more bytes -> 2**112 to 2**119-1
11111111 11111111 10zzzzzz ... 15 more bytes -> 2**119 to 2**126-1
11111111 11111111 110zzzzz ... 16 more bytes -> 2**126 to 2**133-1You 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.
Good point about not adding another format. I guess they want to avoid confusion.
- 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
``` 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.
Ie, two leading ones set in the first byte mean that there are two trailing bytes.
https://news.ycombinator.com/item?id=11263378 is one description.
https://github.com/stoklund/varint has some benchmarks.
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.
You can box Copy types.
I do think you're correct here, which is that this idea sounds simple but has a lot of edge cases.
I could see some kinds of funny differences in behavior between debug / production builds, if for a debug build a particular thing is boxed, but in production it isn't.
But if you're generating polymorphic dispatch code at a lower level than expressible in Rust itself, there is no reason why hidden box types cannot be used to simulate unboxed types. That's just a memory representation difference. A bit like the way V8 creates specialised types for JavaScript objects at run time, but it's invisible to JavaScript except for speed.
For Rust, it makes a lot of sense to pay for some compile speed penalty to not have any performance penalty.
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?
For many applications debug builds are fast enough, but their runtime performance is already so slow, that I hope they don't get even slower.
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.
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
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:
tl;dr: Profiling and tests show that codegen and LLVM work takes up the lion's share of compilation time. The borrow checker itself isn't that expensive in the grand scheme of things, and languages like OCaml show that it's very feasible to have a complex type system that compiles quickly.
Rust has solid incremental compilation now though so you shouldn't be paying the price of a full rebuild often.
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.
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.
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.
n-body Rust #7 program 16.37s to complete and log all make actions
n-body C++ g++ #2 program 6.22s to complete and log all make actions
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
Something seemed a bit weird with those numbers to me. My heavily loaded 2015 MacBook Air, which is also overheating, took <5s to compile nbody with the same Rust version and command line. The ratio remains about the same though - a similar GCC version is also much faster. Turns out, the hardware is really, really old ("Measured on a quad-core 2.4Ghz Intel® Q6600® with 3.8 GiB of RAM and 250GB SATA II disk drive; using Ubuntu™ 19.10 Linux x64 5.3.0-29-generic.").
So for that back-of-the-envelope comparison of compile times (of 300 line tiny tiny programs) it really really doesn't matter that "the hardware is really, really old" :-)
"relative ones" :-)
True.
Although if jonny383 actually wanted to know how many seconds then shouldn't our answer be — it depends.