Re: Speed up KConfig - fix hashtable confusion

[David Laight <david.laight.linux@gmail.com>]

On Mon, 2 Nov 2026 10:20:35 -0800
Linus Torvalds <torvalds@linux-foundation.org> wrote:

> On Mon, 2 Nov 2026 at 01:47, David Laight <david.laight.linux@gmail.com> wrote:
> >
> > An alternative would be:
> >         ((key) * (u64)(size)) >> 32
> > which avoids the division when size isn't a constant power of 2.  
> 
> That's certainly cleaner
> 
> Not that it should matter - afaik the size is always a constant (it
> comes from 'sizeof()'), and I would actually prefer it if
> HASHTABLE_DECLARE and HASHTABLE_DEFINE took the number of *bits* (like
> DECLARE_HASHTABLE() does for the kernel proper), and we'd just make it
> a rule that it's always a power-of-2.
> 
> It already *is* always a power-of-two, and the old code used to make
> it a slow modulus operation if it wasn't.

Ah yes, some people think hash tables need to have a prime size.
Do not doubt the sanity of the person who decided that the elf symbol
hash table size would be (IIRC) 'the prime number below the power of
2 below the number of symbols' - this makes every hash list have ~1.5
symbols so you pretty much always have to do name compares on every
shared library that gets loaded with a program in order to find a
symbol that is in libc.
I remember significantly speeding up loading of mozilla by rewriting
the elf interpreter to generate a merged symbol table for all those
libraries - no idea what the one the Linux uses does.

With a reasonable hash function (or even the crap and slow to calculate
one elf uses) a power of two sized table works just as well.

> I'd also worry a tiny bit about what the compilers do on 32-bit
> targets, although obviously hopefully (a) they'd optimize it to the
> right 32-bit code rather than do 64-bit ops and (b) it's not like we
> seriously care about 32-bit host builds anyway.

They'll probably zero-pad both sides to 64 bit and do all four multiplies.
But that isn't so bad on most systems.
At least the 32bit shift is cheap!

But yes, you are going to have trouble with a lot of builds on 32bit hosts.
objtool sat for minutes (long enough for me to think it might be stuck)
with an RSS of ~30GB on a recent build (ok it was allyesconfig - I wanted
the symbol table) - but I suspect it will hit 3GB on a reasonable kernel.

David

> 
>              Linus