Hacker News Reader

Comment by ndesaulniers | Hacker News Reader

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.

View on HN

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.

There exists a multi-threaded linker called gold.

LLD (llvm's linker) is also threaded but much faster than gold.

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/

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.

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?

I also find that the linker is the issue. Yes for performance, but also for testing (to the point of failure) linux's 'out of memory' scenario (try make -j8 on the llvm source, for example).

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.

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

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

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.

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.

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.

Reply on news.ycombinator.com