News for hackers. Stuff that matters.
Re:Parallel GCC: a research project aiming to parallelize a ... by The_rationalist on Saturday September 14, 2019 @11:21AM (#20971336)
Llvm already has one process per compile unit I believe.
Re:Parallel GCC: a research project aiming to parallelize a ... by ndesaulniers on Saturday September 14, 2019 @11:24AM (#20971359)
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.
Re:Parallel GCC: a research project aiming to parallelize a ... by blattimwind on Saturday September 14, 2019 @12:04PM (#20971674)
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.
Re:Parallel GCC: a research project aiming to parallelize a ... by kardos on Saturday September 14, 2019 @12:16PM (#20971758)
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?

Re:Parallel GCC: a research project aiming to parallelize a ... by tacostakohashi on Saturday September 14, 2019 @12:13PM (#20971751)
There exists a multi-threaded linker called gold.
Re:Parallel GCC: a research project aiming to parallelize a ... by ndesaulniers on Sunday September 15, 2019 @10:45AM (#20977410)
LLD (llvm's linker) is also threaded but much faster than gold.
Re:Parallel GCC: a research project aiming to parallelize a ... by ef004 on Saturday September 14, 2019 @12:14PM (#20971754)
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/

Re:Parallel GCC: a research project aiming to parallelize a ... by barrkel on Saturday September 14, 2019 @02:14PM (#20972661)
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.

Re:Parallel GCC: a research project aiming to parallelize a ... by seamyb88 on Saturday September 14, 2019 @03:16PM (#20973074)
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).
Re:Parallel GCC: a research project aiming to parallelize a ... by DannyBee on Saturday September 14, 2019 @11:44AM (#20971525)
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.

Re:Parallel GCC: a research project aiming to parallelize a ... by Joky on Saturday September 14, 2019 @06:28PM (#20974257)
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...

Re:Parallel GCC: a research project aiming to parallelize a ... by daddypro on Monday September 16, 2019 @02:01AM (#20981471)
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..
Re:Parallel GCC: a research project aiming to parallelize a ... by Joky on Sunday September 22, 2019 @12:12AM (#21039623)
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.
Re:Parallel GCC: a research project aiming to parallelize a ... by phkahler on Saturday September 14, 2019 @12:01PM (#20971650)
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.

Re:Parallel GCC: a research project aiming to parallelize a ... by jart on Saturday September 14, 2019 @11:08PM (#20975326)
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.

Re:Parallel GCC: a research project aiming to parallelize a ... by dunkelheit on Saturday September 14, 2019 @04:19PM (#20973485)
So at a project that I was working on one of the compilation units got so unwieldy that the last part of the build process was basically waiting for it alone to compile (it contained a lot of template instantiations). The solution was of course to manually "shard" it into several files even if semantically it didn't make much sense. Now, you might argue that it was our shitty code that caused this but surely this is a fairly simple thing for a compiler to do automatically and not require the user do it.
Re:Parallel GCC: a research project aiming to parallelize a ... by namibj on Saturday September 14, 2019 @05:24PM (#20973906)
Even better: throw differential dataflow machinery at all the template handling of C++ code, interprocedural constant peopagation (and similar steps), and of course the linking itself.

It's sad these foundations only seem to exist in rust.

Re:Parallel GCC: a research project aiming to parallelize a ... by exikyut on Saturday September 14, 2019 @09:14PM (#20974944)
Hmmm.

I recently learned about c-reduce, which minimizes the size of reproducing C/C++ crash testcases by iteratively permuting the source code and invoking the compiler.

I can imagine a similar tool that takes a set of input file(s), carefully instruments the files somehow to determine the data interactions (a bit like the dataflow analysis mentioned in the sibling comment), and then iterates through different bucket-sorts (automatically invoking the compiler) until it finds some arrangement of locality-optimized input that also happens to compile the fastest.

On the one hand, this process would take hours - but on the other hand it can be lifted out of the compile/test cycle, and run eg overnight instead.

Optimizations might include tracing what you're editing right now and what that depends on, so active work can be relocated to the smallest discrete files possible. The system could just aim to minimize the size of all input files, but weighting what you're currently working on might produce additional speedups, I'm not sure.

In such a model, feeding in something like Boost would result in it eating all the templates that are never referenced.

To me, the biggest problem is that this entire infrastructure would need to understand very large parts of C/C++, and of course would also need to be faster than current infrastructure in order to actually speed anything up. I don't think there are any production-capable research analysis systems out there capable of doing this.

So, the likeliest path forward would be turning LLVM/GCC into something that can a) stay resident in memory (not fundamentally hard, just don't exit() :) ), b) be fed modified source code and accordingly traverse/update its analyses graph(s), and c) (most important) perform (b) efficiently (hah).

One major downside, apart from the total nonsemanticity of the actually-compiled output, would be the introduction of yet another hurdle to jump over to achieve reproducible builds.

I wonder if a design like this could be [part of] an intermediary first stage to getting something like incremental compilation into LLVM/GCC. Ie, it could be a (temporary) binary of its own that would allow for these features to be developed within a production-usable context that doesn't impact the behavior of the compiler itself; and then when it was properly built out, the compiler could be made to more and more progressively depend on it until either a) the compiler itself has the server-mode built in, or b) the changes are so dramatic the server-mode is not needed (unlikely).

I say all the above as a not-compiler person. I have no idea what I'm talking about.