Hacker News Reader

Comment by gok | Hacker News Reader

Novel compiler backends are a super cool idea, but I don't think it's going to help Rust compile speeds as much as this posts suggests. The complexity of Rust's type system puts a pretty high lower bound on compile times because of work the front end needs to do. Plain C compiles quickly even with an LLVM backend, for example.

View on HN

Rustc normally spends way more time in LLVM than in the frontend. Rust parsing and type checking are very fast in comparison to LLVM's codegen.

Here is a chart from last September showing where the time goes in compiling a large Rust codebase (rustc itself):

https://gistpreview.github.io/?74d799739504232991c49607d5ce7...

(Scroll down to the large horizontal bars once dependencies have been built.) (Sorry if GitHub is down at the moment; try later if it doesn't load.)

The blue part of each bar is time in the frontend, the purple part is time in LLVM. The largest bar (rustc) spans 105 seconds in LLVM out of 140 total, or 75% in LLVM. Many of the subcrates are even more dominated by LLVM time, for example look at rustc_metadata or rustc_traits where >95% of compile time is spent in LLVM.

Rust is famous for throwing garbage IR at LLVM and hoping it cleans it all up. They've made a lot of progress but comparing the timing is very misleading when the work is intentionally offloaded to LLVM.

Isn't that kind of the point of having a relatively high-level backend - to avoid the need for every front-end to do the same tedious optimizations?

You do have to have some sort of balance. With a large enough input, any program will become slow.

My comment is in response to "super cool idea, but I don't think it's going to help Rust compile speeds". Even a compiler that emits garbage IR from the frontend would get 20x faster with a magic instant backend if 95% of time is currently spent in the backend.

A magic instant backend is unrealistic, so Rust will need to move some of the current backend work to frontend work for things that can be done more efficiently on the frontend. But the fact remains that there is an opportunity for big improvement from a much faster backend.

It sounds like this is addressed in the post, no? LLVM IR doesn't always map cleanly to Rust representations, so a backend that supports a cleaner mapping should obviate the need for more frontend optimization.

I'm basically a layperson when it comes to this topic, but that's my understanding of one of the potential benefits of a different backend.

I think you might be surprised just how much time is spent in codegen- and optimization-related code.

For example, a bit over 75% of the time needed to compile the regex crate can be attributed to codegen- and optimization-related events, with a bit over 64% of that time spent in LLVM-related events specifically [0]. Granted, I'm not certain whether this is a release or debug build, but it does show that there is room for significant wins by switching backends.

As for why C can compile quickly with an LLVM backend while Rust can't, I'm not sure. I've read in the past that rustc generates pretty bad LLVM IR to pass to the backend, and it takes time for LLVM to sort through that, but there's probably some other factors in there too.

[0]: https://blog.rust-lang.org/inside-rust/2020/02/25/intro-rust...

I wonder how much of it is just code style. A simple for-loop in C is probably going to be an iterator blob in Rust with an order of magnitude more code for the backend to chew through.

We can compare them! https://godbolt.org/z/-Fzuqs

(My screen is small so it's tough for me to read these results, to be honest...)

I believe that is the IR after the optimizer has chewed through it.

Oh duh. Should be obvious that you can drop the -O flags, at least.

Yes, which gives about 40 lines of IR for C, and about 1300 for Rust (Godbolt truncates it at 500).

Part of it may be code style, but another part comes from just how much LLVM IR the frontend generates for just about any code style.

Part of the reason LLVM runs so much faster on C than on Rust is that Clang is smarter about generating less/better IR from the start, so LLVM's optimizer has less of a hole to dig itself out of.

I think it's actually mostly the language. Rust idioms just generate a lot of code.

Clang is in a worse spot than rustc is in terms of emitting good LLVM IR, since it has no IR aside from the AST. By contrast, rustc has MIR which is more amenable to optimizations. At this point I'm fairly sure the problem is just that C code naturally generates less IR than Rust code does. All those function calls that go into iterators, array indexing, containers, etc. etc. add up quick.

Modern C++ is in a similar situation with iterators, indexing, etc. and it's still often faster for LLVM to get through.

MIR optimization can help close the gap but that still involved generating "garbage" that takes extra time to codegen (in Debug) or optimize out (in Release).

Being smarter about generating IR, whether MIR or LLVM IR, is still an area rustc has a lot of room to improve, even given Rust's idioms. E.g. stuff like this: https://github.com/rust-lang/rust/issues/69715

I think people are way too hard on rustc. That linked issue is pretty esoteric and is a good example of the low-hanging fruit being picked. I doubt it'll move the needle much.

It's hardly esoteric when it affects some of the most common (and commonly-inlined) methods in the entire language, which are a large part of Rust's unique idioms.

While the type system does add to compile times, profiling generally doesn't show that it's the current limiting factor for compile times. Additionally, tools like rust-analyzer will give you type errors pretty much instantaneously, though of course that work is not finished.

Also of note, this blog post isn't speculation; they posted numbers from actually doing it.

A 30% speedup is nothing to sneeze at, but it's not putting Rust within spitting distance of Go or C for similar amounts of code.

Absolutely. I don't see where anyone is claiming that.

Haskell, OCaml, SML, Idris also compile quite fast, with complex type systems.

Their secret? Multiple backends with different kinds of optimizations.

You don't need to compile for the ultimate release performance when in the middle of compile-debug-edit cycle.

From my (limited) experience, Haskell does not compile fast, especially if you’re doing something that needs lenses.

It surely does, because Haskell is not one compiler language, not only does it have multiple implementations, which I concede almost everyone only cares about GHC, there are interpreters and a REPL experience as well.

You don't need to compile your program in one go using GHC's LLVM backend, many times a GHCi session is more than enough.

Haskell and Idris both have very slow compilation time.

Only when using release mode compilers, they also have interpreters and REPLs to choose from.

Reply on news.ycombinator.com