13 ms·

> Incremental compilation! 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 (

> Incremental compilation! 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.

pcwalton 9y ago
> There were compilers in the 90s which ran a million lines per second (on much slower computers). 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.
- civility 9y ago
  Not going to budge an inch, eh? It must be as good as it will ever get.
  - pcwalton 9y ago
    I don't know what this means.
    - civility 9y ago
      It means things don't usually get better until you admit they're not as good as they can be.
      - sametmax 9y ago
        The rust compiler provide huge guaranties no other provide, like for memory safety. This has a performance impact.
        cakoose 9y ago
        The memory safety checking (or more generally, the type checking) isn't what makes the compiler slow. That part is pretty fast because it's intentionally modular. 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.
      - coldtea 9y ago
        I hope you see the irony in accusing them of that in a post announcing that the compiler just got better.
        civility 9y ago
        It's not ironic. I see this kind of thing all the time. Rather than cleanup and speedup an implementation, engineers will make it multi-threaded or send it off to a GPU, generally achieving limited improvements and greater complexity. In this case, rather than make the compiler faster, they hack it up with incremental compilation. It's still slow, but they apply the slow code to less data and call it a win.
        pcwalton 9y ago
        Nobody who reads the rustc commit history would agree that this is what is going on. The number of straightforward changes that are constantly made in the service of small performance improvements far outweighs the work on incremental compilation.
      - ComputerGuru 9y ago
        I’m pretty sure no one in their right mind claims that rustc is “as good as can be.” It’s called incremental progress.
  - coldtea 9y ago
    Is it they who didn't "budge an inch", or you, that despite a reasoned explanation, insist on the original accusation? 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.
    - deleted 9y ago
      [deleted]
    - civility 9y ago
      My criticisms are meant to point out areas for actual improvement. 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.
      - pcwalton 9y ago
        Borrow checking is a lot more involved than const correctness. It's not even in the same league. Const correctness just adds a few more types, whereas borrow checking involves generating sets of constraints and solving them with a constraint solver, something C++ doesn't really have to do at all. 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...
- frankmcsherry 9y ago
  > Those compilers performed nowhere near the level of optimization that modern compilers do. 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.
  - civility 9y ago
    > I think this gets at Wirth's law a bit. 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.
- pjmlp 9y ago
  Have you guys spend any time with the incremental compilation and linking of Visual C++ or C++ Builder? It really does make a difference versus traditional UNIX compilers.
- Q6T46nT668w6i3m 9y ago
  clang++ is slow, but it certainly feels faster compared to rustc (and I typically use the write everything in one include C++ style). I’m curious, has there been any outreach to the clang community about rustc performance issues?
steveklabnik 9y ago
It's not a big-O thing. The optimization passes aren't necessarily huge either; right now, 50% of the time is in LLVM compiling IR -> machine code. The static checks, optimization passes, and everything else are minuscule overall. You can see this with -Z time-passes. 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.
- Shoop 9y ago
  Is there a way to generate IR which is easier on LLVM? The Jai compiler compiles 60kloc with an llvm backend in seconds. Could performance like this be seen in rustc?
  - steveklabnik 9y ago
    Possibly; we'll see. MIR optimization passes may help. It's hard to say what exactly Jai does since it's not public yet.
  - e12e 9y ago
    Apparently that's : https://inductive.no/jai/ https://inductive.no/jai/
- civility 9y ago
  > Don't forget the differences in compilation model; C/C++'s compilation units are much smaller 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.
  - pcwalton 9y ago
    How much code did the preprocessor strip out?
nerpderp83 9y ago
Those languages were Wirthian, and were designed for fast compilation.
- civility 9y ago
  Oberon certainly compiles quickly, and I believe Delphi (Pascal-ish) was fast too, but I was thinking of Microsoft's Java compiler before they got spanked.
  - nine_k 9y ago
    Java without generics used to compile pretty fast. 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.
    - civility 9y ago
      Below, steveklabnik claims these things are miniscule. Are you really sure you know what is actually slow?
      - frankmcsherry 9y ago
        In my experience (with Rust programs that take 20mins+) it is all about the monomorphisation of generics. The great majority of the time is spent in LLVM, because Rust hands over many GB of LLVM IR for optimization, having done not very much (edit: in the way of code transformation) other than direct instantiation of the generic parameters. 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.
      - geofft 9y ago
        If you're referring to the comment starting with "It's not a big-O thing," I think that comment says the opposite. "Generics, lifetimes, and type inference" aren't "static checks and optimization passes" (within rustc)—he says the bulk of the work is LLVM dealing with the quantity of IR rustc generates, which is exactly what you'd expect from having heavy source-level abstractions like generics and type-heavy patterns like libstd's approach to iterators that all need to be compiled out.

pcwalton 9y ago

> There were compilers in the 90s which ran a million lines per second (on much slower computers). 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.

civility 9y ago
Not going to budge an inch, eh? It must be as good as it will ever get.
- pcwalton 9y ago
  I don't know what this means.
  - civility 9y ago
    It means things don't usually get better until you admit they're not as good as they can be.
    - sametmax 9y ago
      The rust compiler provide huge guaranties no other provide, like for memory safety. This has a performance impact.
      - cakoose 9y ago
        The memory safety checking (or more generally, the type checking) isn't what makes the compiler slow. That part is pretty fast because it's intentionally modular. 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.
    - coldtea 9y ago
      I hope you see the irony in accusing them of that in a post announcing that the compiler just got better.
      - civility 9y ago
        It's not ironic. I see this kind of thing all the time. Rather than cleanup and speedup an implementation, engineers will make it multi-threaded or send it off to a GPU, generally achieving limited improvements and greater complexity. In this case, rather than make the compiler faster, they hack it up with incremental compilation. It's still slow, but they apply the slow code to less data and call it a win.
        pcwalton 9y ago
        Nobody who reads the rustc commit history would agree that this is what is going on. The number of straightforward changes that are constantly made in the service of small performance improvements far outweighs the work on incremental compilation.
    - ComputerGuru 9y ago
      I’m pretty sure no one in their right mind claims that rustc is “as good as can be.” It’s called incremental progress.
- coldtea 9y ago
  Is it they who didn't "budge an inch", or you, that despite a reasoned explanation, insist on the original accusation? 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.
  - deleted 9y ago
    [deleted]
  - civility 9y ago
    My criticisms are meant to point out areas for actual improvement. 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.
    - pcwalton 9y ago
      Borrow checking is a lot more involved than const correctness. It's not even in the same league. Const correctness just adds a few more types, whereas borrow checking involves generating sets of constraints and solving them with a constraint solver, something C++ doesn't really have to do at all. 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...
frankmcsherry 9y ago
> Those compilers performed nowhere near the level of optimization that modern compilers do. 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.
- civility 9y ago
  > I think this gets at Wirth's law a bit. 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.
pjmlp 9y ago
Have you guys spend any time with the incremental compilation and linking of Visual C++ or C++ Builder? It really does make a difference versus traditional UNIX compilers.
Q6T46nT668w6i3m 9y ago
clang++ is slow, but it certainly feels faster compared to rustc (and I typically use the write everything in one include C++ style). I’m curious, has there been any outreach to the clang community about rustc performance issues?

steveklabnik 9y ago

It's not a big-O thing. The optimization passes aren't necessarily huge either; right now, 50% of the time is in LLVM compiling IR -> machine code. The static checks, optimization passes, and everything else are minuscule overall. You can see this with -Z time-passes. 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.

Shoop 9y ago
Is there a way to generate IR which is easier on LLVM? The Jai compiler compiles 60kloc with an llvm backend in seconds. Could performance like this be seen in rustc?
- steveklabnik 9y ago
  Possibly; we'll see. MIR optimization passes may help. It's hard to say what exactly Jai does since it's not public yet.
- e12e 9y ago
  Apparently that's : https://inductive.no/jai/ https://inductive.no/jai/
civility 9y ago
> Don't forget the differences in compilation model; C/C++'s compilation units are much smaller 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.
- pcwalton 9y ago
  How much code did the preprocessor strip out?

nerpderp83 9y ago

Those languages were Wirthian, and were designed for fast compilation.

civility 9y ago
Oberon certainly compiles quickly, and I believe Delphi (Pascal-ish) was fast too, but I was thinking of Microsoft's Java compiler before they got spanked.
- nine_k 9y ago
  Java without generics used to compile pretty fast. 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.
  - civility 9y ago
    Below, steveklabnik claims these things are miniscule. Are you really sure you know what is actually slow?
    - frankmcsherry 9y ago
      In my experience (with Rust programs that take 20mins+) it is all about the monomorphisation of generics. The great majority of the time is spent in LLVM, because Rust hands over many GB of LLVM IR for optimization, having done not very much (edit: in the way of code transformation) other than direct instantiation of the generic parameters. 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.
    - geofft 9y ago
      If you're referring to the comment starting with "It's not a big-O thing," I think that comment says the opposite. "Generics, lifetimes, and type inference" aren't "static checks and optimization passes" (within rustc)—he says the bulk of the work is LLVM dealing with the quantity of IR rustc generates, which is exactly what you'd expect from having heavy source-level abstractions like generics and type-heavy patterns like libstd's approach to iterators that all need to be compiled out.