9 ms·

Parallel GCC: a research project aiming to parallelize a real-world compiler

171 points by matt_d 7y ago

ape4 7y ago
A tricky job to say the least
pjc50 7y ago
The old-school approach to this was "distcc". At the company where we used it for C++ we had a small compile farm and usually did "make -j 50".
- pstrateman 7y ago
  distcc can be useful, but requires that the local build environment matches the remote 100%.
  - spork12 7y ago
    That is not true
  - IcePic 7y ago
    No it doesn't, it sends preprocessed files just to not depend on remote env.
    - cat199 7y ago
      > it sends preprocessed files just to not depend on remote env. to then be compiled by the host compiler ..
      - IcePic 7y ago
        Sure, one compiler can't be egcs 2.95 and the other clang 8 (at least not in most cases) but the target compiler system doesn't even have to have include files, libs, libfoo-devel packages installed or they can be, but from old versions. As a proof of concept I once had a linux with gcc4.2.1 make c->.o files that later ran on OpenBSD. Would I trust that resulting binary? Sure not. But in cases of "lets spin up 10 compile boxes with <same ubuntu within a week of updating>" or have something along the lines of Xcode which allowed you and your colleagues to help out each other with small work units in order to make a single compile run quite much faster, that is a definite possibility. For that final release build, you might consider running it on one of those 10 VMs in the example above and have 'only' 9 others help out with the sub-parts in order to get some kind of .. guarantee. If it takes a minute for a full build on one box, getting a hint after 10 seconds that you misspelled something and that it won't ever link decently is worth something too if you value your time as a developer. Not saying it's perfect, only chipped in on the "must be 100% or it can't ever work", hopefully without needing to go into the "coach says we need to give 110% this game, and 120% if it's the finals" nitpicking.
        boring_twenties 7y ago
        This doesn't work for C++, as there is no standard ABI and thus no safe way to link object files from different compiler versions into the same binary.
  - bgmeister 7y ago
    Icecc (an old distcc fork) also distributes the toolchain, to avoid that particular problem. https://github.com/icecc/icecream https://github.com/icecc/icecream
- ndesaulniers 7y ago
  Google has objfs, a authenticed network mounted drive that is an object file cache. Usually most of the tree has already been compiles so just your change needs to get recompiled and relinked. Further, there's then GOMA which is the distcc equivalent. I frequently build Android with 500 cores in the cloud. For that reason, I don't think Google engineers will ever focus on the compiler speed of llvm. That said, LLD (llvm's linker) is the fastest linker in town by far.
  - cromka 7y ago
    Interesting. I searched for some more information on that but don't see anything except the GitHub repostoryitself. I wonder how would one go about integrating that into .Net stack.
    - jingwen 7y ago
      Check out Bazel's remote execution feature and Google RBE (remote build execution) [1]. Bazel itself is language agnostic (language support comes in the form of rules). (disclaimer: I'm an engineer on the Bazel team) [1] https://docs.bazel.build/versions/master/remote-execution.html https://docs.bazel.build/versions/master/remote-execution.ht...
      - bgmeister 7y ago
        There's also an opensource goma client + server which proxies to RBE (or potentially other bazel remote execution API implementations). Which is great if you can't or don't want to use the bazel client, but can use a compiler wrapper. https://chromium.googlesource.com/infra/goma/client/ https://chromium.googlesource.com/infra/goma/client/ https://chromium.googlesource.com/infra/goma/server/ https://chromium.googlesource.com/infra/goma/server/
  - exikyut 7y ago
    Nice info. I've wondered for quite a while about the impact of the G level of compile parallelization :). A couple of followup questions, if I may: - How long do incremental and non-incremental builds take with the build configuration you describe? - How does core<->engineer allocation work? Is 500 cores an average number? High-priority work presumably commands more access, but I'm curious if allocation is generally team-specific or engineer-specific (eg, more responsibilities = more resources). (I guess the reason I ask this is that 500 cores sounds kind of impressive and I'm going "surely they'll run out of cores if they're handing them out like candy???"), but then thinking about it that's only like 11 computers...) - I'm curious if you happen to know how Chromium gets built (IIUC Android builds it 2 (or is it 3?) times). It's tricky to distill (presumably/understandably deliberately so) how many cores the CI/trybot/etc infra is using. Overall my curiosity is what the core/time ratios/graphs are, ie how many cores translates to how short of a build. - As an aside, I vaguely recall absorbing by osmosis several years ago that Chromium takes approximately 15 minutes to build on a Very Cool™ local workstation (HP Z series). Not sure how out of date this info is. Do engineers still do test builds on local hardware (and if yes, how long does this take? probably longer than 500 cores, heh); or is everything done in throwaway cloud instances nowadays? Thanks in advance for whatever answers you're happy to provide :)
- Twirrim 7y ago
  Distcc is neat, and invaluable, but it's parallelism on a different level to this, which is introducing parallelism at the single-file compilation level. It would be interesting to see the overall performance impact of this in combination with parallelism on a build level. It could even be harmful (but I doubt it) due to resource contention.
- saurik 7y ago
  That's great for super large builds, but the point of this is to deal with "I have one file I want to compile which is taking 30 seconds to compile, and I only have like three files to compile, so it would be awesome if I could use all of the cores on my laptop to do this compile and get it down to 10 seconds or something".
  - marmaduke 7y ago
    This, parti ularly for template heavy C++. Older versions of Stan on GCC 4.8 would take 60+ seconds to compile a single C++ file.
    - stochastic_monk 7y ago
      I write template heavy code. I’ve recently refactored template instantiation across many object files. It’s faster, but a lot of work. It’d be great if I didn’t have to.
The_rationalist 7y ago
Llvm already has one process per compile unit I believe.
- ndesaulniers 7y ago
  Which is not parallelization. There's always the question of should I parallelize my compilation at the compiler level, or the build level (ie. Multiple translation units in flight). I think there's room for both, so you hopefully can get faster incremental compiles of a few number of TUs, but still have the old data level parallelization of multiple TUs.
  - DannyBee 7y ago
    LLVM has actually been working through multithreaded compilation for years. It actually works just fine (IIRC), but occasionally breaks when people do silly things :) I believe you just need to enable LLVM_ENABLE_THREADS in the config.
    - Joky 7y ago
      In LLVM, even with LLVM_ENABLE_THREADS, the compilation of a module is still sequential as far as I know. The LLVM Context is the unit of isolation between threads. For instance the multi-threaded ThinLTO optimizer/codegen will use one LLVM Context per-thread, and so each thread is processing a single Module / TU. The issue for concurrency is fairly deep in LLVM (use-lists, constant stored uniquely in context, etc.) that would make it really difficult to address intra-module parallelism. MLIR for example is designed with this in mind and the pass-manager is already multi-threaded at every level of nesting (function passes would runs on two functions of the same Module in parallel). This is causing other complication/inefficiency in the infrastructure, I'm still not sure how much it is a good tradeoff, we'll see...
      - daddypro 7y ago
        Could you elaborate on what MLIR has done differently wrt making it multithread safe and what complications it's causing and what the trade offs are..
ndesaulniers 7y ago
I look forward to this. One that that will be important for reproducible builds is having tests for non determinism. Having nondeterministic code gen in a compiler is a source of frustration and dispair and sucks to debug.
- earenndil 7y ago
  My understanding from the article is that the code gen will still be deterministic--independent operations will be performed in parallel instead of in sequence, but data dependency will still be respected.
deleted 7y ago
[deleted]
coldtea 7y ago
>This page introduces the Parallel GCC -- a research project aiming to parallelize a real-world compiler. This can be useful in many-core machines where GNU Make itself can not provide enough parallelism Huh? One wants a fast compiler even for a single compilation, not just for multiple ones that parallel make can handle as implied here...
modeless 7y ago
There are so many tools to parallelize compilation, but comparatively little effort has gone into reducing the vast amounts of redundant work that compilers do. A staggeringly large percentage of compilation time is simply wasted duplicating work that was already done hundreds of times over. Tools like ccache are really primitive compared to what is possible. Change one bit in a header file and you have to recompile your whole project, even if the output ends up being bit-identical. Zapcc[1] is more advanced, but still far from ideal. What I really want is a compiler that can incrementally update the binary as I type code, and can start from a snapshot that I download from someone else so that nobody ever needs to do a full recompile. It would require a radically different compiler infrastructure, but I don't see any reason why it would be impossible. [1] https://github.com/yrnkrn/zapcc https://github.com/yrnkrn/zapcc
- kachurovskiy 7y ago
  First time I spend a day on a partial-compile-only bug I switch if off and it's good old full recompilation from that point :)
  - tempguy9999 7y ago
    That happened to a colleague of mine with the Eiffel compiler (a long time ago). He was pissed off. Ditto full compilation thereafter. Had something similar in our office with scala & SBT, but SBT is a POS anyway.
  - Animats 7y ago
    That's a big problem with build systems based on timestamps, not checksums. Also, unless the build system can see all the inputs to the compilation, there's the potential for trouble.
    - carlmr 7y ago
      That's why Ninja build is so amazing for C/C++. It can use the whole dependencies output from the compiler and knows exactly what to recompile, even if only a header changed.
NilsIRL 7y ago
The use case is really niche. The only time it comes in handy is when: 1. You have enormous files AND 2. You have a little number of files.
- rumanator 7y ago
  Yes, I agree. In a world where all projects are comprised of a myriad source files where each one takes a fraction of a second to compile, this kind of approach sounds a tad pointless.
- ris 7y ago
  I'm not sure about that. The traditional way of exploiting parallelism for large builds is to work on a per-file basis. Want more parallelism? Fork more jobs. But this can fall apart in a couple of ways: 1. It can get extremely expensive in memory use. Your parallelism limit can be dictated by the memory your machine has. Spending your available cores over fewer simultaneous compilation units could also have benefits arising from data locality, even in situations where a machine's memory headroom isn't a concern. 2. Many large build processes have serialized steps which are currently unable to benefit from any form of parallelism. This is becoming even more the case with the rise of IPO & LTO. But as ever, we'll probably have to wait to find out how large the practical benefits end up being from this work.
- mrich 7y ago
  It is quite a common case. First you do your scratch make with 800 jobs which maxes out your machine just from preprocessing :) Thereafter you only edit a small portion of the code and recompile a small number of files, which only uses a few cores. It's especially problematic for C++ with all the template instantiations. Some files in our codebase take 40+ sec to compile.
- mxcrossb 7y ago
  Agreed. I do know some projects that do a lot of code generation that end up with huge files, though this is probably largely caused by C++’s templates forcing too much into headers (which newer versions fix). It’d also be nice if parallel make had better load balancing.
loeg 7y ago
Huh, I thought compilation was already quite parallel even on many core machines. I guess that's only true for larger software projects (or ones with many small compilation units, at least). The step that could use some TLC and increased parallelism is linking. On the other hand, maybe this project will help improve whole-program LTO link time. I see that is mentioned as future work for this effort: > Parallelize IPA part. This can also improve the time during LTO compilations Big kudos to Giuliano Belinassi, who seems to be the one driving this effort.
andyayers 7y ago
FWIW, MSVC has had this ability for a few years now. It helps with both normal compilation unit compiles and with link-time code generation. See for instance Bruce Dawson's notes: https://randomascii.wordpress.com/2014/03/22/make-vc-compiles-fast-through-parallel-compilation/ https://randomascii.wordpress.com/2014/03/22/make-vc-compile... .
nwmcsween 7y ago
OT but why isn't there a compiler that simply does absolutely basic passes to get the IR into a 'normalized' form then apply optimizations based on a 'database' of super optimized 'chunks'? For unoptimized parts run the super optimizer.
- exikyut 7y ago
  So basically a code lowering engine that works a bit like https://en.wikipedia.org/wiki/Hashlife https://en.wikipedia.org/wiki/Hashlife. Interesting! (NB. Googling "lowering" turned up the seemingly-random https://news.ycombinator.com/item?id=14422944; https://news.ycombinator.com/item?id=14422944; that page isn't such a bad set of starting links, so I figured I'd include it.)
  - Eug894 7y ago
    Please, read this idea regarding use of superoptimizers: https://drive.google.com/file/d/1GSv89tiQmPDcnFEu4n4CqfaJcUJxVmL5KrSCJ047g4o/edit https://drive.google.com/file/d/1GSv89tiQmPDcnFEu4n4CqfaJcUJ...
- UncleMeat 7y ago
  Superoptimization scales to hundreds of assembly instructions. Its not feasible for overall compilation.
deleted 7y ago
[deleted]

171 points by matt_d 7y ago

ape4 7y ago

A tricky job to say the least

The old-school approach to this was "distcc". At the company where we used it for C++ we had a small compile farm and usually did "make -j 50".

pstrateman 7y ago
distcc can be useful, but requires that the local build environment matches the remote 100%.
- spork12 7y ago
  That is not true
- IcePic 7y ago
  No it doesn't, it sends preprocessed files just to not depend on remote env.
  - cat199 7y ago
    > it sends preprocessed files just to not depend on remote env. to then be compiled by the host compiler ..
    - IcePic 7y ago
      Sure, one compiler can't be egcs 2.95 and the other clang 8 (at least not in most cases) but the target compiler system doesn't even have to have include files, libs, libfoo-devel packages installed or they can be, but from old versions. As a proof of concept I once had a linux with gcc4.2.1 make c->.o files that later ran on OpenBSD. Would I trust that resulting binary? Sure not. But in cases of "lets spin up 10 compile boxes with <same ubuntu within a week of updating>" or have something along the lines of Xcode which allowed you and your colleagues to help out each other with small work units in order to make a single compile run quite much faster, that is a definite possibility. For that final release build, you might consider running it on one of those 10 VMs in the example above and have 'only' 9 others help out with the sub-parts in order to get some kind of .. guarantee. If it takes a minute for a full build on one box, getting a hint after 10 seconds that you misspelled something and that it won't ever link decently is worth something too if you value your time as a developer. Not saying it's perfect, only chipped in on the "must be 100% or it can't ever work", hopefully without needing to go into the "coach says we need to give 110% this game, and 120% if it's the finals" nitpicking.
      - boring_twenties 7y ago
        This doesn't work for C++, as there is no standard ABI and thus no safe way to link object files from different compiler versions into the same binary.
- bgmeister 7y ago
  Icecc (an old distcc fork) also distributes the toolchain, to avoid that particular problem. https://github.com/icecc/icecream https://github.com/icecc/icecream
ndesaulniers 7y ago
Google has objfs, a authenticed network mounted drive that is an object file cache. Usually most of the tree has already been compiles so just your change needs to get recompiled and relinked. Further, there's then GOMA which is the distcc equivalent. I frequently build Android with 500 cores in the cloud. For that reason, I don't think Google engineers will ever focus on the compiler speed of llvm. That said, LLD (llvm's linker) is the fastest linker in town by far.
- cromka 7y ago
  Interesting. I searched for some more information on that but don't see anything except the GitHub repostoryitself. I wonder how would one go about integrating that into .Net stack.
  - jingwen 7y ago
    Check out Bazel's remote execution feature and Google RBE (remote build execution) [1]. Bazel itself is language agnostic (language support comes in the form of rules). (disclaimer: I'm an engineer on the Bazel team) [1] https://docs.bazel.build/versions/master/remote-execution.html https://docs.bazel.build/versions/master/remote-execution.ht...
    - bgmeister 7y ago
      There's also an opensource goma client + server which proxies to RBE (or potentially other bazel remote execution API implementations). Which is great if you can't or don't want to use the bazel client, but can use a compiler wrapper. https://chromium.googlesource.com/infra/goma/client/ https://chromium.googlesource.com/infra/goma/client/ https://chromium.googlesource.com/infra/goma/server/ https://chromium.googlesource.com/infra/goma/server/
- exikyut 7y ago
  Nice info. I've wondered for quite a while about the impact of the G level of compile parallelization :). A couple of followup questions, if I may: - How long do incremental and non-incremental builds take with the build configuration you describe? - How does core<->engineer allocation work? Is 500 cores an average number? High-priority work presumably commands more access, but I'm curious if allocation is generally team-specific or engineer-specific (eg, more responsibilities = more resources). (I guess the reason I ask this is that 500 cores sounds kind of impressive and I'm going "surely they'll run out of cores if they're handing them out like candy???"), but then thinking about it that's only like 11 computers...) - I'm curious if you happen to know how Chromium gets built (IIUC Android builds it 2 (or is it 3?) times). It's tricky to distill (presumably/understandably deliberately so) how many cores the CI/trybot/etc infra is using. Overall my curiosity is what the core/time ratios/graphs are, ie how many cores translates to how short of a build. - As an aside, I vaguely recall absorbing by osmosis several years ago that Chromium takes approximately 15 minutes to build on a Very Cool™ local workstation (HP Z series). Not sure how out of date this info is. Do engineers still do test builds on local hardware (and if yes, how long does this take? probably longer than 500 cores, heh); or is everything done in throwaway cloud instances nowadays? Thanks in advance for whatever answers you're happy to provide :)
Twirrim 7y ago
Distcc is neat, and invaluable, but it's parallelism on a different level to this, which is introducing parallelism at the single-file compilation level. It would be interesting to see the overall performance impact of this in combination with parallelism on a build level. It could even be harmful (but I doubt it) due to resource contention.
saurik 7y ago
That's great for super large builds, but the point of this is to deal with "I have one file I want to compile which is taking 30 seconds to compile, and I only have like three files to compile, so it would be awesome if I could use all of the cores on my laptop to do this compile and get it down to 10 seconds or something".
- marmaduke 7y ago
  This, parti ularly for template heavy C++. Older versions of Stan on GCC 4.8 would take 60+ seconds to compile a single C++ file.
  - stochastic_monk 7y ago
    I write template heavy code. I’ve recently refactored template instantiation across many object files. It’s faster, but a lot of work. It’d be great if I didn’t have to.

The_rationalist 7y ago

Llvm already has one process per compile unit I believe.

ndesaulniers 7y ago
Which is not parallelization. There's always the question of should I parallelize my compilation at the compiler level, or the build level (ie. Multiple translation units in flight). I think there's room for both, so you hopefully can get faster incremental compiles of a few number of TUs, but still have the old data level parallelization of multiple TUs.
- DannyBee 7y ago
  LLVM has actually been working through multithreaded compilation for years. It actually works just fine (IIRC), but occasionally breaks when people do silly things :) I believe you just need to enable LLVM_ENABLE_THREADS in the config.
  - Joky 7y ago
    In LLVM, even with LLVM_ENABLE_THREADS, the compilation of a module is still sequential as far as I know. The LLVM Context is the unit of isolation between threads. For instance the multi-threaded ThinLTO optimizer/codegen will use one LLVM Context per-thread, and so each thread is processing a single Module / TU. The issue for concurrency is fairly deep in LLVM (use-lists, constant stored uniquely in context, etc.) that would make it really difficult to address intra-module parallelism. MLIR for example is designed with this in mind and the pass-manager is already multi-threaded at every level of nesting (function passes would runs on two functions of the same Module in parallel). This is causing other complication/inefficiency in the infrastructure, I'm still not sure how much it is a good tradeoff, we'll see...
    - daddypro 7y ago
      Could you elaborate on what MLIR has done differently wrt making it multithread safe and what complications it's causing and what the trade offs are..

ndesaulniers 7y ago

I look forward to this. One that that will be important for reproducible builds is having tests for non determinism. Having nondeterministic code gen in a compiler is a source of frustration and dispair and sucks to debug.

earenndil 7y ago
My understanding from the article is that the code gen will still be deterministic--independent operations will be performed in parallel instead of in sequence, but data dependency will still be respected.

deleted 7y ago

[deleted]

coldtea 7y ago

>This page introduces the Parallel GCC -- a research project aiming to parallelize a real-world compiler. This can be useful in many-core machines where GNU Make itself can not provide enough parallelism Huh? One wants a fast compiler even for a single compilation, not just for multiple ones that parallel make can handle as implied here...

modeless 7y ago

There are so many tools to parallelize compilation, but comparatively little effort has gone into reducing the vast amounts of redundant work that compilers do. A staggeringly large percentage of compilation time is simply wasted duplicating work that was already done hundreds of times over. Tools like ccache are really primitive compared to what is possible. Change one bit in a header file and you have to recompile your whole project, even if the output ends up being bit-identical. Zapcc[1] is more advanced, but still far from ideal. What I really want is a compiler that can incrementally update the binary as I type code, and can start from a snapshot that I download from someone else so that nobody ever needs to do a full recompile. It would require a radically different compiler infrastructure, but I don't see any reason why it would be impossible. [1] https://github.com/yrnkrn/zapcc https://github.com/yrnkrn/zapcc

kachurovskiy 7y ago
First time I spend a day on a partial-compile-only bug I switch if off and it's good old full recompilation from that point :)
- tempguy9999 7y ago
  That happened to a colleague of mine with the Eiffel compiler (a long time ago). He was pissed off. Ditto full compilation thereafter. Had something similar in our office with scala & SBT, but SBT is a POS anyway.
- Animats 7y ago
  That's a big problem with build systems based on timestamps, not checksums. Also, unless the build system can see all the inputs to the compilation, there's the potential for trouble.
  - carlmr 7y ago
    That's why Ninja build is so amazing for C/C++. It can use the whole dependencies output from the compiler and knows exactly what to recompile, even if only a header changed.

NilsIRL 7y ago

The use case is really niche. The only time it comes in handy is when: 1. You have enormous files AND 2. You have a little number of files.

rumanator 7y ago
Yes, I agree. In a world where all projects are comprised of a myriad source files where each one takes a fraction of a second to compile, this kind of approach sounds a tad pointless.
ris 7y ago
I'm not sure about that. The traditional way of exploiting parallelism for large builds is to work on a per-file basis. Want more parallelism? Fork more jobs. But this can fall apart in a couple of ways: 1. It can get extremely expensive in memory use. Your parallelism limit can be dictated by the memory your machine has. Spending your available cores over fewer simultaneous compilation units could also have benefits arising from data locality, even in situations where a machine's memory headroom isn't a concern. 2. Many large build processes have serialized steps which are currently unable to benefit from any form of parallelism. This is becoming even more the case with the rise of IPO & LTO. But as ever, we'll probably have to wait to find out how large the practical benefits end up being from this work.
mrich 7y ago
It is quite a common case. First you do your scratch make with 800 jobs which maxes out your machine just from preprocessing :) Thereafter you only edit a small portion of the code and recompile a small number of files, which only uses a few cores. It's especially problematic for C++ with all the template instantiations. Some files in our codebase take 40+ sec to compile.
mxcrossb 7y ago
Agreed. I do know some projects that do a lot of code generation that end up with huge files, though this is probably largely caused by C++’s templates forcing too much into headers (which newer versions fix). It’d also be nice if parallel make had better load balancing.

loeg 7y ago

Huh, I thought compilation was already quite parallel even on many core machines. I guess that's only true for larger software projects (or ones with many small compilation units, at least). The step that could use some TLC and increased parallelism is linking. On the other hand, maybe this project will help improve whole-program LTO link time. I see that is mentioned as future work for this effort: > Parallelize IPA part. This can also improve the time during LTO compilations Big kudos to Giuliano Belinassi, who seems to be the one driving this effort.

andyayers 7y ago

FWIW, MSVC has had this ability for a few years now. It helps with both normal compilation unit compiles and with link-time code generation. See for instance Bruce Dawson's notes: https://randomascii.wordpress.com/2014/03/22/make-vc-compiles-fast-through-parallel-compilation/ https://randomascii.wordpress.com/2014/03/22/make-vc-compile... .

nwmcsween 7y ago

OT but why isn't there a compiler that simply does absolutely basic passes to get the IR into a 'normalized' form then apply optimizations based on a 'database' of super optimized 'chunks'? For unoptimized parts run the super optimizer.

exikyut 7y ago
So basically a code lowering engine that works a bit like https://en.wikipedia.org/wiki/Hashlife https://en.wikipedia.org/wiki/Hashlife. Interesting! (NB. Googling "lowering" turned up the seemingly-random https://news.ycombinator.com/item?id=14422944; https://news.ycombinator.com/item?id=14422944; that page isn't such a bad set of starting links, so I figured I'd include it.)
- Eug894 7y ago
  Please, read this idea regarding use of superoptimizers: https://drive.google.com/file/d/1GSv89tiQmPDcnFEu4n4CqfaJcUJxVmL5KrSCJ047g4o/edit https://drive.google.com/file/d/1GSv89tiQmPDcnFEu4n4CqfaJcUJ...
UncleMeat 7y ago
Superoptimization scales to hundreds of assembly instructions. Its not feasible for overall compilation.

deleted 7y ago

[deleted]