graph-depends: optimize remove_transitive_deps()
PATCH 1/1 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
--- support/scripts/graph-depends | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+)
support/scripts/graph-depends +27 -0
@@ -237,16 +237,43 @@ for dep in dependencies: dict_deps[dep[0]] = [] dict_deps[dep[0]].append(dep[1]) +# 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): + if is_dep_cache.has_key(pkg): + is_dep_cache[pkg].update({pkg2: val}) + else: + is_dep_cache[pkg] = {pkg2: val} + +# Returns a tuple (r, val), where r is a boolean that indicates if a +# value was found in the cache or not, and val being the value found +# (only when r is True). +def is_dep_cache_lookup(pkg, pkg2): + if is_dep_cache.has_key(pkg): + if is_dep_cache[pkg].has_key(pkg2): + return (True, is_dep_cache[pkg][pkg2]) + return (False, False) + # 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): + (r, val) = is_dep_cache_lookup(pkg, pkg2) + if r: + return val if pkg2 in deps: for p in deps[pkg2]: if pkg == p: + is_dep_cache_insert(pkg, pkg2, True) return True if is_dep(pkg,p,deps): + is_dep_cache_insert(pkg, pkg2, True) return True + is_dep_cache_insert(pkg, pkg2, False) return False # This function eliminates transitive dependencies; for example, given
Signature · 1 line
2.6.4
PATCH 1/1 graph-depends: optimize remove_transitive_deps()
Quoted 30 lines · Thomas Petazzoni
For large configurations, the execution time of
remove_transitive_deps()becomes really high, due to the number of nested loops + theis_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 secondsreal 6m39.289s user 6m16.644s sys 0m8.792sBy 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
Quoted 5 lines
real 1m10.201s user 0m47.716s sys 0m7.948sSigned-off-by Thomas Petazzoni <[email protected]>
For a lot of transitive deps (custom package set) the difference is even bigger, akin to hours (previous version) vs 2 minutes (patch applied).
Regards.
PATCH 1/1 graph-depends: optimize remove_transitive_deps()
In reply to Thomas PetazzoniThomas, All,
On 2015-12-15 11:21 +0100, Thomas Petazzoni spake thusly:
Quoted 30 lines
For large configurations, the execution time of
remove_transitive_deps()becomes really high, due to the number of nested loops + theis_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 secondsreal 6m39.289s
user 6m16.644s
sys 0m8.792sBy 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
Quoted 3 lines
real 1m10.201s
user 0m47.716s
sys 0m7.948s
Wee! :-)
Still, somme comments, see below...
I did use the Python profiler to investigate:
python -m cProfile -s cumulative support/scripts/graph-depends >foo.list
Unfortunately, it is not possible to dump a text version to a file... :-( Or I'm too dumb for that. :-]
Quoted 11 lines
Signed-off-by Thomas Petazzoni <[email protected]>--- support/scripts/graph-depends | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+)support/scripts/graph-depends +0
-0@@ -237,16 +237,43 @@ for dep in dependencies: dict_deps[dep[0]] = []
support/scripts/graph-depends for dep in dependencies: · line 247
Quoted 10 lines
support/scripts/graph-depends +8
-0dict_deps[dep[0]].append(dep[1]) +# 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): + if is_dep_cache.has_key(pkg):
if pkg in is_dep_cache
support/scripts/graph-depends for dep in dependencies: · line 259
Quoted 12 lines
support/scripts/graph-depends +12
-0+ is_dep_cache[pkg].update({pkg2: val}) + else: + is_dep_cache[pkg] = {pkg2: val} + +# Returns a tuple (r, val), where r is a boolean that indicates if a +# value was found in the cache or not, and val being the value found +# (only when r is True). +def is_dep_cache_lookup(pkg, pkg2): + if is_dep_cache.has_key(pkg): + if is_dep_cache[pkg].has_key(pkg2): + return (True, is_dep_cache[pkg][pkg2]) + return (False, False)
I think using exceptions is better:
return is_dep_cache[pkg][pkg2]
Don't catch any exception, it'll be propagated up as usual, see below...
Quoted 7 lines
support/scripts/graph-depends +3
-0# 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): + (r, val) = is_dep_cache_lookup(pkg, pkg2) + if r: + return val
support/scripts/graph-depends for dep in dependencies: · line 277
Quoted 10 lines
support/scripts/graph-depends +3
-0if pkg2 in deps: for p in deps[pkg2]: if pkg == p: + is_dep_cache_insert(pkg, pkg2, True) return True if is_dep(pkg,p,deps): + is_dep_cache_insert(pkg, pkg2, True) return True + is_dep_cache_insert(pkg, pkg2, False) return False
Here, I would have dome a bit differently:
- keep is_dep() untouched
- rename is_dep() to is_dep_uncached()
- add is_dep() as such:
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
Not really tested, but should work I hope! ;-)
Regards,
Yann E. MORIN.
Quoted 4 lines
support/scripts/graph-depends +0
-0# This function eliminates transitive dependencies; for example, givenSignature · 1 line
2.6.4
Signature · 6 lines
.-----------------.--------------------.------------------.--------------------. | Yann E. MORIN | Real-Time Embedded | /"\ ASCII RIBBON | Erics' conspiracy: | | +33 662 376 056 | Software Designer | \ / CAMPAIGN | ___ | | +33 223 225 172 `------------.-------: X AGAINST | \e/ There is no | | http://ymorin.is-a-geek.org/ | _/*\_ | / \ HTML MAIL | v conspiracy. | '------------------------------^-------^------------------^--------------------'
PATCH 1/1 graph-depends: optimize remove_transitive_deps()
Hi Thomas, Yann, all,
Quoted 36 lines · Yann E. MORIN
Thomas, All,
On 2015-12-15 11:21 +0100, Thomas Petazzoni spake thusly:
Quoted 33 lines
For large configurations, the execution time of
remove_transitive_deps()becomes really high, due to the number of nested loops + theis_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 secondsreal 6m39.289s
user 6m16.644s
sys 0m8.792sBy 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 secondsreal 1m10.201s
user 0m47.716s
sys 0m7.948s
Impressive! :-)
Quoted 50 lines
Wee! :-)
Still, somme comments, see below...
I did use the Python profiler to investigate:
python -m cProfile -s cumulative support/scripts/graph-depends >foo.listUnfortunately, it is not possible to dump a text version to a file... :-( Or I'm too dumb for that. :-]
Quoted 11 lines
Signed-off-by Thomas Petazzoni <[email protected]>--- support/scripts/graph-depends | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+)support/scripts/graph-depends +0
-0@@ -237,16 +237,43 @@ for dep in dependencies: dict_deps[dep[0]] = []support/scripts/graph-depends for dep in dependencies: · line 247
Quoted 10 lines
support/scripts/graph-depends +8
-0dict_deps[dep[0]].append(dep[1]) +# 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): + if is_dep_cache.has_key(pkg):if pkg in
is_dep_cachesupport/scripts/graph-depends for dep in dependencies: · line 259
Quoted 12 lines
support/scripts/graph-depends +12
-0+ is_dep_cache[pkg].update({pkg2: val}) + else: + is_dep_cache[pkg] = {pkg2: val} + +# Returns a tuple (r, val), where r is a boolean that indicates if a +# value was found in the cache or not, and val being the value found +# (only when r is True). +def is_dep_cache_lookup(pkg, pkg2): + if is_dep_cache.has_key(pkg): + if is_dep_cache[pkg].has_key(pkg2): + return (True, is_dep_cache[pkg][pkg2]) + return (False, False)I think using exceptions is better:
Quoted 3 lines
return is_dep_cache[pkg][pkg2]
Don't catch any exception, it'll be propagated up as usual, see below...
Well, since this patch is about performance optimization, exception should be avoided because they are expensive [1].
But in the end, the choice will also depends on the maintainability of one or the other option.
Quoted 49 lines
Quoted 8 lines
support/scripts/graph-depends +3
-0# 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): + (r, val) = is_dep_cache_lookup(pkg, pkg2) + if r: + return valsupport/scripts/graph-depends for dep in dependencies: · line 277
Quoted 10 lines
support/scripts/graph-depends +3
-0if pkg2 in deps: for p in deps[pkg2]: if pkg == p: + is_dep_cache_insert(pkg, pkg2, True) return True if is_dep(pkg,p,deps): + is_dep_cache_insert(pkg, pkg2, True) return True + is_dep_cache_insert(pkg, pkg2, False) return FalseHere, I would have dome a bit differently:
- keep
is_dep()untouched
- renameis_dep()tois_dep_uncached()
- addis_dep()as such:def
is_dep(pkg,pkg2,deps):
try:
returnis_dep_cache_lookup(pkg,pkg2)
except KeyError:
val =is_dep_uncached(pkg, pkg2, deps)is_dep_cache_insert(pkg, pkg2, val)return valNot really tested, but should work I hope! ;-)
Regards,
Yann E. MORIN.Quoted 4 lines
support/scripts/graph-depends +0
-1# This function eliminates transitive dependencies; for example, given --2.6.4
--
.-----------------.--------------------.------------------.--------------------.| Yann E. MORIN | Real-Time Embedded | /"\ ASCII RIBBON | Erics' conspiracy: | | +33 662 376 056 | Software Designer | \ / CAMPAIGN | ___ | | +33 223 225 172 `------------.-------: X AGAINST | \e/ There is no | | http://ymorin.is-a-geek.org/ | _/*\_ | / \ HTML MAIL | v conspiracy. |
Quoted 5 lines
'------------------------------^-------^------------------^--------------------'
_______________________________________________
buildroot mailing list
buildroot at busybox.net
http://lists.busybox.net/mailman/listinfo/buildroot
Regards,
Signature · 1 line
Samuel
PATCH 1/1 graph-depends: optimize remove_transitive_deps()
Quoted 94 lines · Samuel Martin
Hi Thomas, Yann, all,
Quoted 36 lines · Yann E. MORIN
Thomas, All,
On 2015-12-15 11:21 +0100, Thomas Petazzoni spake thusly:
Quoted 33 lines
For large configurations, the execution time of
remove_transitive_deps()becomes really high, due to the number of nested loops + theis_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 secondsreal 6m39.289s
user 6m16.644s
sys 0m8.792sBy 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 secondsreal 1m10.201s
user 0m47.716s
sys 0m7.948sImpressive! :-)
Quoted 52 lines
Wee! :-)
Still, somme comments, see below...
I did use the Python profiler to investigate:
python -m cProfile -s cumulative support/scripts/graph-depends >foo.listUnfortunately, it is not possible to dump a text version to a file... :-( Or I'm too dumb for that. :-]
Quoted 11 lines
Signed-off-by Thomas Petazzoni <[email protected]>--- support/scripts/graph-depends | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+)support/scripts/graph-depends +0
-0@@ -237,16 +237,43 @@ for dep in dependencies: dict_deps[dep[0]] = []support/scripts/graph-depends for dep in dependencies: · line 247
Quoted 10 lines
support/scripts/graph-depends +8
-0dict_deps[dep[0]].append(dep[1]) +# 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): + if is_dep_cache.has_key(pkg):if pkg in
is_dep_cachesupport/scripts/graph-depends for dep in dependencies: · line 259
Quoted 12 lines
support/scripts/graph-depends +12
-0+ is_dep_cache[pkg].update({pkg2: val}) + else: + is_dep_cache[pkg] = {pkg2: val} + +# Returns a tuple (r, val), where r is a boolean that indicates if a +# value was found in the cache or not, and val being the value found +# (only when r is True). +def is_dep_cache_lookup(pkg, pkg2): + if is_dep_cache.has_key(pkg): + if is_dep_cache[pkg].has_key(pkg2): + return (True, is_dep_cache[pkg][pkg2]) + return (False, False)I think using exceptions is better:
return is_dep_cache[pkg][pkg2]
Quoted 8 lines
Quoted 1 line
Don't catch any exception, it'll be propagated up as usual, see below...
Well, since this patch is about performance optimization, exception should be avoided because they are expensive [1].
But in the end, the choice will also depends on the maintainability of one or the other option.
forgot the ref.:
[1] https://mail.python.org/pipermail/tutor/2003-January/019812.html
Quoted 59 lines
Quoted 49 lines
Quoted 8 lines
support/scripts/graph-depends +3
-0# 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): + (r, val) = is_dep_cache_lookup(pkg, pkg2) + if r: + return valsupport/scripts/graph-depends for dep in dependencies: · line 277
Quoted 10 lines
support/scripts/graph-depends +3
-0if pkg2 in deps: for p in deps[pkg2]: if pkg == p: + is_dep_cache_insert(pkg, pkg2, True) return True if is_dep(pkg,p,deps): + is_dep_cache_insert(pkg, pkg2, True) return True + is_dep_cache_insert(pkg, pkg2, False) return FalseHere, I would have dome a bit differently:
- keep
is_dep()untouched
- renameis_dep()tois_dep_uncached()
- addis_dep()as such:def
is_dep(pkg,pkg2,deps):
try:
returnis_dep_cache_lookup(pkg,pkg2)
except KeyError:
val =is_dep_uncached(pkg, pkg2, deps)is_dep_cache_insert(pkg, pkg2, val)return valNot really tested, but should work I hope! ;-)
Regards,
Yann E. MORIN.Quoted 4 lines
support/scripts/graph-depends +0
-1# This function eliminates transitive dependencies; for example, given --2.6.4
--
.-----------------.--------------------.------------------.--------------------.| Yann E. MORIN | Real-Time Embedded | /"\ ASCII RIBBON | Erics' conspiracy: | | +33 662 376 056 | Software Designer | \ / CAMPAIGN | ___ | | +33 223 225 172 `------------.-------: X AGAINST | \e/ There is no | | http://ymorin.is-a-geek.org/ | _/*\_ | / \ HTML MAIL | v conspiracy. |Quoted 5 lines
'------------------------------^-------^------------------^--------------------'
_______________________________________________
buildroot mailing list
buildroot at busybox.net
http://lists.busybox.net/mailman/listinfo/buildrootRegards,
--
Samuel
Signature · 1 line
Samuel
PATCH 1/1 graph-depends: optimize remove_transitive_deps()
In reply to Thomas PetazzoniHello,
Quoted 30 lines · Thomas Petazzoni
For large configurations, the execution time of
remove_transitive_deps()becomes really high, due to the number of nested loops + theis_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 secondsreal 6m39.289s
user 6m16.644s
sys 0m8.792sBy 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
Quoted 8 lines
real 1m10.201s
user 0m47.716s
sys 0m7.948sSigned-off-by Thomas Petazzoni <[email protected]>--- support/scripts/graph-depends | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+)
I've applied an improved version provided by Yann E. Morin, implementing the various suggestions he has made (mainly using exceptions, and making the code more pythonic).
Thanks!
Thomas
Signature · 3 lines
Thomas Petazzoni, CTO, Free Electrons Embedded Linux, Kernel and Android engineering http://free-electrons.com