From 70a9eb0668b51934f8d79f0c037d65aeb440bcef Mon Sep 17 00:00:00 2001 From: Ulf Magnusson Date: Wed, 1 Nov 2017 02:02:45 +0100 Subject: Switch to a much faster invalidation algorithm _cached_vis is always calculated as a side effect of calculating any other cached value, and so doubles as a flag for whether an item (symbol or choice) has any cached values. If _cached_vis is None for some item, it also indirectly means that no other item can have any cached values that (actually) depend on the item, because _cached_vis would have gotten calculated as a side effect of calculating any such cached value. Therefore, it's safe to stop recursive invalidation at an item that has _cached_vis None. Huge speedup for the allyes/noconfig*.py scripts. allnoconfig_simpler.py went from 2.671 seconds to 1.067 seconds. The dependency selftests need to be updated too now that _get_dependent() is gone. The kernel defconfig tests pass even if all global invalidation is disabled at least (except for the few defconfigs that don't set MODULES=y), and that's a huge invalidation test. Seems pretty speedy too, even though there's some redundant work, so maybe things could be simplified a bit... --- testsuite.py | 62 +++++++++++++++++++++++++++++++----------------------------- 1 file changed, 32 insertions(+), 30 deletions(-) (limited to 'testsuite.py') diff --git a/testsuite.py b/testsuite.py index 9ebcef7..4cfc245 100644 --- a/testsuite.py +++ b/testsuite.py @@ -1700,39 +1700,41 @@ g c = Kconfig("Kconfiglib/tests/Kdep") - def verify_dependent(sym_name, deps_names): - sym = c.syms[sym_name] - deps = [c.syms[name] for name in deps_names] - sym_deps = sym._get_dependent() - verify(len(sym_deps) == len(set(sym_deps)), - "{}'s dependencies contains duplicates".format(sym_name)) - sym_deps = [item for item in sym_deps - if not isinstance(item, Choice)] - verify(len(sym_deps) == len(deps), - "Wrong number of dependent symbols for {}".format(sym_name)) - for dep in deps: - verify(dep in sym_deps, "{} should depend on {}". - format(dep.name, sym_name)) - - # Test twice to cover dependency caching - for i in range(0, 2): - n_deps = 39 - # Verify that D1, D2, .., D are dependent on D - verify_dependent("D", ("D{}".format(i) for i in range(1, n_deps + 1))) - # Choices - verify_dependent("A", ("B", "C")) - verify_dependent("B", ("A", "C")) - verify_dependent("C", ("A", "B")) - verify_dependent("S", ("A", "B", "C")) + # TODO: reintroduce these somehow + + #def verify_dependent(sym_name, deps_names): + # sym = c.syms[sym_name] + # deps = [c.syms[name] for name in deps_names] + # sym_deps = sym._get_dependent() + # verify(len(sym_deps) == len(set(sym_deps)), + # "{}'s dependencies contains duplicates".format(sym_name)) + # sym_deps = [item for item in sym_deps + # if not isinstance(item, Choice)] + # verify(len(sym_deps) == len(deps), + # "Wrong number of dependent symbols for {}".format(sym_name)) + # for dep in deps: + # verify(dep in sym_deps, "{} should depend on {}". + # format(dep.name, sym_name)) + + ## Test twice to cover dependency caching + #for i in range(0, 2): + # n_deps = 39 + # # Verify that D1, D2, .., D are dependent on D + # verify_dependent("D", ("D{}".format(i) for i in range(1, n_deps + 1))) + # # Choices + # verify_dependent("A", ("B", "C")) + # verify_dependent("B", ("A", "C")) + # verify_dependent("C", ("A", "B")) + # verify_dependent("S", ("A", "B", "C")) # Verify that the last symbol depends on the first in a long chain of # dependencies. Test twice to cover dependency caching. - c = Kconfig("Kconfiglib/tests/Kchain") + #c = Kconfig("Kconfiglib/tests/Kchain") - for i in range(0, 2): - verify(c.syms["CHAIN_26"] in c.syms["CHAIN_1"]._get_dependent(), - "Dependency chain broken") + #for i in range(0, 2): + # verify(c.syms["CHAIN_26"] in c.syms["CHAIN_1"]._get_dependent(), + # "Dependency chain broken") print("Testing compatibility with weird selects/implies...") @@ -1920,7 +1922,7 @@ def test_sanity(conf, arch): verify(sym not in conf.const_syms, sym.name + " in both 'syms' and 'const_syms'") - for dep in sym._direct_dependents: + for dep in sym._dependents: verify(not dep.is_constant, "the constant symbol {} depends on {}" .format(dep.name, sym.name)) @@ -1956,7 +1958,7 @@ def test_sanity(conf, arch): verify(not sym.nodes, '"{}" is constant but has menu nodes'.format(sym.name)) - verify(not sym._direct_dependents, + verify(not sym._dependents, '"{}" is constant but is a dependency of some symbol' .format(sym.name)) -- cgit v1.2.3