Speed up KConfig - fix hashtable confusion

Speed up KConfig - fix hashtable confusion

[Linus Torvalds]

[-- Attachment #1: Type: text/plain, Size: 2367 bytes --]

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)))

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

[-- Attachment #2: patch.diff --]
[-- Type: text/x-patch, Size: 2008 bytes --]

 scripts/include/hashtable.h | 4 +++-
 scripts/kconfig/expr.c      | 5 +++--
 scripts/kconfig/internal.h  | 4 ----
 3 files changed, 6 insertions(+), 7 deletions(-)

diff --git a/scripts/include/hashtable.h b/scripts/include/hashtable.h
index 45abcb12bfce..a69332ccffcd 100644
--- a/scripts/include/hashtable.h
+++ b/scripts/include/hashtable.h
@@ -13,7 +13,9 @@
 	HASHTABLE_DECLARE(name, size) =						\
 			{ [0 ... ((size) - 1)] = HLIST_HEAD_INIT }
 
-#define hash_head(table, key)		(&(table)[(key) % HASH_SIZE(table)])
+#define HASH_KEY(key,size) (unsigned int)((unsigned int)(key)/(0x100000000ull/(size)))
+
+#define hash_head(table, key)		(&(table)[HASH_KEY(key,HASH_SIZE(table))])
 
 static inline void __hash_init(struct hlist_head *ht, unsigned int sz)
 {
diff --git a/scripts/kconfig/expr.c b/scripts/kconfig/expr.c
index 2b91d16bf14f..19ca2ad10425 100644
--- a/scripts/kconfig/expr.c
+++ b/scripts/kconfig/expr.c
@@ -16,7 +16,8 @@
 
 #define DEBUG_EXPR	0
 
-HASHTABLE_DEFINE(expr_hashtable, EXPR_HASHSIZE);
+#define EXPR_HASHSIZE		(1U << 14)
+static HASHTABLE_DEFINE(expr_hashtable, EXPR_HASHSIZE);
 
 static struct expr *expr_eliminate_yn(struct expr *e);
 
@@ -35,7 +36,7 @@ static struct expr *expr_lookup(enum expr_type type, void *l, void *r)
 	struct expr *e;
 	int hash;
 
-	hash = hash_32((unsigned int)type ^ hash_ptr(l) ^ hash_ptr(r));
+	hash = hash_32((unsigned int)type + hash_ptr(l) + hash_ptr(r));
 
 	hash_for_each_possible(expr_hashtable, e, node, hash) {
 		if (e->type == type && e->left._initdata == l &&
diff --git a/scripts/kconfig/internal.h b/scripts/kconfig/internal.h
index d0ffce2dfbba..f244952496eb 100644
--- a/scripts/kconfig/internal.h
+++ b/scripts/kconfig/internal.h
@@ -11,10 +11,6 @@ extern HASHTABLE_DECLARE(sym_hashtable, SYMBOL_HASHSIZE);
 #define for_all_symbols(sym) \
 	hash_for_each(sym_hashtable, sym, node)
 
-#define EXPR_HASHSIZE		(1U << 14)
-
-extern HASHTABLE_DECLARE(expr_hashtable, EXPR_HASHSIZE);
-
 void expr_invalidate_all(void);
 
 struct menu;

Re: Speed up KConfig - fix hashtable confusion

[Julian Braha]

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 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?

Thanks for diagnosing this, Linus

- Julian Braha

Re: Speed up KConfig - fix hashtable confusion

[Nicolas Schier]

[-- Attachment #1: Type: text/plain, Size: 3006 bytes --]

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@kernel.org>

Kind regards,
Nicolas


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: Speed up KConfig - fix hashtable confusion

[David Laight]

On Sun, 1 Nov 2026 12:08:15 -0800
Linus Torvalds <torvalds@linux-foundation.org> 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

Re: Speed up KConfig - fix hashtable confusion

[Linus Torvalds]

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.

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.

             Linus

Re: Speed up KConfig - fix hashtable confusion

[David Laight]

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

Re: Speed up KConfig - fix hashtable confusion

[Sasha Levin]

On Sun, Nov 01, 2026 at 12:08:15PM -0800, Linus Torvalds wrote:
> 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.

I'm not sure why we have a copy of include/linux/hashtable.h in
scripts/, but it's silly that it has diverged slightly from what we do
in-kernel, and now we're chasing bugs caused by that divergence.

Can we instead align both back to be the same, or even use
include/linux/hashtable.h directly from scripts/?

--
Thanks,
Sasha

Re: Speed up KConfig - fix hashtable confusion

[Nicolas Schier]

On Mon, Nov 02, 2026 at 05:26:27AM -0500, Sasha Levin wrote:
> On Sun, Nov 01, 2026 at 12:08:15PM -0800, Linus Torvalds wrote:
> > 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.
> 
> I'm not sure why we have a copy of include/linux/hashtable.h in
> scripts/, but it's silly that it has diverged slightly from what we do
> in-kernel, and now we're chasing bugs caused by that divergence.
> 
> Can we instead align both back to be the same, or even use
> include/linux/hashtable.h directly from scripts/?

I think that matches Julian's proposal.  For include/linux/hashtable.h,
it may be a good idea to use it directly from include/linux/, but in
general we should be careful when re-using kernel internal header files
for host tooling.  I am afraid we may put a burden on changes on these
if we (mis)use them in a non-kernel context.  But yes, we should
consider at least regular syncing in some way to prevent repeating
mistakes.

-- 
Nicolas