Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date: Wed, 24 Jun 2015 02:24:50 +0300
From: Alexander Monakov <>
Cc: Alexander Monakov <>
Subject: [PATCH 0/5] gnu-hash speedups


I'm happy to finally send the results of my tinkering with .gnu.hash in musl.
This patch series should improve the speed of initial loading with many
dynamic libraries and symbols, provided that .gnu.hash is populated by the
linker.  I was testing on 32-bit x86 with Clang/LLVM, and got a speedup from
~235-245ms to ~95-105ms.  This is about halfway between non-lazy binding and
lazy-binding with glibc.

Most of the speedup comes from the first patch (Bloom filters), and a bit from
the last (strength reduction for h*33).  Notably, I don't see an improvement
from the second patch (strength reduction for modulus), but it may be there
for other architectures.

I'd love to see test results on other platforms!  Although keep in mind that
the patches don't affect loading when .gnu.hash is not present.

Thanks to Rich for ideas (unsigned division by magic and 'h1 == (h2|1)' test
reordering), and to community members who encouraged me to finish this work :)


Alexander Monakov (5):
  dynlink.c: use bloom filter in gnu hash lookup
  dynlink.c: compute modulus via magic multiplication
  dynlink.c: slim down gnu_lookup
  dynlink.c: pass gnu-hash table pointer to gnu_lookup
  dynlink.c: use a faster expression in gnu_hash

 src/ldso/dynlink.c | 124 +++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 101 insertions(+), 23 deletions(-)

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.