I spent 8 years working on Visual C++ back-end, and everything is not as bad. With very reasonable effort it is possible to speed up compilation by factor of ~2.5x on 4-core CPU. Without major redesign, in an existing compiler codebase. Memory use would grow insignificantly.

Major problems are caused by non-thread-safety of lot of existing data structures. I.e. problems are not with algorithms but with particular implementation. Years ago, when initial compiler code was written, nobody thought about compiling several functions in parallel. Then we added LTCG to the compiler, and amount of code that is compiled in one compiland suddenly grew. I remember debugging compiler crash that came from customer -- we asserted after 16 hours of work, compiling function #250,000 (that was debug version of the compiler, several times slower than production one, so customer had better experience...)

Further speedups and better scaling are harder because of Amdahl law, but are possible, too.

Unfortunately I cannot go into details in the public forum...

Thanks,
Eugene

rwessel (robertwessel@yahoo.com) on 11/12/09 wrote:
---------------------------
>? (0xe2.0x9a.0x9b@gmail.com) on 11/12/09 wrote:
>---------------------------
>>Potatoswatter (potswa_m@c.com) on 11/11/09 wrote:
>>---------------------------
>>>It sounds more like you're talking about pipelining the compiler: one thread parses
>>>while another thread generates code. Unfortunately that only works when you know
>>>the relative speeds of the pipeline stages.
>>
>>Couldn't that (at least partially) be solved by inserting a buffer between the pipeline stages? Like:
>>
>>[parser thread] ---> [buffer] ---> [compiler thread]
>
>
>Yes, some buffering would go a long way to allowing that sort of structure to work.
>The problem is that you need still need to be able to break up the work into relatively
>even sized pieces. Let's say, for example, that the parser in the above did 10
>units of work, while the compiler did 1000. The parallelism is simply not going
>to buy you much (about 1%, in fact). In fact, parsing is typically a pretty small part of a modern compilation process.
>
>Worse, most things compilers do these days *don't* organize well as processes on
>streams. Now that definitely did used to be the case, and many compilers basically
>were dozens of passes each reading a sequential input from the prior pass and writing
>a sequential output for the next pass. Parallelizing that sort of thing with the above structure would work well.
>
>Unfortunately these days compilers tend to build a single big structure for the
>entire program and then work on that as a whole, and the "passes" are far, far less
>distinct. In fact, typically the only fairly independent passes are the "parse"
>and "code generation" steps (and a preprocessor, if your language includes that).
>And of those two or three passes, only code generation is a real CPU hog these
>days. Most I/O ends up happening in the parsing (or preprocessor) phases, code
>generation typically just does a big sequential write of the object file at the
>end after mucking around with the internal representation of the program for a long while.
>
>While it might appear that different routines (functions, procedures, or whatever
>your language calls them) could reasonably go through code generation and optimization
>independently, that's typically not possible since all modern compilers do things
>like inlining and inter-procedure optimizations. And it's those kinds of optimizations
>that are particularly CPU intensive.
>
>Now that doesn't mean that real projects can't use parallelism during the build
>process. Any parallel make tool will do that for you, and is probably already being
>used on large projects. Unfortunately Amdahl bites us at this point and often one
>of the biggest consumers of (wall clock) time is then the link step (and frankly
>linker performance is often astonishingly slow).
>
>This is made worse by the increasing use of link time code generation, which leaves
>little more than the parsing step actually happening in the "compiler" invocation.
>And basically the whole point of LTCG is to expose *more* inter-procedure optimization
>possibilities to the compiler, so that the LTCG function now has more of the most expensive work to do.
>
>Now a project that generates multiple binaries still gets considerable benefit
>from a parallel make, so long as there are not dependencies between the links (in
>Windows, for example, a build of a DLL often generates an import library which is
>a dependency for another executable, which can bite).
>
>But in general, I think the compilation of a single program is one of the least profitable places to apply parallelism.
>