<p>No one likes waiting around for minutes (or even hours!) for their programs to compile. When designing languages, we should be cognizant that some features may require more work to parse and understand and thus lead to longer waiting times. What kinds of features are especially susceptible to causing it take drastically longer to compile a program that uses the feature?</p>

<compilers>
What kinds of features lead to long compilation times?
CC BY-SA 4.0
2023-05-18T03:37:58.943Z
Turing-complete syntax.  When distinguishing valid and invalid programs require solving the halting problem, compiling takes a while.
Mark
<p>Let's take Rust as an example. It's well known that the Rust compiler takes a while to build a sizeable project, and Rust has at least a typical amount of static analysis to do, but the compiler itself is implemented fairly efficiently (in Rust itself, so it compiles to an optimised native binary).</p>
<p>I'll use my own compiler, <a href="https://github.com/kaya3/papyri-rs" rel="nofollow noreferrer">Papyri</a>, as a quick benchmark since it's a moderately-sized Rust project which I have immediately available; it uses a decent number of third-party crates (download time not included in the results below) and macros, so it should cover a decent proportion of what the Rust compiler has to do when building a project. I'll also do a <code>cargo clean</code> before each command so that cached builds don't affect the results.</p>
<ul>
<li><p>All of the analyses ─ type checking, borrow checking, reachability, and so on ─ can be run separately with the <code>cargo check</code> command. This takes about 7 seconds, but a good chunk of this time is spent compiling and checking the dependencies, so a lot of this isn't necessarily <em>just</em> doing the checks. This also includes the time taken for parsing, of course.</p>
<p>For what it's worth, <code>cargo check</code> without a <code>cargo clean</code> first, so it's only checking the project source files and not any third party code, takes about 0.13s.</p>
</li>
<li><p>A debug build, which does all of the same static checks, plus code generation but no optimisations, takes 11.03s.</p>
</li>
<li><p>A full release build, with code generation and optimisations, takes 24.55s.</p>
</li>
</ul>
<p>So roughly speaking, more than half of the time is spent just on optimisations (including link-time optimisations, which are enabled here). Of the rest, a big chunk is spent on code generation, and probably significantly less is spent on static checking, but it's hard to tell because I can't do a <code>cargo check</code> without both checking <em>and</em> compiling the third-party libraries.</p>
<p>Of course, <em>every</em> compiler must do some code generation by definition, but Rust's code generation is potentially slower than other compilers because it generates LLVM IR and then invokes LLVM on that, so there'll be a whole extra set of parsing and checking that LLVM does before its own code generation. For the rest of what the compiler does, it should be fair to say that doing more optimisations will have a much greater effect on compile times than doing more static checks. This makes sense: most static checks can be done with just one or two passes over the source code in linear time, but optimisation problems can be as computationally intensive as you're willing to go, due to <a href="https://en.wikipedia.org/wiki/Combinatorial_explosion" rel="nofollow noreferrer">combinatorial explosion</a>.</p>
<p>All of that said, if your own compiler is slow and you want to find out why, you should experiment to find out. You can try running just some parts of the build (e.g. checking but no code generation) like I did above to get a broad idea, or use a profiler if you want to narrow it down to particular places in your code. It's often the case that just one analysis, or just one or two optimisations out of hundreds, can account for the bulk of the time.</p>

CC BY-SA 4.0
2023-05-18T03:12:23.577Z
2023-05-18T04:46:43.450Z
2023-05-18T04:46:43.450Z
kaya3
<h1>Complicated Type Systems</h1>
<p>The more complicated type systems get, the harder and longer type checking is. This is especially, but not exclusively, the case with turing complete type systems. With a turing complete type system, it's usually easy enough to get the typical case to work, purposefully causing a significant slowdown is trivial, and running into slow edge cases naturally does happen as well.</p>
<p>Additionally, these complicated type systems generally occur in languages with static dispatch, which tends to cause monomorphization costs to balloon, especially when optimization happens in the backend after monomorphization happens. The Rust programming language is a perfect example of this phenomenon- the fact that optimizations in the front end are starting to show up is a huge deal compile time-wise because it saves the LLVM back end the effort of doing those same optimizations but a bunch more times because LLVM operates on the code after monomorphization.</p>

CC BY-SA 4.0
2023-05-18T03:34:13.737Z
2023-05-18T04:15:46.330Z
2023-05-18T04:15:46.330Z
Aiden4
<p>The more work a compiler does, the longer the compilation time: templates, Hindley Milner, borrow checking, optimizers etc.</p>
<p>Some actions are literally NP hard, like register allocation. These require heuristics.</p>
<p>And then there are language-specific quirks like how the C pre-processor must open files during “#include”, which means potentially touching the same file over and over.</p>

CC BY-SA 4.0
2023-05-18T02:30:30.903Z
2023-05-18T02:30:30.903Z
chrisaycock
<h1>Header files</h1>
<p>The headers files system in C/C++ is a big reason for long compilation times. Quote from <a href="https://stackoverflow.com/a/318440/14193797">this answer</a> for <a href="https://stackoverflow.com/q/318398/14193797">Why does C++ compilation take so long?</a></p>
<blockquote>
<p>Every single compilation unit requires hundreds or even thousands of
headers to be (1) loaded and (2) compiled. Every one of them typically
has to be recompiled for every compilation unit, because the
preprocessor ensures that the result of compiling a header might vary
between every compilation unit. (A macro may be defined in one
compilation unit which changes the content of the header).</p>
<p>This is probably the main reason, as it requires huge amounts of code
to be compiled for every compilation unit, and additionally, every
header has to be compiled multiple times (once for every compilation
unit that includes it).</p>
</blockquote>
<p>For alternatives, you can either precompile the headers (which can be difficult to maintain) or use the modules system (which C++20 <a href="https://en.cppreference.com/w/cpp/language/modules" rel="nofollow noreferrer">implemented</a>).</p>

CC BY-SA 4.0
2023-05-18T02:31:01.010Z
2023-05-18T02:31:01.010Z
justANewbie
CC BY-SA 4.0
2023-09-07T21:33:49.570Z
Another approach would be to allow one source file to be treated as multiple compilation units, rewinding the symbol table state at the end of each compilation unit to some particular marked state within the previous one.
supercat
# What kinds of features lead to long compilation times?
Posted by: username_0 on 2023-05-18
No one likes waiting around for minutes (or even hours!) for their programs to compile. When designing languages, we should be cognizant that some features may require more work to parse and understand and thus lead to longer waiting times. What kinds of features are especially susceptible to causing it take drastically longer to compile a program that uses the feature?
**Tags:** compilers
> **Comments:**
> **username_1**: Turing-complete syntax.  When distinguishing valid and invalid programs require solving the halting problem, compiling takes a while.  
---
## 4 answers
### Answer by username_2 on 2023-05-18. Score: 3 | Accepted answer
Let's take Rust as an example. It's well known that the Rust compiler takes a while to build a sizeable project, and Rust has at least a typical amount of static analysis to do, but the compiler itself is implemented fairly efficiently (in Rust itself, so it compiles to an optimised native binary).

I'll use my own compiler, [Papyri](https://github.com/kaya3/papyri-rs), as a quick benchmark since it's a moderately-sized Rust project which I have immediately available; it uses a decent number of third-party crates (download time not included in the results below) and macros, so it should cover a decent proportion of what the Rust compiler has to do when building a project. I'll also do a `cargo clean` before each command so that cached builds don't affect the results.

* All of the analyses ─ type checking, borrow checking, reachability, and so on ─ can be run separately with the `cargo check` command. This takes about 7 seconds, but a good chunk of this time is spent compiling and checking the dependencies, so a lot of this isn't necessarily *just* doing the checks. This also includes the time taken for parsing, of course.

  For what it's worth, `cargo check` without a `cargo clean` first, so it's only checking the project source files and not any third party code, takes about 0.13s.
* A debug build, which does all of the same static checks, plus code generation but no optimisations, takes 11.03s.
* A full release build, with code generation and optimisations, takes 24.55s.

So roughly speaking, more than half of the time is spent just on optimisations (including link-time optimisations, which are enabled here). Of the rest, a big chunk is spent on code generation, and probably significantly less is spent on static checking, but it's hard to tell because I can't do a `cargo check` without both checking *and* compiling the third-party libraries.

Of course, *every* compiler must do some code generation by definition, but Rust's code generation is potentially slower than other compilers because it generates LLVM IR and then invokes LLVM on that, so there'll be a whole extra set of parsing and checking that LLVM does before its own code generation. For the rest of what the compiler does, it should be fair to say that doing more optimisations will have a much greater effect on compile times than doing more static checks. This makes sense: most static checks can be done with just one or two passes over the source code in linear time, but optimisation problems can be as computationally intensive as you're willing to go, due to [combinatorial explosion](https://en.wikipedia.org/wiki/Combinatorial_explosion).

All of that said, if your own compiler is slow and you want to find out why, you should experiment to find out. You can try running just some parts of the build (e.g. checking but no code generation) like I did above to get a broad idea, or use a profiler if you want to narrow it down to particular places in your code. It's often the case that just one analysis, or just one or two optimisations out of hundreds, can account for the bulk of the time.
---
### Answer by username_3 on 2023-05-18. Score: 11
# Complicated Type Systems

The more complicated type systems get, the harder and longer type checking is. This is especially, but not exclusively, the case with turing complete type systems. With a turing complete type system, it's usually easy enough to get the typical case to work, purposefully causing a significant slowdown is trivial, and running into slow edge cases naturally does happen as well.

Additionally, these complicated type systems generally occur in languages with static dispatch, which tends to cause monomorphization costs to balloon, especially when optimization happens in the backend after monomorphization happens. The Rust programming language is a perfect example of this phenomenon- the fact that optimizations in the front end are starting to show up is a huge deal compile time-wise because it saves the LLVM back end the effort of doing those same optimizations but a bunch more times because LLVM operates on the code after monomorphization.
---
### Answer by username_4 on 2023-05-18. Score: 6
The more work a compiler does, the longer the compilation time: templates, Hindley Milner, borrow checking, optimizers etc.

Some actions are literally NP hard, like register allocation. These require heuristics.

And then there are language-specific quirks like how the C pre-processor must open files during “#include”, which means potentially touching the same file over and over.
---
### Answer by username_5 on 2023-05-18. Score: 4
# Header files

The headers files system in C/C++ is a big reason for long compilation times. Quote from [this answer](https://stackoverflow.com/a/318440/14193797) for [Why does C++ compilation take so long?](https://stackoverflow.com/q/318398/14193797)

> Every single compilation unit requires hundreds or even thousands of
> headers to be (1) loaded and (2) compiled. Every one of them typically
> has to be recompiled for every compilation unit, because the
> preprocessor ensures that the result of compiling a header might vary
> between every compilation unit. (A macro may be defined in one
> compilation unit which changes the content of the header).
>
> This is probably the main reason, as it requires huge amounts of code
> to be compiled for every compilation unit, and additionally, every
> header has to be compiled multiple times (once for every compilation
> unit that includes it).

For alternatives, you can either precompile the headers (which can be difficult to maintain) or use the modules system (which C++20 [implemented](https://en.cppreference.com/w/cpp/language/modules)).
> **Comments:**
> **username_6** (2023-09-07): Another approach would be to allow one source file to be treated as multiple compilation units, rewinding the symbol table state at the end of each compilation unit to some particular marked state within the previous one.  
---
