dynsym/dynstr/relocs sorting speedup #2

[Nick Clifton]

Hi Michael,

>         It seems that by sorting dynsym & dynstr and relocations by
> (elf_hash % bucketcount) we can easily get a 5%+ speedup for linking.

The patch itself looks fairly reasonable.  There are some formatting 
issues, but they are not important right now.  One glaring thing though 
is the use of the DONT_SORT_SYMS environment variable.  This is a no-no. 
  A command line option should be used instead.  (I assume that you used 
the environment variable as a quick way to get performance figures 
without having to add the command line code).

>         issues / queries:
>                 * calculates elf hash of strtab symbols again
>                         + could we store the elf_link_hash_entry
>                           pointer from bfd_elf_record_dynamic_symbol ?
>                           where possible to avoid re-calculating that.

Hmm - this sounds like a good idea, but I am not sure if we could always 
rely upon this value having been calculated for us when we need it.  I 
would suggest reserving this to a future optimization of this code.

>                 * qsort - has no closure, nasty global variable for
>                           bucket count - how should that be fixed ?

By writing your own version of qsort ?  Or by creating a new structure 
that holds an "elf_link_hash_entry **" hash entry and a "size_t" bucket 
size and passing pointers to this structure as arguments to qsort.

>                 * conditional
>                         + the sorting takes some time & space at link
>                           time - should it be conditional ?

Yes, most definitely.  You may also want to hook the disabling into the 
--reduce-memory-overheads switch.

> 			+ should we shrink the number of discrete bucket
> 			  counts, clearly where these match the current
> 			  library we get a better win [ should we pick 
> 			  the best count/avg of the deps ? ;-]

No idea squire.  A little bit of experimentation would be a god idea here.


Cheers
   Nick