From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/7994 Path: news.gmane.org!not-for-mail From: Alexander Monakov Newsgroups: gmane.linux.lib.musl.general Subject: [PATCH 0/5] gnu-hash speedups Date: Wed, 24 Jun 2015 02:24:50 +0300 Message-ID: <1435101895-18240-1-git-send-email-amonakov@ispras.ru> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org X-Trace: ger.gmane.org 1435107314 13085 80.91.229.3 (24 Jun 2015 00:55:14 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 24 Jun 2015 00:55:14 +0000 (UTC) Cc: Alexander Monakov To: musl@lists.openwall.com Original-X-From: musl-return-8007-gllmg-musl=m.gmane.org@lists.openwall.com Wed Jun 24 02:55:14 2015 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1Z7Yy9-0003sB-FV for gllmg-musl@m.gmane.org; Wed, 24 Jun 2015 02:55:13 +0200 Original-Received: (qmail 22114 invoked by uid 550); 24 Jun 2015 00:55:11 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 3788 invoked from network); 23 Jun 2015 23:25:23 -0000 X-Mailer: git-send-email 2.1.4 Xref: news.gmane.org gmane.linux.lib.musl.general:7994 Archived-At: Hello! 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 :) Yours, 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(-)