Is there some algorithm in Rust which has a necessary big-O? There were compilers in the 90s which ran a million lines per second (on much slower computers). Incremental compilation feels like working around the problem rather than solving it, and I have to imagine the complexity and maintenance is much worse.
I'm sure some of the LLVM optimization passes are expensive, but those are used in clang++ too, and it's not terribly slow.
Those compilers performed nowhere near the level of optimization that modern compilers do.
> I'm sure some of the LLVM optimization passes are expensive, but those are used in clang++ too, and it's not terribly slow.
clang++ is sure slow if it has to rebuild an entire codebase from scratch.
The main reason that C++ compilers get away with not having partial compilation is that it forces programmers to do the division into code units manually through separate .h and .cpp files. Rust doesn't have this, except at the crate level, so it needs partial compilation instead. It turns out that partial compilation is better in the first place, because compilation units tend to be fairly coarse-grained: .cpp files frequently grow very large.
It's the cross-module optimizations that make the compiler slow. Those optimizations are in service of C++-inspired ideal of being able to use layers of abstraction to make your code cleaner, but having the compiler flatten them down so your program still runs fast.
It’s called incremental progress.
I'm simply pushing back on the idea that there's some obvious low-hanging fruit that clang did that rustc didn't. Compiler performance has more or less much been the #1 goal for well over a year now. The Rust compiler team (which hasn't included me for years, by the way) is fantastic. We'd all like for there to be some magic bullet that makes the compiler faster, but at this point I don't believe it exists. It's hard work from here on out.
I didn't suggest low hanging fruit or a magic bullet. If anything, incremental compilation is being promoted as that kind of thing, and I just wanted call it into question.
Not to mention the underlying insinuation, that the Rust compiler developers are dumb for not being able to get at the 80s compiler's level of speed -- since you don't seem to accept that this is a byproduct of the advanced optimizations and security guarantees they do.
Try to be scientific. If you've got a conjecture, test it and see if it holds water. One excuse was that C++ is only faster because people build C++ projects with separate compilation units. Well, you can compile a project in C++ with a single compilation unit, and it's not horribly slow. Now you need a new conjecture.
The type system is comparable to Standard ML from the 70s. The lifetime analysis is a solid improvement over mainstream languages, but I have a tough time believing it needs to be an order of magnitude slower than const correctness. The optimizations are on par with C++ and Fortran (mostly because they're leveraging the guts from an existing C++ compiler). SML, C++, and Fortran do not compile as slowly as Rust. There's probably another reason.
I don't think the Rust compiler developers are dumb, and I never said that. I think several of them are brilliant but young (and occasionally very arrogant).
Rust is so close to being a great replacement for C++. I read every one of these threads about new releases hoping they'll eventually fix the problems. Compilation speed and memory use are lesser issues, but they're still important, and things like incremental compilation dodge the issues instead of fixing them.
The type system of Rust goes significantly beyond that of Standard ML, because of traits/typeclasses among many other features. Also, Standard ML is usually not implemented with monomorphization, which affects compile time.
> Compilation speed and memory use are lesser issues, but they're still important, and things like incremental compilation dodge the issues instead of fixing them.
Incremental compilation is a way of addressing the compile time and memory usage issues. It's just not the way you seem to want them to be fixed. Nobody did incremental compilation for fun; it was done because without it we didn't believe we could reach our compiler performance goals.
Again, you're asking for a magic bullet, and I'm saying it's not likely that there is going to be one. If one existed, it probably would have been found already. There's lots of hard work that has been done, and lots of hard work ahead.
If I had to guess what the most important issue is, it's that idiomatic Rust generates a lot more LLVM IR than idiomatic C++ does, because it leans on abstractions for safety and developer ergonomics. Think about how many more closures Rust code uses, what for loops expand to, what pointer arithmetic compiles to (ptr::offset), etc...
> Incremental compilation is a way of addressing the compile time and memory usage issues. It's just not the way you seem to want them to be fixed. Nobody did incremental compilation for fun.
I'm well aware that my opinion doesn't matter, but I doubt incremental compilation will make any real strides towards making things as good as they could be. It sounds like the real problem is here:
> If I had to guess what the most important issue is, it's that idiomatic Rust generates a lot more LLVM IR than idiomatic C++ does
I suspect every single feature in idiomatic Rust has a one-to-one translation to some bit of C++ that isn't too horrible. You can do lambdas, iterators, generators, or whatever else it takes to do Rust style for loops and closures in C++, and it won't choke the compiler. So while I don't doubt rustc is generating a lot more IR, I doubt it needs to.
Maybe the MIR optimization pass will move in that direction.
I think this gets at Wirth's law a bit. Yes compilers perform lots of optimizations now, but in Rust's case it is at least partly because they need to in order to claw back the performance that the Rust gives up with its abstraction (as seen in debug builds).
I do much prefer Rust's safe abstractions to writing more direct code and hoping I get it right. I hope (and do believe) that the MIR effort will somewhat rein in the burden shunted over to LLVM, as it is super painful for some of us.
I think Proebsting's law is also relevant. Compilers did an impressive job of optimization in the 90s, and while yes there have been advancements in the last 18 years, it's foolish to over-estimate the progress.
Also, considering how much hardware changes have improved performance (speculative execution, register renaming, etc...), it wouldn't surprise me if many compiler optimizations have become less important with time. For instance, peep-hole instruction scheduling has to matter less than it once did.
It really does make a difference versus traditional UNIX compilers.
We have some hunches, but nothing super conclusive yet; basically, right now it's all about how much IR we generate.
Don't forget the differences in compilation model; C/C++'s compilation units are much smaller, so incremental isn't as big of a deal.
It's hard to say what exactly Jai does since it's not public yet.
Not everyone compiles C++ the same way. I prefer header-only libraries and a single compilation unit. Counting lines of code with "gcc -E" to get the headers, I just compiled 20,000 lines of C++ from scratch in .6 seconds with gcc and .4 seconds with clang. I don't have a comparable project in Rust.
(And in the case of uninstantiated templates, a C++ compiler doesn't even need to type check them…)
- Did you have optimizations enabled?
Not many. How many lines would a comparable Rust program have to instantiate? (should be the same)
All I was trying to do was make an apples to apples comparison by discrediting the implication that the clang++ and g++ compilers are only faster because people use separate compilation units.
I think it's fair to compare Rust and C++ this way, and if Rust is slower to compile, then it's fair to ask why.
> Did you have optimizations enabled?
Yes, -O3. Also -Wall -Wextra and -fwrapv if you're interested.
When you add generics, lifetimes, and type inference, the amount of work the compiler does grows significantly. It allows to check much more interesting invariants, leading to the "if it compiles, it runs correctly" effect.
Rust does have the opportunity to do more, and I suspect they are hoping to do more with MIR, but at the moment they rely on LLVM to optimize out all of the zero-cost abstractions that they introduce.
https://github.com/rust-lang-nursery/rust-forge/blob/master/... is how you're supposed to do this these days. It's a ton of work that I don't have time to do right now, but if you look at the example HTML output linked there, for a hello world, my broader point still stands, which is "translation 78.1%". That is, taking the MIR and turning it into machine code, first through LLVM IR, is the vast, vast majority of the compile time. Not the safety checks, not some un-optimized algorithm in them.
-------------------------------------
To make this concrete, here's a project I'm working on, with -Z time-passes: https://gist.github.com/steveklabnik/c2646b209debf1f66355343...
Some annotated bits of the larger passes:
time: 0.646; rss: 91MB expansion
time: 0.338; rss: 169MB coherence checking
time: 0.596; rss: 205MB item-bodies checking
time: 0.588; rss: 219MB borrow checking
time: 2.566; rss: 220MB MIR borrow checking
Then we get into a ton of LLVM passes. As you can see, most of them take basically no time. Ones that stick out are mostly codegen passes, which is what I was referring to with my comments above. But then we have:
time: 5.625; rss: 413MB translate to LLVM IR
time: 7.418; rss: 415MB LLVM passes
time: 9.437; rss: 414MB translation
Note that all of this is for an initial, clean build, so a lot of that stuff is setting up incremental builds. I deleted src, git checked it out, and then built again, and got this: https://gist.github.com/steveklabnik/1ed07751c563810b515db3f... way, way, way less work, and a faster build time overall: just five seconds.
So, anyway, yeah.
Right - my understanding is that Rust generates very large MIR and also LLVM IR because the "zero-cost abstractions" aren't yet zero-cost, and compiling them into zero-cost machine code is inherently expensive.
So it's not the safety checks per se, but it's things like "there are three wrapper objects here with various generic parameters where C/C++ would have started with just a pointer from the beginning". Those three wrapper objects couldn't have existed without the safety checks, and rustc very quickly identified that everything is in order, but then it monomorphized the generics into lots of tiny functions and LLVM has to optimize all of that into machine code that resembles what the (unsafe) pointer approach would have generated. (Which explains why it's not time taken in rustc proper, but also why we don't see LLVM being equally slow when compiling C/C++.)
Is that interpretation correct?
I might split out C++ from C here though; template-heavy C++ is known to be pretty slow to compile too, for what's basically similar reasons: you end up generating a bunch of code that needs to be crunched down.
There's also some possibly deeper reasons around heavy use of generics: if your code touches something that is generic, and you change the type, it's going to need to recompile that function too. And then anything generic it touches. Etc. Trait objects can help compile times for this reason, but they aren't considered idiomatic, so most Rust code tends to stress the compiler in this way.
Other languages with powerful generics and type inference like modern C# clearly manage just fine, too.
It is also the only deployment option on iDevices and Windows Store since Windows 8.
Also if you prefer other native examples, Ada, Eiffel, Sather, D come to mind.
They are actually, but only anecdotically (like PowerPoint is also Turing Complete).
AOT Java compilers certainly exist, but I don't recall Microsoft having one -- I fully admit my recollection of their Java dev environment is quite foggy at this point, though.
Regardless, the Java AOT compilers I've tried didn't seem particularly fast in relation to their level of optimization.