Towards a second edition of the compiler

matklad · 2017-07-21T16:58:00.704Z

glaebhoerl:

Oh, of course procedural macros are a different matter. But I think there’s no reason in principle why declarative macros (macro_rules!) couldn’t be handled directly?

macro by example requires name resolution, which requires knowledge of a build system (to know crate roots and cfg flags), and so is quite a sizable part of the compiler, not only the parser. In principle, it’s possible to handle everything on the IDE side (that’s what we do in IntelliJ) but if one want’s to split IDE and compiler, I would say that all syntax should live in the IDE, and all semantics, including all macros, should live in the compiler.

regexident:

Couldn’t the current stripped-down syntax-tree (T2) be generated with a transformation on a more complete tree (T1)?

This will work perfectly in a language without macros. If you have macros, you’ll sometimes need to parse AST not from the source code, but from bits and pieces produced by other macro expansions. So the T1 parser must handle both parsing raw text, and parsing in-memory results of previous expansions. This could be done as well, but is more difficult.

regexident · 2017-07-21T17:59:55.876Z

Ah, I see. Should have guessed it’d be macros. I knew there had to be something, 'cause otherwise the great minds behind rustc would have gone that path long ago.

jntrnr · 2017-07-21T18:34:38.043Z

@ahmedcharles - I think these are good questions. There’s lots of good work in the current compiler, and lots of hours has gone into making it. I’m not proposing we throw it out or anything. That said, I hope that we can take a step back and think about what the fastest compiler might look like in terms of its architecture and capability and see what it would take to get there.

jntrnr · 2017-07-21T18:40:05.753Z

@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.

jntrnr · 2017-07-21T18:48:17.949Z

@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.

matklad · 2017-07-21T19:02:59.490Z

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

jntrnr:

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.

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.

nnethercote · 2017-07-22T00:16:36.418Z

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?

SimonSapin · 2017-07-22T05:43:51.488Z

nnethercote:

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?

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.

est31 · 2017-07-22T18:04:19.361Z

nnethercote:

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?

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.

Ericson2314 · 2017-07-23T01:38:42.780Z

@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.

michaelwoerister · 2017-07-27T16:25:45.664Z

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.

DanielFath · 2017-08-09T12:32:47.583Z

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

repax · 2017-08-09T14:34:38.606Z

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.

jntrnr · 2017-08-09T18:59:42.464Z

@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.

matklad · 2017-08-10T09:49:53.447Z

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!).

oln · 2017-08-10T14:07:57.490Z

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: https://github.com/rust-lang/rust/pull/43506

jntrnr · 2017-08-10T18:54:39.433Z

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.

RalfJung · 2017-08-10T22:23:43.731Z

matklad:

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

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.

rpjohnst · 2017-08-11T00:41:36.350Z

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.

oln · 2017-08-11T18:05:16.465Z

jntrnr:

@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.

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:

gist.github.com

https://gist.github.com/oyvindln/3d9c074f22e249f15d7e3f89267e0310

vec.cpp

// clang++ -S -std=c++11 -emit-llvm -vec.cpp -o vec_cpp.ll
// lines: 891
// ( wc -l vec_cpp.ll )
// with stripped blank lines and comments:
// ( sed '/^\s*;/d;/^\s*$/d' vec_cpp.ll | wc -l )
// 698

#include <cinttypes>
#include <vector>

This file has been truncated. show original

vec.rs

// rustc +nightly --emit llvm-ir vec.rs -o vec_rust.ll
// lines: 4634
// ( wc -l vec_rust.ll )
// with stripped blank lines and comments:
// ( sed '/^\s*;/d;/^\s*$/d' vec_rust.ll | wc -l )
// 3523

fn main() {
    let v = vec![0i32;100];
    for n in v {

This file has been truncated. show original

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.