Re: parallelized 'ld'?

[Ian Lance Taylor <ian at airs dot com>]

Cynbe ru Taren <cynbe@muq.org> writes:

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

An interesting idea, and one I, at least, never considered.  At one
point the linker was mainly disk bound, which suggests that
parallelization will not bring a big improvement.  However, I did that
profiling 7 or 8 years ago, on Sun hardware running Solaris, and it is
quite possible that on modern hardware the tradeoffs are very
different.

The ELF linker runs in two significant loops.  The first one could be
parallelized with a fair amount of work--that loop is building various
data structures, and access to those data structures would of course
have to be locked.  The second loop, which I suspect is the more time
consuming one, could, I think, be parallelized fairly easily.

The first loop is a call to elf_link_add_object_symbols() for each
input file.  The actual loop appears in map_input_to_output_sections()
in ld/ldlang.c.

The second loop is in elf_bfd_final_link().  The main loop is the one
which loops over sections and then link_orders, but actually
effectively loops over input files.  Look for the code which tests and
sets the output_has_begun field.  I think that each call to
elf_link_input_bfd() can be straightforwardly parallelized, if you
strip out the stuff which causes each iteration to use the same memory
buffer.  There are also some details which would have to be handled
below that level, as the actual data is written via
_bfd_elf_set_section_contents() and bfd_seek() and bfd_write().

Ian