[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <20251205210629.GO3520958@port70.net>
Date: Fri, 5 Dec 2025 22:06:29 +0100
From: Szabolcs Nagy <nsz@...t70.net>
To: Rich Felker <dalias@...c.org>
Cc: Fabian Rast <fabian.rast@....de>, musl@...ts.openwall.com
Subject: Re: [PATCH] ldso: skip gnu hash calculation if precomputed
* Rich Felker <dalias@...c.org> [2025-12-05 13:48:34 -0500]:
> On Fri, Dec 05, 2025 at 07:30:51PM +0100, Szabolcs Nagy wrote:
> > eventually the gain from not computing the hash
> > is dominated by caculating 2*n bloom filters
> > (and potentially chasing twice as many hash chains)
>
> I think this analysis sounds correct, in which case the optimization
> probably only makes sense if we can find a way to determine the
> correct hash in tiny bounded time as a one-off operation, rather than
> having to try two candidate hashes per dso.
>
> One way to do this would be to use the bloom filter from the dso
> making the symbol reference: if only one of the two candidates passes
> it, we know which candidate was correct. I would expect this to happen
> most of the time, if the bloom filter is actually doing anything
> useful to begin with.
nice, this should work as the hash chain starts at:
uint32_t i = buckets[h % nbuckets];
so the chain depends on the lsb and i is a symidx
uint32_t *ght = dso->ghastab;
uint32_t nbuckets = ght[0];
uint32_t *buckets = ght + 4 + ght[2]*(sizeof(size_t)/4);
uint32_t h0 = buckets[nbuckets + sym_index - ght[1]] & -2u;
uint32_t h1 = h0|1;
uint32_t i1 = buckets[h1 % nbuckets];
uint32_t gh = sym_idx < i1 ? h0 : h1;
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.
