From f93d6bfbd2f74d79041c153a59df5336f6e9a14a Mon Sep 17 00:00:00 2001 From: Masahiro Yamada Date: Sun, 8 Sep 2024 21:43:20 +0900 Subject: kconfig: use hash table to reuse expressions Currently, every expression in Kconfig files produces a new abstract syntax tree (AST), even if it is identical to a previously encountered one. Consider the following code: config FOO bool "FOO" depends on (A || B) && C config BAR bool "BAR" depends on (A || B) && C config BAZ bool "BAZ" depends on A || B The "depends on" lines are similar, but currently a separate AST is allocated for each one. The current data structure looks like this: FOO->dep ==> AND BAR->dep ==> AND BAZ->dep ==> OR / \ / \ / \ OR C OR C A B / \ / \ A B A B This is redundant; FOO->dep and BAR->dep have identical ASTs but different memory instances. We can optimize this; FOO->dep and BAR->dep can share the same AST, and BAZ->dep can reference its sub tree. The optimized data structure looks like this: FOO->dep, BAR->dep ==> AND / \ BAZ->dep ==> OR C / \ A B This commit introduces a hash table to keep track of allocated expressions. If an identical expression is found, it is reused. This does not necessarily result in memory savings, as menu_finalize() transforms expressions without freeing up stale ones. This will be addressed later. One optimization that can be easily implemented is caching the expression's value. Once FOO's dependency, (A || B) && C, is calculated, it can be cached, eliminating the need to recalculate it for BAR. This commit also reverts commit e983b7b17ad1 ("kconfig/menu.c: fix multiple references to expressions in menu_add_prop()"). Signed-off-by: Masahiro Yamada --- scripts/include/hash.h | 13 +++++++++++++ 1 file changed, 13 insertions(+) (limited to 'scripts/include') diff --git a/scripts/include/hash.h b/scripts/include/hash.h index ce2bc43b308b..efa904368a62 100644 --- a/scripts/include/hash.h +++ b/scripts/include/hash.h @@ -12,4 +12,17 @@ static inline unsigned int hash_str(const char *s) return hash; } +/* simplified version of functions from include/linux/hash.h */ +#define GOLDEN_RATIO_32 0x61C88647 + +static inline unsigned int hash_32(unsigned int val) +{ + return 0x61C88647 * val; +} + +static inline unsigned int hash_ptr(const void *ptr) +{ + return hash_32((unsigned int)(unsigned long)ptr); +} + #endif /* HASH_H */ -- cgit