parallelized 'ld'?

[Cynbe ru Taren]

Executive summary:
 o I/we need a parallelized version of 'ld'
 o My boss might pay me to write it.
 o Has there been any work done on this?
 o Is there any reason this would be particularly hard?
 o Would the 'ld' maintainers welcome such work?



In more detail:

I work at Cisco.  We regularly (well -- CONSTANTLY) link
multi-million-line C programs [*] on 16-32 processor boxes.
The compile phase parallelizes pretty well.  The link
phase, as far as I can tell, runs totally monoprocessor,
and consequently winds up often dominating the wallclock
build time.  (Since often only a subset of files need be
recompiled.)

It would be a substantial win for us if 'ld' could run
16-32 way parallel when appropriate hardware is
available.

linking strikes me as an "embarassingly parallel" problem:
Mostly one is doing additions to compute relocations, no?

So I don't see any reason why parallelizing linking should
be particularly hard in principle, although I can imagine
that the specific 'ld' architecture might not be suited.  (I
have not yet dived into the source.)

I expect it is simply a matter of not many of the 'ld'
maintainers having parallel hardware and hence incentive to
implement this.

Perfectly understandable, but with the imminent arrival of
"hyperthreaded" and multi-core-per-chip CPUs, this issue is
liable to become of more general interest in due course, no?

Anyhow, I'd welcome any pointers to relevant work, cautions
as to known issues and pitfalls &tc which y'all (yeah, I'm
stuck in Texas at the moment) would be willing to provide me
at this point.

Thanks!

 -- Cynbe

FWIW: If it makes any difference, I have a couple of decades
of C hacking experience and several years of
compiler/linker/assembler hacking experience (albeit mostly
in in the '80s): I think I have the basic background
knowledge and skills needed, albeit in somewhat rusty shape.
I don't need a pointer to the Dragon Book.  I *would* like
to avoid putting significant work into such a project and
only then finding out that the maintainers aren't interested
in incorporating it, for whatever reason.

[*] Please -- that's a separate flamewar entirely.