[Cogito]

Really great read.

Someone mentioned recently that the slowness of rustc is in large part due to llvm. I know that is probably orthogonal to the work here, but I do like the idea of building the compiler with different toolchains, and that there may be follow on effects down the line.

[JoshTriplett]

Depends on the workload, but yes, codegen is a huge part of the total compilation time.

That said, that doesn't mean LLVM is always where the fixes need to be. For instance, one reason rustc spends a lot of time in LLVM is that rustc feeds more code to LLVM than it should, and relies on the LLVM optimizer to improve it. Over time, we're getting better about how much code we throw at LLVM, and that's providing performance improvements.

[Cogito]

I'm completely ignorant so forgive me if this is obvious: in the effort of the parent article - to compile rustc with gcc - will rustc still be feeding lots of code to LLVM, or would that code now be fed to gcc?

[feznyng]

There's an experimental compiler backend [1] using cranelift [1] that's supposed to improve debug build times. I never see it mentioned often in threads about Rust's long compilation time so I'm not sure if I'm missing something.

[1] https://github.com/rust-lang/rustc_codegen_cranelift/ [2] https://cranelift.dev/

[torstenvl]

It's slow because the borrow checker is NP complete. LLVM may or may not generate slower code than GCC would for rustc, but I doubt it's anywhere close to the primary cause of the lack of snappy.

[almostgotcaught]

You're wrong it's been debunked that the borrow checker is any appreciable part of the compile time - Steve Klabnik actually verified it on here somewhere.

Edit: found it

https://news.ycombinator.com/item?id=44391240

[resurrectedcyb]

I do not know if the borrow checker and Rust's type system have been formalized. There are stacked borrows and tree borrows, and other languages experimenting with features similar to borrow checking, but without formal algorithms like Algorithm W or J for Hindley-Milner, or formalizations like of Hindley-Milner and problems like typability for them, I am not sure how one can prove the complexity class of the borrow checking problem nor a specific algorithm, like https://link.springer.com/chapter/10.1007/3-540-52590-4_50 does for ML.

I could imagine you being correct about the borrow checking typability problem being NP-complete. Or an even worse complexity class. Typability in ML is EXPTIME-complete, a larger set than NP-complete https://en.wikipedia.org/wiki/EXPTIME https://dl.acm.org/doi/10.1145/96709.96748 .

I also am not sure how to figure out if the complexity class of some kind of borrow checking has something to do with the exponential compile times of some practical Rust projects after they upgraded compiler version, for instance in https://github.com/rust-lang/rust/issues/75992 .

It would be good if there was a formal description of at least one borrow checking algorithm as well as the borrow checking "problem", and maybe also analysis of the complexity class of the problem.