* [Buildroot] [PATCH] graph-depends: optimize remove_transitive_deps()
@ 2015-12-15 10:21 Thomas Petazzoni
2015-12-15 11:20 ` Gustavo Zacarias
` (2 more replies)
0 siblings, 3 replies; 6+ messages in thread
From: Thomas Petazzoni @ 2015-12-15 10:21 UTC (permalink / raw)
To: buildroot
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>
---
support/scripts/graph-depends | 27 +++++++++++++++++++++++++++
1 file changed, 27 insertions(+)
diff --git a/support/scripts/graph-depends b/support/scripts/graph-depends
index 5f77038..d39306e 100755
--- a/support/scripts/graph-depends
+++ b/support/scripts/graph-depends
@@ -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
--
2.6.4
^ permalink raw reply related [flat|nested] 6+ messages in thread
* [Buildroot] [PATCH] graph-depends: optimize remove_transitive_deps()
2015-12-15 10:21 [Buildroot] [PATCH] graph-depends: optimize remove_transitive_deps() Thomas Petazzoni
@ 2015-12-15 11:20 ` Gustavo Zacarias
2015-12-15 20:37 ` Yann E. MORIN
2015-12-29 22:28 ` Thomas Petazzoni
2 siblings, 0 replies; 6+ messages in thread
From: Gustavo Zacarias @ 2015-12-15 11:20 UTC (permalink / raw)
To: buildroot
On 15/12/15 07:21, Thomas Petazzoni wrote:
> 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>
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.
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Buildroot] [PATCH] graph-depends: optimize remove_transitive_deps()
2015-12-15 10:21 [Buildroot] [PATCH] graph-depends: optimize remove_transitive_deps() Thomas Petazzoni
2015-12-15 11:20 ` Gustavo Zacarias
@ 2015-12-15 20:37 ` Yann E. MORIN
2015-12-15 21:23 ` Samuel Martin
2015-12-29 22:28 ` Thomas Petazzoni
2 siblings, 1 reply; 6+ messages in thread
From: Yann E. MORIN @ 2015-12-15 20:37 UTC (permalink / raw)
To: buildroot
Thomas, All,
On 2015-12-15 11:21 +0100, Thomas Petazzoni spake thusly:
> 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
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. :-]
> Signed-off-by: Thomas Petazzoni <thomas.petazzoni@free-electrons.com>
> ---
> support/scripts/graph-depends | 27 +++++++++++++++++++++++++++
> 1 file changed, 27 insertions(+)
>
> diff --git a/support/scripts/graph-depends b/support/scripts/graph-depends
> index 5f77038..d39306e 100755
> --- a/support/scripts/graph-depends
> +++ b/support/scripts/graph-depends
> @@ -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):
if pkg in is_dep_cache
> + 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...
> # 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
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.
> # 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. |
'------------------------------^-------^------------------^--------------------'
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Buildroot] [PATCH] graph-depends: optimize remove_transitive_deps()
2015-12-15 20:37 ` Yann E. MORIN
@ 2015-12-15 21:23 ` Samuel Martin
2015-12-15 21:27 ` Samuel Martin
0 siblings, 1 reply; 6+ messages in thread
From: Samuel Martin @ 2015-12-15 21:23 UTC (permalink / raw)
To: buildroot
Hi Thomas, Yann, all,
On Tue, Dec 15, 2015 at 9:37 PM, Yann E. MORIN <yann.morin.1998@free.fr> wrote:
> Thomas, All,
>
> On 2015-12-15 11:21 +0100, Thomas Petazzoni spake thusly:
>> 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
Impressive! :-)
>
> 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. :-]
>
>> Signed-off-by: Thomas Petazzoni <thomas.petazzoni@free-electrons.com>
>> ---
>> support/scripts/graph-depends | 27 +++++++++++++++++++++++++++
>> 1 file changed, 27 insertions(+)
>>
>> diff --git a/support/scripts/graph-depends b/support/scripts/graph-depends
>> index 5f77038..d39306e 100755
>> --- a/support/scripts/graph-depends
>> +++ b/support/scripts/graph-depends
>> @@ -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):
>
> if pkg in is_dep_cache
>
>> + 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...
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.
>
>> # 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
>
> 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.
>
>> # 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. |
> '------------------------------^-------^------------------^--------------------'
> _______________________________________________
> buildroot mailing list
> buildroot at busybox.net
> http://lists.busybox.net/mailman/listinfo/buildroot
Regards,
--
Samuel
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Buildroot] [PATCH] graph-depends: optimize remove_transitive_deps()
2015-12-15 21:23 ` Samuel Martin
@ 2015-12-15 21:27 ` Samuel Martin
0 siblings, 0 replies; 6+ messages in thread
From: Samuel Martin @ 2015-12-15 21:27 UTC (permalink / raw)
To: buildroot
On Tue, Dec 15, 2015 at 10:23 PM, Samuel Martin <s.martin49@gmail.com> wrote:
> Hi Thomas, Yann, all,
>
> On Tue, Dec 15, 2015 at 9:37 PM, Yann E. MORIN <yann.morin.1998@free.fr> wrote:
>> Thomas, All,
>>
>> On 2015-12-15 11:21 +0100, Thomas Petazzoni spake thusly:
>>> 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
>
> Impressive! :-)
>
>>
>> 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. :-]
>>
>>> Signed-off-by: Thomas Petazzoni <thomas.petazzoni@free-electrons.com>
>>> ---
>>> support/scripts/graph-depends | 27 +++++++++++++++++++++++++++
>>> 1 file changed, 27 insertions(+)
>>>
>>> diff --git a/support/scripts/graph-depends b/support/scripts/graph-depends
>>> index 5f77038..d39306e 100755
>>> --- a/support/scripts/graph-depends
>>> +++ b/support/scripts/graph-depends
>>> @@ -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):
>>
>> if pkg in is_dep_cache
>>
>>> + 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...
>
> 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
>>
>>> # 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
>>
>> 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.
>>
>>> # 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. |
>> '------------------------------^-------^------------------^--------------------'
>> _______________________________________________
>> buildroot mailing list
>> buildroot at busybox.net
>> http://lists.busybox.net/mailman/listinfo/buildroot
>
> Regards,
>
> --
> Samuel
--
Samuel
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Buildroot] [PATCH] graph-depends: optimize remove_transitive_deps()
2015-12-15 10:21 [Buildroot] [PATCH] graph-depends: optimize remove_transitive_deps() Thomas Petazzoni
2015-12-15 11:20 ` Gustavo Zacarias
2015-12-15 20:37 ` Yann E. MORIN
@ 2015-12-29 22:28 ` Thomas Petazzoni
2 siblings, 0 replies; 6+ messages in thread
From: Thomas Petazzoni @ 2015-12-29 22:28 UTC (permalink / raw)
To: buildroot
Hello,
On Tue, 15 Dec 2015 11:21:41 +0100, Thomas Petazzoni wrote:
> 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>
> ---
> 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
--
Thomas Petazzoni, CTO, Free Electrons
Embedded Linux, Kernel and Android engineering
http://free-electrons.com
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2015-12-29 22:28 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2015-12-15 10:21 [Buildroot] [PATCH] graph-depends: optimize remove_transitive_deps() Thomas Petazzoni
2015-12-15 11:20 ` Gustavo Zacarias
2015-12-15 20:37 ` Yann E. MORIN
2015-12-15 21:23 ` Samuel Martin
2015-12-15 21:27 ` Samuel Martin
2015-12-29 22:28 ` Thomas Petazzoni
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox