Re: parallelized 'ld'?

["Kris Warkentin" <kewarken at qnx dot com>]

I don't know much about the subject one way or another but an interesting
whitepaper on a related subject, Incremental Linking is here:

http://www.usenix.org/events/osdi2000/wiess2000/full_papers/mikulin/mikulin.
pdf

I have a feeling that the gains from this would be similar to parallelizing
(when only a few objects are changed) and perhaps, in the case of GNU ld,
easier to implement.

cheers,

Kris

----- Original Message -----
From: "Cynbe ru Taren" <cynbe@muq.org>
To: <binutils@sources.redhat.com>
Sent: Monday, July 14, 2003 7:17 PM
Subject: parallelized 'ld'?


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