6 ms·

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 transla

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..
    - Joky 7y ago
      Sure: for instance in LLVM global values (variables, functions) have use-lists, so do constants. That means you can find easily every uses of a function: they are chained in a doubly linked list. In MLIR, it isn't the case. We use symbol name to refer to other global object, we lose the ability to easily find the uses of these global objects. On the other hand functions are well isolated and you can run Function passes in a multi-threaded fashion safely.
phkahler 7y ago
I only see parallelism at this level useful for JIT compilation. Interpreted languages, shaders, and similar. Those are good uses. Not real valuable for building big projects that can build in parallel at the file level already.
- jart 7y ago
  I agree. At the end of the day, C++ headers are quadratic. Folks who don't respect that fact are going to end up with files that take minutes to build. Threads won't save them. Linearly increasing core usage can't satisfactorily address an exponential problem. It would also mean make -j#cores may need to be adjusted to make -j#cores/#threads to ensure the system doesn't get bombed if a bunch of boost-heavy files get scheduled for compilation at the same time. If GCC devs try anyway and end up adding mutexes to all their data structures, it could potentially make things slower for everyone. It'd be overkill too. Last time I checked, GCC doesn't even memoize the O(n^2*m) stat system calls it does when processing includes (where m = # of -I / -isystem / -iquote flags). That would be a very simple patch to make things less bad. But it still doesn't solve the problem, which is that programming practices need to change.
blattimwind 7y ago
From my observations multi-threading the linker would be more useful, since for small changes in bigger projects the linking step usually takes a lot longer than compiling a couple units.
- tacostakohashi 7y ago
  There exists a multi-threaded linker called gold.
  - ndesaulniers 7y ago
    LLD (llvm's linker) is also threaded but much faster than gold.
- ef004 7y ago
  Ive never found linking to take more than 5 seconds with the standard linker which, but lld exists and its super fast in my experience. But i guess its only needed whon working on huge c++ like firefox or sth. like that. https://lld.llvm.org/ https://lld.llvm.org/
  - barrkel 7y ago
    Linking is isomorphic to tracing, moving GC. Effectively, the linker relocates objects in memory and writes a freeze-dried "heap" for the OS loader (another linker) to page in later. Linker slowness ~= GC pause. The cost is approximately proportional to the size of the traced graph.
- kardos 7y ago
  In a similar vein, not all units cost the same to compile -- even with many jobs in a make -j situation, toward the end of the build there may be only a few units still in progress. These lengthy 'stragglers' might benefit the most from this parallelism and consequently reduce total compile time. Quite looking forward to this project landing in a stable release. On the topic of linking-- can you sub in the gold linker for faster linking in your projects?
- 7y ago

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..
  - Joky 7y ago
    Sure: for instance in LLVM global values (variables, functions) have use-lists, so do constants. That means you can find easily every uses of a function: they are chained in a doubly linked list. In MLIR, it isn't the case. We use symbol name to refer to other global object, we lose the ability to easily find the uses of these global objects. On the other hand functions are well isolated and you can run Function passes in a multi-threaded fashion safely.

phkahler 7y ago

I only see parallelism at this level useful for JIT compilation. Interpreted languages, shaders, and similar. Those are good uses. Not real valuable for building big projects that can build in parallel at the file level already.

jart 7y ago
I agree. At the end of the day, C++ headers are quadratic. Folks who don't respect that fact are going to end up with files that take minutes to build. Threads won't save them. Linearly increasing core usage can't satisfactorily address an exponential problem. It would also mean make -j#cores may need to be adjusted to make -j#cores/#threads to ensure the system doesn't get bombed if a bunch of boost-heavy files get scheduled for compilation at the same time. If GCC devs try anyway and end up adding mutexes to all their data structures, it could potentially make things slower for everyone. It'd be overkill too. Last time I checked, GCC doesn't even memoize the O(n^2*m) stat system calls it does when processing includes (where m = # of -I / -isystem / -iquote flags). That would be a very simple patch to make things less bad. But it still doesn't solve the problem, which is that programming practices need to change.

blattimwind 7y ago

From my observations multi-threading the linker would be more useful, since for small changes in bigger projects the linking step usually takes a lot longer than compiling a couple units.

tacostakohashi 7y ago
There exists a multi-threaded linker called gold.
- ndesaulniers 7y ago
  LLD (llvm's linker) is also threaded but much faster than gold.
ef004 7y ago
Ive never found linking to take more than 5 seconds with the standard linker which, but lld exists and its super fast in my experience. But i guess its only needed whon working on huge c++ like firefox or sth. like that. https://lld.llvm.org/ https://lld.llvm.org/
- barrkel 7y ago
  Linking is isomorphic to tracing, moving GC. Effectively, the linker relocates objects in memory and writes a freeze-dried "heap" for the OS loader (another linker) to page in later. Linker slowness ~= GC pause. The cost is approximately proportional to the size of the traced graph.
kardos 7y ago
In a similar vein, not all units cost the same to compile -- even with many jobs in a make -j situation, toward the end of the build there may be only a few units still in progress. These lengthy 'stragglers' might benefit the most from this parallelism and consequently reduce total compile time. Quite looking forward to this project landing in a stable release. On the topic of linking-- can you sub in the gold linker for faster linking in your projects?
7y ago