This is an archive of the discontinued LLVM Phabricator instance.

Make .gnu.hash section smaller.
ClosedPublic

Authored by ruiu on Nov 30 2017, 2:58 PM.

Details

Summary

Our on-disk hash table was unnecessarily large. The cost of collision is
not high in the .gnu.hash table because each symbol in the .gnu.hash
table has a hash value with it. So, for each collided symbol, the
dynamic linker just compares an integer, which is pretty cheap.

This patch increases the load factor by about 8. Here's a comparison.

$ readelf --histogram libclangSema.so.6.0.0svn-new-lld
Histogram for `.gnu.hash' bucket list length (total of 582 buckets):
 Length  Number     % of total  Coverage
      0  11         (  1.9%)
      1  35         (  6.0%)      1.5%
      2  93         ( 16.0%)      9.5%
      3  108        ( 18.6%)     23.4%
      4  121        ( 20.8%)     44.1%
      5  86         ( 14.8%)     62.6%
      6  63         ( 10.8%)     78.8%
      7  38         (  6.5%)     90.2%
      8  18         (  3.1%)     96.4%
      9  6          (  1.0%)     98.7%
     10  3          (  0.5%)    100.0%

$ readelf --histogram libclangSema.so.6.0.0svn-old-lld
Histogram for `.gnu.hash' bucket list length (total of 4093 buckets):
 Length  Number     % of total  Coverage
      0  1498       ( 36.6%)
      1  1545       ( 37.7%)     37.7%
      2  712        ( 17.4%)     72.5%
      3  251        (  6.1%)     90.9%
      4  66         (  1.6%)     97.3%
      5  16         (  0.4%)     99.3%
      6  5          (  0.1%)    100.0%

$ readelf --histogram libclangSema.so.6.0.0svn-bfd
Histogram for `.gnu.hash' bucket list length (total of 1004 buckets):
 Length  Number     % of total  Coverage
    0  92         (  9.2%)
      1  227        ( 22.6%)      9.8%
      2  266        ( 26.5%)     32.6%
      3  222        ( 22.1%)     61.2%
      4  115        ( 11.5%)     81.0%
      5  55         (  5.5%)     92.8%
      6  21         (  2.1%)     98.2%
      7  6          (  0.6%)    100.0%

$ readelf --histogram libclangSema.so.6.0.0svn-gold
Histogram for `.gnu.hash' bucket list length (total of 2053 buckets):
 Length  Number     % of total  Coverage
      0  671        ( 32.7%)
      1  709        ( 34.5%)     30.4%
      2  470        ( 22.9%)     70.7%
      3  141        (  6.9%)     88.9%
      4  54         (  2.6%)     98.2%
      5  5          (  0.2%)     99.2%
      6  3          (  0.1%)    100.0%

Diff Detail

Repository
rLLD LLVM Linker

Event Timeline

ruiu created this revision.Nov 30 2017, 2:58 PM
This revision was automatically updated to reflect the committed changes.