Linus fixes Kconfig hash misuse that slowed make oldconfig

Linus Torvalds has fixed a long-standing performance bug in Kconfig that made make oldconfig slower than it needed to be. The expression lookup path alone was consuming more than 10% of runtime on his machine.

The root cause was not the hash function itself. hash_32() is fast and adequate, but it concentrates useful entropy in the high bits of its result. Kernel code knows this and extracts those bits. The simplified hashtable helpers used by host tools did not: they reduced the key with a plain modulo of the table size. For pointer-derived keys whose low bits are typically clear, the low bits of the hash are also clear, so most buckets stayed empty even when the table was sized correctly. Enlarging the table only papered over the problem at the cost of worse cache behavior.

Torvalds changed the host-side bucket selection to pull from the high bits and stopped generating lookup keys by XORing two pointers, a pattern that can cancel shared bits. On his system the cost of expression lookup fell by roughly a factor of four and ceased to be the hottest function in make oldconfig.

Julian Braha argued the host helpers should more closely match the kernel’s hashtable API rather than keep a divergent simplification; David Laight floated a multiply-and-shift form that avoids a division when the table size is not a compile-time power of two. The immediate win is simpler: configuration no longer pays a large, unnecessary tax for a misunderstood hash.

The change does not make Kconfig fast overnight, but it removes one particularly stupid reason it was slower than necessary.