This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: DT_GNU_HASH: ~ 50% dynamic linking improvement
- From: Jakub Jelinek <jakub at redhat dot com>
- To: djamel anonymous <djam8193ah at hotmail dot com>
- Cc: drepper at redhat dot com, michael dot meeks at novell dot com, binutils at sources dot redhat dot com, libc-alpha at sources dot redhat dot com
- Date: Mon, 3 Jul 2006 14:00:57 +0200
- Subject: Re: DT_GNU_HASH: ~ 50% dynamic linking improvement
- References: <BAY22-F23BC428ADF941CF3CD77DCC7700@phx.gbl> <BAY22-F36445176EABFC5316D26FC7700@phx.gbl>
- Reply-to: 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