Towards a second edition of the compiler

@matklad - Indeed! I didn’t want to jam a bunch of IDE stuff in the proposal, but there are good reasons to be as lazy as possible, and that’s another one of them. I think just in general not doing work we don’t need to do is going to be a big save, and that’s especially important when we ask the compiler to be more interactive, error-recovering, and whatnot.

On the libsyntax front, yes I think that’s another area I think we can do a bit better on. I can empathize with the desire to not lock down the API/ABI for working with the compiler’s structures, but there is a definite need to standardize them so other folks can use them.

Another example here, in addition to Dart, is that the TypeScript compiler (at least last I checked) uses the same parser for serving IDE and compilation. Both are pretty darn fast. For me, it feels like so long as you build it with both use cases in mind from the start, you can keep both pretty fast.

6 Likes

@dhardy - yes, cretonne is on the radar as a possible backend, though that’s still a ways out. Right now, the compiler, std lib, etc are all geared towards creating the fastest output binary. There definitely is a need for a “-O1” mode that aims to be both a fast compile and a reasonably fast output.

Some projects, like Jai (Jonathan Blow’s new language) I believe have a simple, custom codegen that can be used for fast edit-compile-run cycles. His videos show off him building and running his new game, which is currently at roughly 55kloc, in less than a second. The game runs at playable speeds. This dramatically increases his ability to test ideas and debug. Should we do something like that for Rust? It’s an interesting idea, at least.

9 Likes

Yeah, sorry for derailing the thread quite a bit :stuck_out_tongue: That said, "IDE support" can make edit-compile cycle much faster by removing compile part altogether in some cases.

Exactly! Just to make sure, my point wasn't "we need a separate parser for IDE" (I mostly was answering a question by @dhardy if they have to be the same). Ideally, IDE and compiler should use the same parser, which is super fast, incremental, aggressively recovers from errors and provides superb error messages.

That said, given that somebody tried to push libsyntax to crates.io and failed, and that recently rustfmt moved in-tree because it was easier than moving libsyntax out, I fear that the best way forward is to design a fresh syntax tree and a parser (syntax tree data structure itself being massively more important then the actual parser code) from the start, use it in RLS/rustfmt/clippy, and, if successful, move rustc over to it.

4 Likes

Rust’s crate-based compilation model does seem inherently inimical to fast compilation. Also, compilers tend to get slower with age. Put these together and the situation is challenging.

Here’s a question. Imagine you have a program that consists of two crates, A and B, where B depends on A. Do Cargo and rustc currently finish building A before they start building B? If so, could they instead overlap the back-end compilation (codegen) of A with the front-end compilation (parsing, checking, etc.) of B?

2 Likes

Yes, currently Cargo will wait for rustc to finish building A before it starts building B.

We already have a cargo check and rustc --emit=metadata which does checking, generate just enough for dependents, and skips code generation entirely. We could imagine a mode where rustc first generates A’s metadata, then somehow signals to Cargo that that metadata is ready, then continues with codegen while Cargo starts compiling B in parallel. But this doesn’t exist yet.

5 Likes

That idea has come up several times in discussion and MIR only rlibs are a big step towards that (also see my earlier thread about this). There has been no official decision by the compiler team to get this going though.

1 Like

@jntrnr thank you for proposing all this! Beyond the concrete benefits you mentioned, I firmly believe this is the Right Way ™ / elegant thing to do.

In too many languages, the compile is a rather monolithic program divorced from the larger ecosystem (Rustc today even is far from the worst offender). I think we’ll see unprecedented itch-scratching in hard-to-foresee ways.

Certainly the overall framework for cached, parallel, lazy, persisted, etc compilation has uses many uses beyond the compiler. I would love to see that factored out.

5 Likes

I think “MIR-only rlibs” + ThinLTO + incr. comp. will get us pretty far already and all of those will happen sooner or later within the current architecture. Parallelizing type-checking seems to be the hardest item on this list.

2 Likes

@jntrnr So, has any work gone into a second edition compiler? Are there any crates/github projects etc. working on this?

While this proposal seems to be the most liked idea to this date, I do not think that this is a viable undertaking without Mozilla’s and the core team’s express support and stewardship.

I don’t think it would be wise to fractionate the community’s efforts without a clear plan of transitioning from one code base to another. I think that we are best off with one reference implementation for the time being. It’s not like with C that has been stable for decades. Rust is still undergoing a fantasic growth and development. I’d hate to see this flourishing thing we’ve got lose pace now!


I’d be grateful if anyone from the core team would share their views. Sorry if I’ve missed any comments.

3 Likes

@DanielFath - sadly, it’s more of a “fever dream” than something currently being planned. That said, it’s my hope that some of this can be investigated (eg splitting up the compiler into crates that others can consume). Other changes, like the deeper parallel/lazy fixes, would be pretty invasive and would likely have to show strong promise before anyone attempted them.

@repax - right, I don’t think that’d be wise either as a general rule. It’s tempting to think of the possibility of a second compiler being built that could use the newer understanding of the algorithms that are coming along (eg, just start with NLL and the new trait system to begin with). That said, I can’t think of any cases where an alternate compiler became the primary one, cpython is still the main one, the Ruby 1.9->2.0 was a core effort, same for C# and Roslyn, etc. So I agree it would need to be core driven and part of the planning, which this isn’t.

1 Like

One question that bothers me is do we really need all this high-tech to make compiler fast? My understanding that compilers which are praised for speed (Go, Java, D, C) don’t do much in terms of laziness (Actually, I have no idea if this is indeed true, would be glad to hear a more informed opinion!).

2 Likes

Maybe it would be better to start of a bit more conservative first before considering a second edition. If the LLVM steps are taking up a lot of time, it might be worth starting a larger effort and look into what we can do to reduce the amount and complexity of output to LLVM. I think there is a lot of room for improvement there. Given the generic nature of the standard libraries, there is a lot of indirection which ends up in a fair bit of code for the llvm optimizer to clean.

As for paralellization, there is work being done on that in the existing compiler:

Laziness is generally coming from compilers built to support IDEs from the start, like C#'s Roslyn compiler and the TypeScript compiler.

Compilers that are generally “fast enough” like the Go compiler can provide IDE support using just straight-line compilation alone. Response times aren’t quite as good as lazy compilers, but may be okay for most use cases.

It’s in general just a fever dream of a post where I imagine some pretty heavy-weight ways to improve things, with the hope we generate some ideas to use later on.

@oln - I’d love for someone just to look into how we could be reduce the complexity of what we give LLVM. I know a few people have talked about looking into this, but I don’t know if anyone has really dedicated the time to do it, yet.

2 Likes

At least for C and Go, one aspect that probably helps a lot is that the type system is pretty much trivial. Rust's powerful generic types and trait system provide lots of benefits, but they also make type-checking and compilation a much harder problem.

The java compiler doesn't have to generate machine code; it targets JVM bytecode. That's a much simpler target, and also means it doesn't do many of the interesting (and expensive) analysis and optimizations that LLVM does -- with Java, these are done at run-time by the JIT of the JVM.

I don't know much about D, so I cannot comment on that.

2 Likes

Type checking and trait resolution are by far not the biggest contributors to Rust compile time. There is room for improvement, but fixing them on their own isn’t going to move the needle on the “Rust is slow to compile” meme.

Yeah, maybe that deserves a separate topic. Though, to give some perspective, I compared the LLVM IR output of a rust and a cpp version of a very simple code example:

As noted in the gist, the output from the rust version is about 5 times larger. (Given that the sed command I used does what I think it does.)

Now, the number of lines of code may not be the best way to judge this. Ideally one would probably check the pre optimisation output for an optimized build, though I didn't find a good way to do that (there probably is though.) I don't think rustc does much in the way of optimisation itself at the moment (only thing I can find for sure is removing redundant *&.) so it may give an estimate at least.

6 Likes

This is a good nugget of a find. Maybe @alexcrichton or @michaelwoerister (or perhaps someone else on the compiler team) knows why this might be.

I think part of the difference in the size of the output is the fact that rust does a lot more things than C++ through function calls at the moment. For example, checking if a pointer is a null pointer: In C++ one would usually do either if (!ptr) or if !(ptr != nullptr), while the rust code does this with ptr::is_null(), which subsequently calls ptr::null() to get the null value for a pointer. I don’t know the innards of the compiler well enough to say how large of an impact all the extra inlining llvm has to do is though. Maybe doing some of this work a bit earlier in the pipeline, e.g on the mir level would be helpful.(Don’t think that works cross-crate).

EDIT: Alternatively something like what’s described in this issue might be helpful: https://github.com/rust-lang/rust/issues/14527. EDIT2: May actually not be too helpful given that inlineable functions tend to be generic, though the issue does shed some light on why the optimizer has to do a lot of inlining work.

Making that work requires storing MIR within the rlibs. I know that's been discussed, but I don't know if it's been implemented.