Re: Speed up KConfig - fix hashtable confusion

[David Laight]

On Sun, 1 Nov 2026 12:08:15 -0800
Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx> wrote:

> So the Kconfig 'expr_lookup()' function is criminally slow and takes
> over 10% of the time of "make oldconfig".
> 
> 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)))

An alternative would be:
	((key) * (u64)(size)) >> 32
which avoids the division when size isn't a constant power of 2.

David

> 
> but at least this improves on things.
> 
> I also stopped the expr_lookup() key generation from using XOR of two
> pointers, which I suspect just ended up clearing most of the shared
> bits. I doubt that makes a difference, but XOR of thigns that may have
> shared bits really isn't great.
> 
> The cost of 'expr_lookup()' drops by a about factor of four on my
> machine, and it's no longer the hottest function in all of 'make
> oldconfig'.
> 
> No, "make oldconfig" still isn't the fastest thing around, but at
> least this removes on particularly stupid reason for it being slower
> than it needs to be.
> 
> 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?
> 
>                 Linus