Re: DT_GNU_HASH: ~ 50% dynamic linking improvement

[Jakub Jelinek <jakub at redhat dot com>]

On Mon, Jul 03, 2006 at 11:33:21AM +0000, djamel anonymous wrote:
> if ((bucket[hash%nbuckets]&0x1)==1) then the chain is of length 1 and 
> contains :
> symindx hash
> if ((bucket[hash%nbuckets]&0x1)==0) then the chain is of variable length 
> larger than 1 and contains :
> symindx0 n hash0 hash1 ....   hashn
> so the chains space usage  will be as follows :
> 1-a chain of length 1 that occupied previously 12 bytes will occupy 8 bytes.
> 2-a chain of length 2 that occupied previously 16 bytes will occupy 16 
> bytes.
> 3-a chain of length 3 that occupied previously 20 bytes will occupy 24 
> bytes.
> 4-a chain of length 4 that occupied previously 24 bytes will occupy 24 
> bytes.
> 5-a chain of length 4 that occupied previously 28 bytes will occupy 32 
> bytes.

This will
1) complicate the lookup function
2) optimize for an uncommon case

The linker can size nbuckets as it wishes of course, but trying
hard to have huge nbuckets to have length 1 chains is with DT_GNU_HASH a bad
idea.  The best chain length is IMHO something like 2-6 entries, certainly
it should fit into a cacheline, but chain with length 1 is just a waste
of space in the first part of the .gnu.hash section.
The linker easily can align the whole .gnu.hash section on say 64 bytes
and reorder the chains, so that it minimizes the number of chains crossing
a 64B boundary (assuming we say 64B is the common cache line length)
and it can do so without making the section very complicated.

Say for libstdc++.so.6 we have currently:
libstdc++.so.6.0.8

Histogram for bucket list length (total of 1013 buckets):
 Length  Number     % of total  Coverage
      0  36         (  3.6%)
      1  134        ( 13.2%)      4.1%
      2  196        ( 19.3%)     16.1%
      3  231        ( 22.8%)     37.3%
      4  194        ( 19.2%)     61.0%
      5  121        ( 11.9%)     79.6%
      6  60         (  5.9%)     90.6%
      7  27         (  2.7%)     96.4%
      8  7          (  0.7%)     98.1%
      9  7          (  0.7%)    100.0%

Histogram for `.gnu.hash' bucket list length (total of 1022 buckets):
 Length  Number     % of total  Coverage
      0  52         (  5.1%)
      1  131        ( 12.8%)      4.1%
      2  225        ( 22.0%)     18.4%
      3  233        ( 22.8%)     40.5%
      4  171        ( 16.7%)     62.2%
      5  115        ( 11.3%)     80.4%
      6  64         (  6.3%)     92.5%
      7  18         (  1.8%)     96.5%
      8  8          (  0.8%)     98.5%
      9  4          (  0.4%)     99.7%
     10  1          (  0.1%)    100.0%

For libc-2.4.90.so:

Histogram for bucket list length (total of 1023 buckets):
 Length  Number     % of total  Coverage
      0  117        ( 11.4%)
      1  311        ( 30.4%)     15.1%
      2  257        ( 25.1%)     40.1%
      3  189        ( 18.5%)     67.6%
      4  97         (  9.5%)     86.5%
      5  38         (  3.7%)     95.7%
      6  10         (  1.0%)     98.6%
      7  4          (  0.4%)    100.0%

Histogram for `.gnu.hash' bucket list length (total of 1011 buckets):
 Length  Number     % of total  Coverage
      0  124        ( 12.3%)
      1  254        ( 25.1%)     12.4%
      2  296        ( 29.3%)     41.2%
      3  198        ( 19.6%)     70.2%
      4  98         (  9.7%)     89.3%
      5  29         (  2.9%)     96.4%
      6  10         (  1.0%)     99.3%
      7  2          (  0.2%)    100.0%

	Jakub