3
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Turing-complete syntax. When distinguishing valid and invalid programs require solving the halting problem, compiling takes a while. $\endgroup$
    – Mark
    May 18, 2023 at 3:37

4 Answers 4

3
$\begingroup$

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, 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.

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.

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

Header files

The headers files system in C/C++ is a big reason for long compilation times. Quote from this answer for Why does C++ compilation take so long?

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).

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – supercat
    Sep 7, 2023 at 21:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .