Re: Optimizing hash table lookup in symbol binding

[Florian Weimer <fweimer at redhat dot com>]

* Szabolcs Nagy:

> On 18/11/2019 21:57, Wilco Dijkstra wrote:
>> Hi Florian,
>> 
>> Hashtables should be powers of 2 - this not only gives very efficient
>
> this hash table is in the elf binary,
> so we are not in control of the size and other details.

But the linker could try quite a few values and choose among them
because that's work that happens only once.  Which values are good
depend on the other propreties of the construct.

For example, if the bitmask filter is really strong, it would make sense
to make sure that almost all buckets are occupied, while the chains are
still reasonably short (but not necessarily length 1).

But if the bitmask filter is too leaky, we probably can't afford to
iterate over multi-element chains just in order to confirm a lookup
failure.

Thanks,
Florian