Re: Optimizing hash table lookup in symbol binding

[Szabolcs Nagy <Szabolcs dot Nagy at arm dot com>]

On 18/11/2019 13:58, Florian Weimer wrote:
> My primary interest was the % operator because it turns out that it
> actually shows up in some profiles stressing symbol binding during
> program lookup.  In most cases, however the search for the right mapping
> dominates and the preceding bitmask check fails most of the time.  But
> with shallow library dependencies, we can end up in a situation where
> the division actually matters.
> 
> Strategies for optimizing integer division are discussed in Hacker's
> Delight and here:
> 
> <http://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html>
> <http://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html>
> 
> (I have written to the author to get some of the math fixed in minor
> ways, but I think the general direction is solid.)
> 
> The algorithm from the first episode looks like this:

note that _itoa.c already uses something like this.

(i think the itoa code is unnecessary: there is no reason
for optimizing anything but base 10 and 16, and the compiler
can do a better job at those than trying something at runtime,
but you may look at that implementation if it's any better).