Re: Speed up KConfig - fix hashtable confusion

[Nicolas Schier]

On Sun, Nov 01, 2026 at 11:44:39PM +0000, Julian Braha wrote:
> On 11/1/26 20:08, Linus Torvalds wrote:
> > So the Kconfig 'expr_lookup()' function is criminally slow and takes
> > over 10% of the time of "make oldconfig".
> 
> My own pet peeve is the occasional slowdowns in menuconfig search...
> > 
> > The reason is that it's called just a lot, but it *really* doesn't
> > help that the scripting versions of the hashtable functions has not
> > understood the subtler issues of the hashing code that it took from
> > the kernel side, and in the process got things very very wrong.
> > 
> > The "hash_32()" function is a perfectly fine hashing function - there
> > are better ones around, but it's fast and "good enough". But when you
> > use it, you need to understand that it puts the significant bits in
> > the *high* bits of the result.
> > 
> > The kernel uses a model where you give it the number of bits you want,
> > and it will pick out those high bits, which makes it all work right.
> > 
> > But the simplified hashtable code for the host code didn't use those
> > high bits of the key. It just did
> > 
> >     (key) % HASH_SIZE(table)
> > 
> > to pick the hash table entry, and that's basically pessimal. When
> > hashing an address that typically has the low bits clear, the low bits
> > of "hash_32()" will *also* be clear. So the hash table ended up being
> > mostly empty! So even though the hash table was sized appropriately,
> > it wasn't being very efficient. And while making the hash table larger
> > mostly hides the problem, it's the wrong solution, because the cache
> > footprint gets worse.
> > 
> > Teach "hash_head()" to use the high bits of the key. Because the users
> > don't pass in the number of bits they want, this is pretty hacky:
> > 
> >     #define HASH_KEY(key,size) \
> >         (unsigned int)((unsigned int)(key)/(0x100000000ull/(size)))
> > 
> > but at least this improves on things.
> 
> It would be a bigger change but IMO the host-side implementation should
> not differ much from the kernel's -- like the rest of the data
> structures in scripts/include/. In other words I'd prefer to revert some
> of the "simplifications" that caused this and adjust the callers
> accordingly.
> 
> Nathan or Nicolas, do you feel differently? This is also used by some
> other tooling outside Kconfig. If not then I'll send out my version.
> 

I have no strong opinion on that, yet.  But probably it's better to take
a working speed-up fix now and think about the long-term maintenance
stuff later on.

[...]
> > Somebody needs to double-check this. I don't love my HASH_KEY() macro,
> > but it should work for power-of-2 sizes. And as far as I can tell, all
> > the hash tables are powers of two.
> > 
> > Comments?

Thanks for spotting!  Patch looks good to me and the use of the hash
table significantly better distributed.

Reviewed-by: Nicolas Schier <nsc@xxxxxxxxxx>

Kind regards,
Nicolas

Attachment: signature.asc
Description: PGP signature