I haven't yet finished the updated incremental linking patch, but I
have made a simple patch that may be also interesting as it speeds up
the normal case. It gives some 2-3% improvement on my test by
reserving upfront more buckets in the comdat signatures hash
(previously, the linker was spending something like  3% time of time
rehashing it - the final number of signatures was 2/3 of the number of
symbols). The heuristic is similar to the initial symbol table size
heuristic, but with the result 8 times smaller. In my test this has
given an average of 2.5 items per bucket and it seems there was no
need to rehash. Should I test if the numbers are similar in other
programs?
  The patch also fixes the parameter of find_or_add_kept_comdat to
pass string be reference, but I don't know if this makes a big
difference. I have also kept the code printing statistics about the
number of signatures, as I thought this may be interesting for others.

2009-04-01  Mikolaj Zalewski  <mikolajz@google.com>
       * layout.cc (Layout::Layout): reserve buckets up front for
signatures hash.
       (Layout::find_or_add_kept_section): pass string by reference
       (Layout::print stats): print information about the number of
comdat signatures.
       * layout.h (Layout::Layout): pass Command_line.
       (Layout::find_or_add_kept_section): pass string by reference
       * main.cc (main): pass Command_line to Layout::Layout.