path: root/support/scripts
diff options
authorGravatar Thomas Petazzoni <thomas.petazzoni@free-electrons.com>2015-12-15 11:21:41 +0100
committerGravatar Thomas Petazzoni <thomas.petazzoni@free-electrons.com>2015-12-29 23:26:22 +0100
commit5ed60cee1ed5f8a8e93866fc9db9ff890184afce (patch)
tree6abe0a83878544814966604b783028b4ac4cad9f /support/scripts
parentd856fc15c083876e2f96d5f8e0763e6c04be6c19 (diff)
graph-depends: optimize remove_transitive_deps()
For large configurations, the execution time of remove_transitive_deps() becomes really high, due to the number of nested loops + the is_dep() function being recursive. For an allyespackageconfig, the remove_extra_deps() function takes 334 seconds to execute, and the overall time to generate the .dot file is 6 minutes and 39 seconds. Here is a timing of the different graph-depends steps and the overall execution time: Getting dependencies: 42.5735 seconds Turn deps into a dict: 0.0023 seconds Remove extra deps: 334.1542 seconds Get version: 22.4919 seconds Generate .dot: 0.0197 seconds real 6m39.289s user 6m16.644s sys 0m8.792s By adding a very simple cache for the results of is_dep(), we bring down the execution time of the "Remove extra deps" step from 334 seconds to just 4 seconds, reducing the overall execution time to 1 minutes and 10 seconds: Getting dependencies: 42.9546 seconds Turn deps into a dict: 0.0025 seconds Remove extra deps: 4.9643 seconds Get version: 22.1865 seconds Generate .dot: 0.0207 seconds real 1m10.201s user 0m47.716s sys 0m7.948s Signed-off-by: Thomas Petazzoni <thomas.petazzoni@free-electrons.com> Tested-by: Gustavo Zacarias <gustavo.zacarias@free-electrons.com> [yann.morin.1998@free.fr: - rename is_dep() to is_dep_uncached(), keep existig code as-is - add is_dep() as a cached-version of is_dep_uncached() - use constructs more conform with 2to3 - use exceptions (EAFP) rather than check-before-use (LBYL) to be more pythonist; that even decreases the duration yet a little bit more! ] Signed-off-by: Yann E. MORIN <yann.morin.1998@free.fr>
Diffstat (limited to 'support/scripts')
1 files changed, 32 insertions, 2 deletions
diff --git a/support/scripts/graph-depends b/support/scripts/graph-depends
index 5f77038241..e91c9c5b90 100755
--- a/support/scripts/graph-depends
+++ b/support/scripts/graph-depends
@@ -237,18 +237,48 @@ for dep in dependencies:
dict_deps[dep[0]] = []
+# Basic cache for the results of the is_dep() function, in order to
+# optimize the execution time. The cache is a dict of dict of boolean
+# values. The key to the primary dict is "pkg", and the key of the
+# sub-dicts is "pkg2".
+is_dep_cache = {}
+def is_dep_cache_insert(pkg, pkg2, val):
+ try:
+ is_dep_cache[pkg].update({pkg2: val})
+ except KeyError:
+ is_dep_cache[pkg] = {pkg2: val}
+# Retrieves from the cache whether pkg2 is a transitive dependency
+# of pkg.
+# Note: raises a KeyError exception if the dependency is not known.
+def is_dep_cache_lookup(pkg, pkg2):
+ return is_dep_cache[pkg][pkg2]
# This function return True if pkg is a dependency (direct or
# transitive) of pkg2, dependencies being listed in the deps
# dictionary. Returns False otherwise.
-def is_dep(pkg,pkg2,deps):
- if pkg2 in deps:
+# This is the un-cached version.
+def is_dep_uncached(pkg,pkg2,deps):
+ try:
for p in deps[pkg2]:
if pkg == p:
return True
if is_dep(pkg,p,deps):
return True
+ except KeyError:
+ pass
return False
+# See is_dep_full() above; this is the cached version.
+def is_dep(pkg,pkg2,deps):
+ try:
+ return is_dep_cache_lookup(pkg, pkg2)
+ except KeyError:
+ val = is_dep_uncached(pkg, pkg2, deps)
+ is_dep_cache_insert(pkg, pkg2, val)
+ return val
# This function eliminates transitive dependencies; for example, given
# these dependency chain: A->{B,C} and B->{C}, the A->{C} dependency is
# already covered by B->{C}, so C is a transitive dependency of A, via B.