RFC: Caching of lookup results during startup

[Andreas Jaeger]

Ulrich Drepper <drepper@redhat.com> writes:

> Andreas Jaeger <aj@suse.de> writes:
> 
>> I haven't seen binutils patches for this yet and looking at his
>> description he seems to do the reordering in his prelinker.
> 
> For now this is true I assume.

Then let's discuss with Jakub and the binutils folks to do the
reordering in binutils and then add his patch for the cache to the
dynamic linker.

FYI: Looking at the binutils I noticed that mips already does a
sorting in bfd/elf32-mips.c:
/* This function is called via qsort() to sort the dynamic relocation
   entries by increasing r_symndx value.  */

>> I've just played around with only caching the last value and got 1050
>> values served from the cache instead of 33770 values using a complete
>> cache (out of 54130 relocations for konqueror).  The reordering part
>> is essential here.
> 
> It's really essential all the time.  Otherwise you have to do more
> work (more than one entry cached) and get less out of it.  It's not
> only the number of relocations you perform, it's also the
> administrative work to be done for each of them.

The only problem I see is data locality.  If we order by symbol
instead of by address we jump a bit more random through the dynamic
object and iterate several times.  Let's see whether these changes
have an effect on the CPU cache.

Andreas
-- 
 Andreas Jaeger
  SuSE Labs aj@suse.de
   private aj@arthur.inka.de
    http://www.suse.de/~aj