13

If I remember my compilers course correctly, the typical compiler has the following simplified outline:

  • A lexical analyzer scans (or calls some scanning function on) the source code character-by-character
  • The string of input characters is checked against the dictionary of lexemes for validity
  • If the lexeme is valid, it is then classified as the token that it corresponds to
  • The parser validates the syntax of the combination of tokens; token-by-token.

Is it theoretically feasible to split the source code into quarters (or whatever denominator) and multithread the scanning and parsing process? Do compilers exist that utilize multithreading?

26

Large software projects are usually composed of many compilation units that can be compiled relatively independently, and so compilation is often parallelized at a very rough granularity by invoking the compiler several times in parallel. This happens at the level of OS processes and is coordinated by the build system rather than the compiler proper. I realize this isn't what you asked but that's the closest thing to parallelization in most compilers.

Why is that? Well, much of the work that compilers do doesn't lend itself to parallelization easily:

  • You can't just split the input into several chunks and lex them independently. For simplicity you'd want to split on lexme boundaries (so that no thread starts in the middle of a lexme), but determining lexme boundaries potentially requires a lot of context. For example, when you jump in the middle of the file, you have to make sure you didn't jump into a string literal. But to check this, you have to look at basically every character that came before, which is almost as much work as simply lexing it to begin with. Besides, lexing is rarely the bottleneck in compilers for modern languages.
  • Parsing is even harder to parallelize. All the problems of splitting the input text for lexing apply even more to splitting the tokens for parsing --- e.g., determining where a function starts is basically as hard as parsing the function contents to begin with. While there might also be ways around this, they will probably be disproportionally complex for the little benefit. Parsing, too, is not the largest bottleneck.
  • After you've parsed, you usually need to perform name resolution, but this leads to a huge interwoven net of relationships. To resolve a method call here you might have to first resolve the imports in this module, but those require resolving the names in another compilation unit, etc. Same for type inference if your language has that.

After this, it gets slightly easier. Type checking and optimization and code generation might, in principle, be parallelized at function granularity. I still know of few if any compilers doing this, perhaps because doing any task this large concurrently is quite challenging. You also have to consider that most large software projects contain so many compilation units that the "run a bunch of compilers in parallel " approach is entirely sufficient to keep all your cores occupied (and in some cases, even an entire server farm). Plus, in large compilation tasks the disk I/O can be as much of a bottleneck as the actual work of compiling.

All that said, I do know of a compiler that parallelizes the work of code generation and optimization. The Rust compiler can split the back end work (LLVM, which actually includes code optimizations that are traditionally considered "middle-end") among several threads. This is called "code-gen units". In contrast with the other parallelization possibilities discussed above, this is economical because:

  1. The language has rather large compilation units (compared to, say, C or Java), so there might be fewer compilation units in flight than you have cores.
  2. The part that is being parallelized usually takes the vast majority of compile time.
  3. The backend work is, for the most part, embarrassingly parallel — just optimize and translate to machine code each function independently. There are inter-procedural optimizations of course, and codegen units do hinder those and thus impact performance, but there aren't any semantic problems.
2

Compilation is an "embarrassingly parallel" problem.

Nobody cares about the time for compiling one file. People care about the time of compiling 1000 files. And for 1000 files, each core of the processor can happily compile one file at a time, keeping all cores totally busy.

Tip: "make" uses multiple cores if you give it the right command line option. Without that it will compile one file after the other on a 16 core system. Which means you can make it compile 16 times faster with a one line change to your build options.

protected by gnat Jan 10 at 12:19

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.