|
Revision tags: v6.15, v6.15-rc7, v6.15-rc6, v6.15-rc5, v6.15-rc4, v6.15-rc3, v6.15-rc2, v6.15-rc1, v6.14, v6.14-rc7, v6.14-rc6, v6.14-rc5, v6.14-rc4, v6.14-rc3, v6.14-rc2, v6.14-rc1, v6.13, v6.13-rc7, v6.13-rc6, v6.13-rc5, v6.13-rc4, v6.13-rc3, v6.13-rc2, v6.13-rc1, v6.12, v6.12-rc7, v6.12-rc6, v6.12-rc5, v6.12-rc4, v6.12-rc3, v6.12-rc2, v6.12-rc1, v6.11, v6.11-rc7 |
|
| #
f93d6bfb |
| 08-Sep-2024 |
Masahiro Yamada <[email protected]> |
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.
Conside
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 <[email protected]>
show more ...
|
| #
a16219bd |
| 08-Sep-2024 |
Masahiro Yamada <[email protected]> |
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 scri
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 <[email protected]>
show more ...
|