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

[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