linux

mirror of https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/ synced 2026-10-18 19:12:56 +00:00

28 lines

563 B

Raw Permalink Normal View History

scripts: move hash function from scripts/kconfig/ to scripts/include/ This function was originally added by commit 8af27e1dc4e4 ("fixdep: use hash table instead of a single array"). Move it to scripts/include/ so that other host programs can use it. Signed-off-by: Masahiro Yamada <masahiroy@kernel.org> 2024-09-08 21:43:16 +09:00













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 <masahiroy@kernel.org> 2024-09-08 21:43:20 +09:00












scripts: move hash function from scripts/kconfig/ to scripts/include/ This function was originally added by commit 8af27e1dc4e4 ("fixdep: use hash table instead of a single array"). Move it to scripts/include/ so that other host programs can use it. Signed-off-by: Masahiro Yamada <masahiroy@kernel.org> 2024-09-08 21:43:16 +09:00

28 lines 563 B Raw Permalink Normal View History

28 lines

563 B

Raw Permalink Normal View History