7 ms·

> Compile time of this really simple example takes 2.85 seconds longer than the “simple C++” version. Haskell, Rust, Scala etc. also have a lot of trouble with

> Compile time of this really simple example takes 2.85 seconds longer than the “simple C++” version. Haskell, Rust, Scala etc. also have a lot of trouble with compile times. I wonder why, though - is it just a matter of priorities being placed on things other than optimizing the compiler, or is there some actual, inherent complexity in compiling these "modern" languages that doesn't apply to C or Go? (I suspect mostly the former, FWIW).

kzrdude 8y ago
Isn't it more about what the typical program looks like? The generic languages like Rust and C++ generate a ton of functions, wrapper types, and indirections that need to be seen through and mostly removed by the compiler. In C++, when compiling: for (; *it; ++it) { } it may look simple but deref is a function you insert (deref operator), `++it` is a function and so it continues on, with new function to generate each time it's a different iterator or even the same iterator with different template parameters.
steveklabnik 8y ago
With Rust, a lot of the issue is monomorphization. Changing one line may make hundreds of lines be needed to recompile. Additionally, we produce more LLVM IR than we must, and rely on LLVM ago boil it away. It’s a complex set of issues that we’re constantly working on. (So yes, Go and C do not have generics, and so do not have this problem.)
- jules 8y ago
  Do you know what's causing that? 1. Maybe monomorphisation overduplicates code, so that different invocations produce the same machine code in the end? 2. If that's not happening, maybe idiomatic Rust code causes a lot of code to be generated where a C programmer would have written something differently, e.g. using a void* instead of passing by value? 3. If that's not happening either, maybe monomorphisation is more or less producing what a C programmer would have monomorphised manually, but it takes the compiler a long time to optimise away abstractions? It seems that in this C++ example the problem is #3: it takes a long time to optimise away the range & lambda abstraction.
  - steveklabnik 8y ago
    It’s all three.
- Gibbon1 8y ago
  Stupid question from a small brained primate. Would it make sense to have two types of generic implementation with a boxing unboxing mechanism. AKA a fast one that requires a rebuild when you monkey with something. And a slow one that doesn't but compiles fast. I think it'd be acceptable if the 'dev' version used GC as long as the final build didn't. Basically anyway to get the development cycle to go fast.
  - steveklabnik 8y ago
    Not stupid! You wouldn’t need a GC to do this either. It’s been talked about but nobody has tried to implement it.
  - mpolun 8y ago
    Rust actually has that they just can't be substituted automatically because they're different types: fn<T: MyTrait> compile_time(thing: &T) {} fn run_time(thing: &dyn MyTrait) {} The reason that you can't just substitute them is that you can do more with compile-time generics than runtime ones -- runtime generics have unknown size (different concrete types have different size, so what size is the runtime generic version?) so they always have to be used through a pointer (and usually heap allocated). There are a variety of other restrictions on trait objects (runtime generics) for type-system reasons. It would be possible to find cases where compile time polymorphism is replaced with runtime polymorphism, but I'm not sure it would really gain much given the restrictions. Now if you start changing the language semantics a lot more becomes possible, but I don't even know what changes you would have to make to the language to let that happen.
    - renox 8y ago
      That's when Jai (if it ever becomes real) hold promise: fast compilation is a first rate goal, not a second rate goal where you decide language features first then try to make the compiler "not too slow".
  - thechao 8y ago
    Almost like combining Siek’s gradual types with parametric polymorphism: you can search for “gradual parametricity” and find a number of papers on the topic.
- pjmlp 8y ago
  C does have a kind of lightweight generics since C11.
  - steveklabnik 8y ago
    Sure, but I’m not aware of them being used in any significant capacity, so I don’t think it’s particilary pertinent to this discussion.
    - pjmlp 8y ago
      Ah, in that regard you are right, I guess.
  - fanf2 8y ago
    Sadly C’s `_Generic` typecase mechanism does not do SFINAE: all the branches have to typecheck OK, regardless of which one is selected. This is OK for <tgmath.h> where the cases are different sizes of float, where there are few opportunities to get different failures in the different cases, but it makes _Generic hard to use for more template-like code.
    - pjmlp 8y ago
      Given how hard SFINAE is to understand for typical developers, I consider it a good thing, actually.
- vmarsy 8y ago
  is monomorphization a more concise term for what is called "implicit template instantiation" in C++? If so, is Rust worse than C++ when it comes to compile times of those? Heavily templated C++ code is known to be slow to compile due to this. Is it much worse in Rust? Are you aware whether C++ compilers do some special optimizations that Rust compiler doesn't have yet? I don't see what can be done to make this better, the whole point of templates is to "pay" at compile time for some gains at runtime. (or in this case for gains in the amount of code a developer has to write)
  - steveklabnik 8y ago
    “Monomorphization” is what happens when a template is instantiated. It’s essentially the same thing in both languages, and has roughly the same compiler performance implications. There’s at least one thing that could be done, in Rust at least. But it’s only in some limited circumstances. See here: http://www.suspectsemantics.com/blog/2016/12/03/monomorphization-bloat/ http://www.suspectsemantics.com/blog/2016/12/03/monomorphiza...
    - vmarsy 8y ago
      Thanks, that's an interesting read. indeed a developer can use that trick "in the case of conversion traits". Monomorphization seems to be the source of 2 major problems: compile time, and binary size. An optimization that could reduce the compile time by caching the generated code (at least when compiling over-and-over the same code base. i.e. "Incremental compilation") - and it seems that Rust already is doing something with it [1]. I wonder if something specific is done for template instantiations there. Optimizations aimed at reducing binary size seems much more tricky, if not impossible, except as you pointed out in the limited cases described above. In the regular cases, templates are kind of working as intended: the developer has to think if he/she would have written the same amount of code N times if templates were non existent. [1] https://blog.rust-lang.org/2016/09/08/incremental.html https://blog.rust-lang.org/2016/09/08/incremental.html
    - strmpnk 8y ago
      The translation units in C++ tend to pay this cost a number of times over because of the way header files are processed. With modules, this theoretically could start getting closer to Rust, but for large projects, C++ templates can still be orders of magnitude worse in terms of instantiation cost. This is partly why there are hacks like unity builds (not related to the engine, where all source is bundled into a single translation unit). These have plenty of drawbacks too so it's not a clear win. Adding to all of this, there are fancier mechanisms for template meta-programming like SFINAE rules + computed template values. Sure, it's "turing complete" but this is why we see such clever libraries with huge explosions in code generation size. I'm far from an expert in modern C++ features but it's clear that there is an entire interpreted programming language of templates bolted on the to the rest of C++. It reminds me of this post on a similar take on Haskell type level programming: https://aphyr.com/posts/342-typing-the-technical-interview https://aphyr.com/posts/342-typing-the-technical-interview (or similar feats by Oleg Kiselyov).
erik_seaberg 8y ago
It must be different ways people work. I can't imagine caring that my integration test suite might get 0.05 minutes slower. Edit: especially if that 3 s pays for generating code that nobody has to write correctly or ever look at.
zmj 8y ago
Fast compilation was an explicit design goal for Go: https://talks.golang.org/2012/splash.article#TOC_4 https://talks.golang.org/2012/splash.article#TOC_4.
JulianMorrison 8y ago
My feeling is that at least in C++ and Haskell, what's going on is that a barebones language core is being extended with a teetering tower of mutually dependent libraries building ever deeper abstractions. Templates upon templates, or monads upon monads. Whereas in Go, say, stuff like ranges and maps is just built in, no more abstraction than is necessary to do a generalist job with a few specialised common cases. Even the standard library is largely one-level, direct code, and only abstract at the interfaces. So simply and literally, C++ has to compile more lines of code to do the thing.
- gumby 8y ago
  This was of course one of the key differentiators of C; one of my favorite lines in the original K&R book was "what? I have to call a function to do I/O?" C was unusual that so much of it was in its libraries rather than being built in. Programming language design in those days didn't have the clean differentiation we have today.. or perhaps did: it's fascinating to see the arc bend back.
  - JulianMorrison 8y ago
    Being in libraries or in the language isn't so much the thing, because really the language is just calling into a hidden library. It's more being directly written, versus being composed of Legos that are themselves composed of Legos... that ends up drawing in a hundred thousand lines of ultra generalist code and then pre-specializing it.
  - int_19h 8y ago
    It predates C tho. In Simula-67, not only I/O was in functions, it was in methods (on file objects). In Pascal, it was also all functions, also some of those were magic (e.g. overloaded on types, in a way user-defined functions couldn't be) - but it still described them as functions.
    - gumby 8y ago
      I said unusual not unique, but perhaps I should have been clearer. Pascal and C were definitely influenced by Simula, a language ahead of its time. When K&R wrote that line I suspect they were thinking more of PL/1 which was the Multics implementation language. Though it has OPEN/CLOSE etc they were keywords not external labels. I think it’s pretty likely K had heard of Pascal at the time. More interestingly BCPL’s i/o was via library rather than innate. And c descends directly from BCPL (->b->c) rather than from PL/1; simula-67 and BCPL were developed contemporaneously in Europe. Again, apologies for my prior brevity.
pjmlp 8y ago
It also does not apply to .NET Native, Delphi, Ada, Eiffel for example. On Haskell's case it depends on which compiler backend you are actually using. So yes, it is a matter of effort spent in the code compilation, specially if the language does support modules.

kzrdude 8y ago

Isn't it more about what the typical program looks like? The generic languages like Rust and C++ generate a ton of functions, wrapper types, and indirections that need to be seen through and mostly removed by the compiler. In C++, when compiling: for (; *it; ++it) { } it may look simple but deref is a function you insert (deref operator), `++it` is a function and so it continues on, with new function to generate each time it's a different iterator or even the same iterator with different template parameters.

steveklabnik 8y ago

With Rust, a lot of the issue is monomorphization. Changing one line may make hundreds of lines be needed to recompile. Additionally, we produce more LLVM IR than we must, and rely on LLVM ago boil it away. It’s a complex set of issues that we’re constantly working on. (So yes, Go and C do not have generics, and so do not have this problem.)

jules 8y ago
Do you know what's causing that? 1. Maybe monomorphisation overduplicates code, so that different invocations produce the same machine code in the end? 2. If that's not happening, maybe idiomatic Rust code causes a lot of code to be generated where a C programmer would have written something differently, e.g. using a void* instead of passing by value? 3. If that's not happening either, maybe monomorphisation is more or less producing what a C programmer would have monomorphised manually, but it takes the compiler a long time to optimise away abstractions? It seems that in this C++ example the problem is #3: it takes a long time to optimise away the range & lambda abstraction.
- steveklabnik 8y ago
  It’s all three.
Gibbon1 8y ago
Stupid question from a small brained primate. Would it make sense to have two types of generic implementation with a boxing unboxing mechanism. AKA a fast one that requires a rebuild when you monkey with something. And a slow one that doesn't but compiles fast. I think it'd be acceptable if the 'dev' version used GC as long as the final build didn't. Basically anyway to get the development cycle to go fast.
- steveklabnik 8y ago
  Not stupid! You wouldn’t need a GC to do this either. It’s been talked about but nobody has tried to implement it.
- mpolun 8y ago
  Rust actually has that they just can't be substituted automatically because they're different types: fn<T: MyTrait> compile_time(thing: &T) {} fn run_time(thing: &dyn MyTrait) {} The reason that you can't just substitute them is that you can do more with compile-time generics than runtime ones -- runtime generics have unknown size (different concrete types have different size, so what size is the runtime generic version?) so they always have to be used through a pointer (and usually heap allocated). There are a variety of other restrictions on trait objects (runtime generics) for type-system reasons. It would be possible to find cases where compile time polymorphism is replaced with runtime polymorphism, but I'm not sure it would really gain much given the restrictions. Now if you start changing the language semantics a lot more becomes possible, but I don't even know what changes you would have to make to the language to let that happen.
  - renox 8y ago
    That's when Jai (if it ever becomes real) hold promise: fast compilation is a first rate goal, not a second rate goal where you decide language features first then try to make the compiler "not too slow".
- thechao 8y ago
  Almost like combining Siek’s gradual types with parametric polymorphism: you can search for “gradual parametricity” and find a number of papers on the topic.
pjmlp 8y ago
C does have a kind of lightweight generics since C11.
- steveklabnik 8y ago
  Sure, but I’m not aware of them being used in any significant capacity, so I don’t think it’s particilary pertinent to this discussion.
  - pjmlp 8y ago
    Ah, in that regard you are right, I guess.
- fanf2 8y ago
  Sadly C’s `_Generic` typecase mechanism does not do SFINAE: all the branches have to typecheck OK, regardless of which one is selected. This is OK for <tgmath.h> where the cases are different sizes of float, where there are few opportunities to get different failures in the different cases, but it makes _Generic hard to use for more template-like code.
  - pjmlp 8y ago
    Given how hard SFINAE is to understand for typical developers, I consider it a good thing, actually.
vmarsy 8y ago
is monomorphization a more concise term for what is called "implicit template instantiation" in C++? If so, is Rust worse than C++ when it comes to compile times of those? Heavily templated C++ code is known to be slow to compile due to this. Is it much worse in Rust? Are you aware whether C++ compilers do some special optimizations that Rust compiler doesn't have yet? I don't see what can be done to make this better, the whole point of templates is to "pay" at compile time for some gains at runtime. (or in this case for gains in the amount of code a developer has to write)
- steveklabnik 8y ago
  “Monomorphization” is what happens when a template is instantiated. It’s essentially the same thing in both languages, and has roughly the same compiler performance implications. There’s at least one thing that could be done, in Rust at least. But it’s only in some limited circumstances. See here: http://www.suspectsemantics.com/blog/2016/12/03/monomorphization-bloat/ http://www.suspectsemantics.com/blog/2016/12/03/monomorphiza...
  - vmarsy 8y ago
    Thanks, that's an interesting read. indeed a developer can use that trick "in the case of conversion traits". Monomorphization seems to be the source of 2 major problems: compile time, and binary size. An optimization that could reduce the compile time by caching the generated code (at least when compiling over-and-over the same code base. i.e. "Incremental compilation") - and it seems that Rust already is doing something with it [1]. I wonder if something specific is done for template instantiations there. Optimizations aimed at reducing binary size seems much more tricky, if not impossible, except as you pointed out in the limited cases described above. In the regular cases, templates are kind of working as intended: the developer has to think if he/she would have written the same amount of code N times if templates were non existent. [1] https://blog.rust-lang.org/2016/09/08/incremental.html https://blog.rust-lang.org/2016/09/08/incremental.html
  - strmpnk 8y ago
    The translation units in C++ tend to pay this cost a number of times over because of the way header files are processed. With modules, this theoretically could start getting closer to Rust, but for large projects, C++ templates can still be orders of magnitude worse in terms of instantiation cost. This is partly why there are hacks like unity builds (not related to the engine, where all source is bundled into a single translation unit). These have plenty of drawbacks too so it's not a clear win. Adding to all of this, there are fancier mechanisms for template meta-programming like SFINAE rules + computed template values. Sure, it's "turing complete" but this is why we see such clever libraries with huge explosions in code generation size. I'm far from an expert in modern C++ features but it's clear that there is an entire interpreted programming language of templates bolted on the to the rest of C++. It reminds me of this post on a similar take on Haskell type level programming: https://aphyr.com/posts/342-typing-the-technical-interview https://aphyr.com/posts/342-typing-the-technical-interview (or similar feats by Oleg Kiselyov).

erik_seaberg 8y ago

It must be different ways people work. I can't imagine caring that my integration test suite might get 0.05 minutes slower. Edit: especially if that 3 s pays for generating code that nobody has to write correctly or ever look at.

zmj 8y ago

Fast compilation was an explicit design goal for Go: https://talks.golang.org/2012/splash.article#TOC_4 https://talks.golang.org/2012/splash.article#TOC_4.

JulianMorrison 8y ago

My feeling is that at least in C++ and Haskell, what's going on is that a barebones language core is being extended with a teetering tower of mutually dependent libraries building ever deeper abstractions. Templates upon templates, or monads upon monads. Whereas in Go, say, stuff like ranges and maps is just built in, no more abstraction than is necessary to do a generalist job with a few specialised common cases. Even the standard library is largely one-level, direct code, and only abstract at the interfaces. So simply and literally, C++ has to compile more lines of code to do the thing.

gumby 8y ago
This was of course one of the key differentiators of C; one of my favorite lines in the original K&R book was "what? I have to call a function to do I/O?" C was unusual that so much of it was in its libraries rather than being built in. Programming language design in those days didn't have the clean differentiation we have today.. or perhaps did: it's fascinating to see the arc bend back.
- JulianMorrison 8y ago
  Being in libraries or in the language isn't so much the thing, because really the language is just calling into a hidden library. It's more being directly written, versus being composed of Legos that are themselves composed of Legos... that ends up drawing in a hundred thousand lines of ultra generalist code and then pre-specializing it.
- int_19h 8y ago
  It predates C tho. In Simula-67, not only I/O was in functions, it was in methods (on file objects). In Pascal, it was also all functions, also some of those were magic (e.g. overloaded on types, in a way user-defined functions couldn't be) - but it still described them as functions.
  - gumby 8y ago
    I said unusual not unique, but perhaps I should have been clearer. Pascal and C were definitely influenced by Simula, a language ahead of its time. When K&R wrote that line I suspect they were thinking more of PL/1 which was the Multics implementation language. Though it has OPEN/CLOSE etc they were keywords not external labels. I think it’s pretty likely K had heard of Pascal at the time. More interestingly BCPL’s i/o was via library rather than innate. And c descends directly from BCPL (->b->c) rather than from PL/1; simula-67 and BCPL were developed contemporaneously in Europe. Again, apologies for my prior brevity.

pjmlp 8y ago

It also does not apply to .NET Native, Delphi, Ada, Eiffel for example. On Haskell's case it depends on which compiler backend you are actually using. So yes, it is a matter of effort spent in the code compilation, specially if the language does support modules.