package/pkg-generic: speed up RECURSIVE_FINAL_DEPENDENCIES
PATCH 1/1 package/pkg-generic: speed up RECURSIVE_FINAL_DEPENDENCIES
Evaluating all the <PKG>_RECURSIVE_FINAL_DEPENDENCIES variables (abbreviated RFD hereafter) ends up being quite slow. Enough, on a reasonable modern workstation, to increase the time it takes to run "make printvars" from 13 seconds in 2018.02 to 371 seconds in 2019.02.
This patch improves this by using dynamic programming to speed the evaluation of RFD, reducing the before mentioned printvars time to about 14.6 seconds.
The evaluation of PKG1_RFD requires recursively evaluating each of PKG1's dependencies' RFDs, then their dependencies' RFDs, and so on. The same is done for PKG2_RFD. But it's likely that many of the dependencies of PKG2 are the same as PKG1. And when we consider all packages, the dependencies are re-computed many thousands of times.
To avoid this re-computation we memoize, or save, the computed value of each RFD variable when it found the first time. Subsequent evaluations re-use the memoized value.
Surprisingly, this ends up being not all the hard to implement in make. The basic construct is this:
VAR = $(if !defined(VAR__X),$(eval VAR__X := value))$(VAR__X)
The first time VAR is evaluated VAR__X will not be defined, and code to set VAR__X to the computed value is eval'd. Then the now defined value of VAR__X is returned. Subsequent evaluations can just return VAR__X.
It is important to note that VAR is defined with '=', as not enough information (namely, all packages' dependencies) is know when it is parsed to find the correct value. VAR will be evaluated each time it is used. But VAR__X is defined with ":=", so that it is evaluated once when defined, and not each time it is used.
---
I did 20 runs of printvars VARS="%_RFD" of this version vs the one that used strip + sort. Mean was 3.19730 vs 3.13765 seconds, in favor of this one being faster. More importantly, the p-value for a one sided t-test was 0.007353, so the difference is statistically significant. I also compared the time to run "make help", to measure the parse time, and there was not a statistically significant difference.
package/pkg-generic.mk | 19 +++++++++++-------- 1 file changed, 11 insertions(+), 8 deletions(-)
package/pkg-generic.mk +11 -8
@@ -678,14 +678,17 @@ $(2)_FINAL_ALL_DEPENDENCIES = \ $$($(2)_FINAL_DOWNLOAD_DEPENDENCIES) \ $$($(2)_FINAL_EXTRACT_DEPENDENCIES) \ $$($(2)_FINAL_PATCH_DEPENDENCIES)) -$(2)_FINAL_RECURSIVE_DEPENDENCIES = \ - $$(sort \ - $$(foreach p,\ - $$($(2)_FINAL_ALL_DEPENDENCIES),\ - $$(p)\ - $$($$(call UPPERCASE,$$(p))_FINAL_RECURSIVE_DEPENDENCIES)\ - )\ - ) +$(2)_FINAL_RECURSIVE_DEPENDENCIES = $$(sort \ + $$(if $$(filter undefined,$$(origin $(2)_FINAL_RECURSIVE_DEPENDENCIES__X)), \ + $$(eval $(2)_FINAL_RECURSIVE_DEPENDENCIES__X := \ + $$(foreach p, \ + $$($(2)_FINAL_ALL_DEPENDENCIES), \ + $$(p) \ + $$($$(call UPPERCASE,$$(p))_FINAL_RECURSIVE_DEPENDENCIES) \ + ) \ + ) \ + ) \ + $$($(2)_FINAL_RECURSIVE_DEPENDENCIES__X)) $(2)_INSTALL_STAGING ?= NO $(2)_INSTALL_IMAGES ?= NO
Signature · 1 line
2.14.4
PATCH 1/1 package/pkg-generic: speed up RECURSIVE_FINAL_DEPENDENCIES
Teent, All,
On 2019-02-25 23:55 +0000, Trent Piepho spake thusly:
Quoted 15 lines
Evaluating all the <PKG>_RECURSIVE_FINAL_DEPENDENCIES variables (abbreviated RFD hereafter) ends up being quite slow. Enough, on a reasonable modern workstation, to increase the time it takes to run "make printvars" from 13 seconds in 2018.02 to 371 seconds in 2019.02.
This patch improves this by using dynamic programming to speed the evaluation of RFD, reducing the before mentioned printvars time to about 14.6 seconds.
The evaluation of
PKG1_RFDrequires recursively evaluating each of PKG1's dependencies' RFDs, then their dependencies' RFDs, and so on. The same is done forPKG2_RFD. But it's likely that many of the dependencies of PKG2 are the same as PKG1. And when we consider all packages, the dependencies are re-computed many thousands of times.
Quoted 8 lines
To avoid this re-computation we memoize, or save, the computed value of each RFD variable when it found the first time. Subsequent evaluations re-use the memoized value.
Surprisingly, this ends up being not all the hard to implement in make. The basic construct is this:
VAR = $(if !defined(VAR__X),$(eval
VAR__X:= value))$(VAR__X)
Thanks for this: I learnt a very interesting piece of makefile code. I'm eager to re-use it everywhere, now! ;-]
Quoted 10 lines
The first time VAR is evaluated
VAR__Xwill not be defined, and code to setVAR__Xto the computed value is eval'd. Then the now defined value ofVAR__Xis returned. Subsequent evaluations can just returnVAR__X.It is important to note that VAR is defined with '=', as not enough information (namely, all packages' dependencies) is know when it is parsed to find the correct value. VAR will be evaluated each time it is used. But
VAR__Xis defined with ":=", so that it is evaluated once when defined, and not each time it is used.
Quoted 6 lines
Signed-off-by Trent Piepho <[email protected]>---
I did 20 runs of printvars VARS="%_RFD" of this version vs the one that used strip + sort. Mean was 3.19730 vs 3.13765 seconds, in favor of this one being faster.
Here, the timings were slightly reversed, with the strip + sort being a bit faster than just sort. I think it might be due to you and I using different config files, where the dependency depths and widths [0] are different, and thus favour one or the other in intricate manners.
So I did a few randconfigs, and it turns out that indeed the order fluctuates slightly, with sort+strip sometimes wining, sometimes losing.
And either way, the delta is in the sub-second range, now. So I think one is as good as the other, so:
Thank you! :-)
Regards,
Yann E. MORIN.
Quoted 46 lines
More importantly, the p-value for a one sided
t-test was 0.007353, so the difference is statistically significant. I also compared the time to run "make help", to measure the parse time, and there was not a statistically significant difference.package/pkg-generic.mk | 19 +++++++++++-------- 1 file changed, 11 insertions(+), 8 deletions(-)package/pkg-generic.mk +11
-8@@ -678,14 +678,17 @@ $(2)_FINAL_ALL_DEPENDENCIES = \ $$($(2)_FINAL_DOWNLOAD_DEPENDENCIES) \ $$($(2)_FINAL_EXTRACT_DEPENDENCIES) \ $$($(2)_FINAL_PATCH_DEPENDENCIES)) -$(2)_FINAL_RECURSIVE_DEPENDENCIES = \ - $$(sort \ - $$(foreach p,\ - $$($(2)_FINAL_ALL_DEPENDENCIES),\ - $$(p)\ - $$($$(call UPPERCASE,$$(p))_FINAL_RECURSIVE_DEPENDENCIES)\ - )\ - ) +$(2)_FINAL_RECURSIVE_DEPENDENCIES = $$(sort \ + $$(if $$(filter undefined,$$(origin $(2)_FINAL_RECURSIVE_DEPENDENCIES__X)), \ + $$(eval $(2)_FINAL_RECURSIVE_DEPENDENCIES__X := \ + $$(foreach p, \ + $$($(2)_FINAL_ALL_DEPENDENCIES), \ + $$(p) \ + $$($$(call UPPERCASE,$$(p))_FINAL_RECURSIVE_DEPENDENCIES) \ + ) \ + ) \ + ) \ + $$($(2)_FINAL_RECURSIVE_DEPENDENCIES__X)) $(2)_INSTALL_STAGING ?= NO $(2)_INSTALL_IMAGES ?= NOSignature · 6 lines
2.14.4 _______________________________________________ buildroot mailing list buildroot at busybox.net http://lists.busybox.net/mailman/listinfo/buildroot
Signature · 6 lines
.-----------------.--------------------.------------------.--------------------. | Yann E. MORIN | Real-Time Embedded | /"\ ASCII RIBBON | Erics' conspiracy: | | +33 662 376 056 | Software Designer | \ / CAMPAIGN | ___ | | +33 561 099 427 `------------.-------: X AGAINST | \e/ There is no | | http://ymorin.is-a-geek.org/ | _/*\_ | / \ HTML MAIL | v conspiracy. | '------------------------------^-------^------------------^--------------------'
PATCH 1/1 package/pkg-generic: speed up RECURSIVE_FINAL_DEPENDENCIES
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
"Yann" == Yann E MORIN <[email protected]> writes:
Hi,
Quoted 8 lines
Here, the timings were slightly reversed, with the strip + sort being a bit faster than just sort. I think it might be due to you and I using different config files, where the dependency depths and widths [0] are different, and thus favour one or the other in intricate manners.
So I did a few randconfigs, and it turns out that indeed the order fluctuates slightly, with sort+strip sometimes wining, sometimes losing.
Quoted 7 lines
And either way, the delta is in the sub-second range, now. So I think one is as good as the other, so:
Tested-by "Yann E. MORIN" <[email protected]>Acked-by "Yann E. MORIN" <[email protected]>Thank you! :-)
Yes, thanks for the change and detailed commit message.
Committed, thanks.
Signature · 1 line
Bye, Peter Korsgaard