[Qemu-devel] [PATCH for-2.8?] rules.mak: speedup save-vars load-vars

[Qemu-devel] [PATCH for-2.8?] rules.mak: speedup save-vars load-vars

[Paolo Bonzini]

Unnesting variables spends a lot of time parsing and executing foreach
and if functions.  Because actually very few variables have to be
saved and restored, a good strategy is to remember what has to be done
in load-vars, and only iterate the right variables in load-vars.
For save-vars, unroll the foreach loop to provide another small
improvement.

This speeds up a "noop" build from around 15.5 seconds on my laptop
to 11.7 (25% roughly).

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
	I'm wondering if this would be acceptable for 2.8.
	I also have sent patches to GNU make that save another
	20%, down to 9.8 seconds.

 rules.mak | 22 ++++++++++------------
 1 file changed, 10 insertions(+), 12 deletions(-)

diff --git a/rules.mak b/rules.mak
index 0333ae3..c0777d7 100644
--- a/rules.mak
+++ b/rules.mak
@@ -192,15 +192,15 @@ clean: clean-timestamp
 # save-vars
 # Usage: $(call save-vars, vars)
 # Save each variable $v in $vars as save-vars-$v, save their object's
-# variables, then clear $v.
+# variables, then clear $v.  saved-vars-$v caches the list of variables
+# that were saved for the objects, in order to speedup load-vars.
 define save-vars
     $(foreach v,$1,
         $(eval save-vars-$v := $(value $v))
-        $(foreach o,$($v),
-            $(foreach k,cflags libs objs,
-                $(if $($o-$k),
-                    $(eval save-vars-$o-$k := $($o-$k))
-                    $(eval $o-$k := ))))
+        $(eval saved-vars-$v := $(foreach o,$($v), \
+            $(if $($o-cflags), $o-cflags $(eval save-vars-$o-cflags := $($o-cflags))$(eval $o-cflags := )) \
+            $(if $($o-libs), $o-libs $(eval save-vars-$o-libs := $($o-libs))$(eval $o-libs := )) \
+            $(if $($o-objs), $o-objs $(eval save-vars-$o-objs := $($o-objs))$(eval $o-objs := ))))
         $(eval $v := ))
 endef
 
@@ -213,12 +213,10 @@ define load-vars
     $(eval $2-new-value := $(value $2))
     $(foreach v,$1,
         $(eval $v := $(value save-vars-$v))
-        $(foreach o,$($v),
-            $(foreach k,cflags libs objs,
-                $(if $(save-vars-$o-$k),
-                    $(eval $o-$k := $(save-vars-$o-$k))
-                    $(eval save-vars-$o-$k := ))))
-        $(eval save-vars-$v := ))
+        $(foreach o,$(saved-vars-$v),
+            $(eval $o := $(save-vars-$o)) $(eval save-vars-$o := ))
+        $(eval save-vars-$v := )
+        $(eval saved-vars-$v := ))
     $(eval $2 := $(value $2) $($2-new-value))
 endef
 
-- 
2.7.4

Re: [Qemu-devel] [PATCH for-2.8?] rules.mak: speedup save-vars load-vars

[Daniel P. Berrange]

On Wed, Nov 02, 2016 at 05:24:01PM +0100, Paolo Bonzini wrote:
> Unnesting variables spends a lot of time parsing and executing foreach
> and if functions.  Because actually very few variables have to be
> saved and restored, a good strategy is to remember what has to be done
> in load-vars, and only iterate the right variables in load-vars.
> For save-vars, unroll the foreach loop to provide another small
> improvement.
> 
> This speeds up a "noop" build from around 15.5 seconds on my laptop
> to 11.7 (25% roughly).
> 
> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
> ---
> 	I'm wondering if this would be acceptable for 2.8.
> 	I also have sent patches to GNU make that save another
> 	20%, down to 9.8 seconds.
> 
>  rules.mak | 22 ++++++++++------------
>  1 file changed, 10 insertions(+), 12 deletions(-)

I've no objection to your patch right now, but in general I wonder
whether the complexity of unnest-vars is worth it.

What is the intended benefit of using the unnest-vars approach, as
opposed to explicitly including the sub-dir Makefiles and thus directly
adding to the main variables without the recursive expansion step ?

eg today we have:

Makefile.objs:

  util-obj-y = util/

  dummy := $(call unnest-vars,, util-obj-y)

util/Makefile.objs:

  util-obj-y = osdep.o cutils.o unicode.o


Could we instead just do:


Makefile.objs:

  util-obj-y =

  include util/Makefile.objs


util/Makefile.objs:

  util-obj-y += util/osdep.o util/cutils.o util/unicode.o


Yes, you now get the "burden" of adding a directory prefix onto the file
paths, but I don't think that's a big deal, as it is only a one-time
cost when you create a new file, or very rarely move files between dirs.

Without the unnest-vars black magic I think it'd be simpler for mere
mortals to understand what is happening in the makefiles, lowering
the barrier to entry for new contributors to QEMU (and even existing
QEMU contributors who've not had the misfortune of debugging our
recursive make system yet)

Regards,
Daniel
-- 
|: http://berrange.com      -o-    http://www.flickr.com/photos/dberrange/ :|
|: http://libvirt.org              -o-             http://virt-manager.org :|
|: http://entangle-photo.org       -o-    http://search.cpan.org/~danberr/ :|

Re: [Qemu-devel] [PATCH for-2.8?] rules.mak: speedup save-vars load-vars

[Paolo Bonzini]

On 02/11/2016 17:40, Daniel P. Berrange wrote:
> Could we instead just do:
> 
> Makefile.objs:
> 
>   util-obj-y =
>   include util/Makefile.objs
> 
> util/Makefile.objs:
>   util-obj-y += util/osdep.o util/cutils.o util/unicode.o
> 
> Yes, you now get the "burden" of adding a directory prefix onto the file
> paths, but I don't think that's a big deal, as it is only a one-time
> cost when you create a new file, or very rarely move files between dirs.

I don't think the simplification would be that much.  In particular,
note that you would keep some of the complication to process *-cflags,
*-libs and *-objs variables, and you would have additional complication
to handle the prepending of ".." in Makefile.target.

Paolo

> Without the unnest-vars black magic I think it'd be simpler for mere
> mortals to understand what is happening in the makefiles, lowering
> the barrier to entry for new contributors to QEMU (and even existing
> QEMU contributors who've not had the misfortune of debugging our
> recursive make system yet)
> 
> Regards,
> Daniel
> 

Re: [Qemu-devel] [PATCH for-2.8?] rules.mak: speedup save-vars load-vars

[Fam Zheng]

On Wed, 11/02 17:24, Paolo Bonzini wrote:
> Unnesting variables spends a lot of time parsing and executing foreach
> and if functions.  Because actually very few variables have to be
> saved and restored, a good strategy is to remember what has to be done
> in load-vars, and only iterate the right variables in load-vars.
> For save-vars, unroll the foreach loop to provide another small
> improvement.
> 
> This speeds up a "noop" build from around 15.5 seconds on my laptop
> to 11.7 (25% roughly).
> 
> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
> ---
> 	I'm wondering if this would be acceptable for 2.8.

I think that's fine if you don't want to bear the slowness in 2.8. But TBH I
haven't really noticed this as an issue myself. Anyway,

Reviewed-by: Fam Zheng <famz@redhat.com>

> 	I also have sent patches to GNU make that save another
> 	20%, down to 9.8 seconds.

Wow, is there a link to the patch?

Thanks,
Fam

Re: [Qemu-devel] [PATCH for-2.8?] rules.mak: speedup save-vars load-vars

[Paolo Bonzini]

On 03/11/2016 07:16, Fam Zheng wrote:
> On Wed, 11/02 17:24, Paolo Bonzini wrote:
>> Unnesting variables spends a lot of time parsing and executing foreach
>> and if functions.  Because actually very few variables have to be
>> saved and restored, a good strategy is to remember what has to be done
>> in load-vars, and only iterate the right variables in load-vars.
>> For save-vars, unroll the foreach loop to provide another small
>> improvement.
>>
>> This speeds up a "noop" build from around 15.5 seconds on my laptop
>> to 11.7 (25% roughly).
>>
>> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
>> ---
>> 	I'm wondering if this would be acceptable for 2.8.
> 
> I think that's fine if you don't want to bear the slowness in 2.8. But TBH I
> haven't really noticed this as an issue myself. Anyway,
> 
> Reviewed-by: Fam Zheng <famz@redhat.com>
> 
>> 	I also have sent patches to GNU make that save another
>> 	20%, down to 9.8 seconds.
> 
> Wow, is there a link to the patch?

In theory it would be
http://lists.gnu.org/archive/html/bug-make/2016-10/index.html but I
cannot see it there yet.

Anyway it's not rocket science: use strchr instead of a hand-rolled
while loop, improve hash functions, and an optimized version of strpbrk
using SSE2.

Paolo

Re: [Qemu-devel] [PATCH for-2.8?] rules.mak: speedup save-vars load-vars

[Stefan Hajnoczi]

[-- Attachment #1: Type: text/plain, Size: 2889 bytes --]

On Wed, Nov 02, 2016 at 05:24:01PM +0100, Paolo Bonzini wrote:
> Unnesting variables spends a lot of time parsing and executing foreach
> and if functions.  Because actually very few variables have to be
> saved and restored, a good strategy is to remember what has to be done
> in load-vars, and only iterate the right variables in load-vars.
> For save-vars, unroll the foreach loop to provide another small
> improvement.
> 
> This speeds up a "noop" build from around 15.5 seconds on my laptop
> to 11.7 (25% roughly).
> 
> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
> ---
> 	I'm wondering if this would be acceptable for 2.8.
> 	I also have sent patches to GNU make that save another
> 	20%, down to 9.8 seconds.

Sorry but I'd like to stick to the soft freeze policy.  This patch is a
nice improvement but it's not a bug fix.  Let's merge it for 2.9.

>  rules.mak | 22 ++++++++++------------
>  1 file changed, 10 insertions(+), 12 deletions(-)
> 
> diff --git a/rules.mak b/rules.mak
> index 0333ae3..c0777d7 100644
> --- a/rules.mak
> +++ b/rules.mak
> @@ -192,15 +192,15 @@ clean: clean-timestamp
>  # save-vars
>  # Usage: $(call save-vars, vars)
>  # Save each variable $v in $vars as save-vars-$v, save their object's
> -# variables, then clear $v.
> +# variables, then clear $v.  saved-vars-$v caches the list of variables
> +# that were saved for the objects, in order to speedup load-vars.
>  define save-vars
>      $(foreach v,$1,
>          $(eval save-vars-$v := $(value $v))
> -        $(foreach o,$($v),
> -            $(foreach k,cflags libs objs,
> -                $(if $($o-$k),
> -                    $(eval save-vars-$o-$k := $($o-$k))
> -                    $(eval $o-$k := ))))
> +        $(eval saved-vars-$v := $(foreach o,$($v), \
> +            $(if $($o-cflags), $o-cflags $(eval save-vars-$o-cflags := $($o-cflags))$(eval $o-cflags := )) \
> +            $(if $($o-libs), $o-libs $(eval save-vars-$o-libs := $($o-libs))$(eval $o-libs := )) \
> +            $(if $($o-objs), $o-objs $(eval save-vars-$o-objs := $($o-objs))$(eval $o-objs := ))))
>          $(eval $v := ))
>  endef
>  
> @@ -213,12 +213,10 @@ define load-vars
>      $(eval $2-new-value := $(value $2))
>      $(foreach v,$1,
>          $(eval $v := $(value save-vars-$v))
> -        $(foreach o,$($v),
> -            $(foreach k,cflags libs objs,
> -                $(if $(save-vars-$o-$k),
> -                    $(eval $o-$k := $(save-vars-$o-$k))
> -                    $(eval save-vars-$o-$k := ))))
> -        $(eval save-vars-$v := ))
> +        $(foreach o,$(saved-vars-$v),
> +            $(eval $o := $(save-vars-$o)) $(eval save-vars-$o := ))
> +        $(eval save-vars-$v := )
> +        $(eval saved-vars-$v := ))
>      $(eval $2 := $(value $2) $($2-new-value))
>  endef
>  
> -- 
> 2.7.4
> 
> 

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 455 bytes --]

Re: [Qemu-devel] [PATCH for-2.8?] rules.mak: speedup save-vars load-vars

[Paolo Bonzini]

On 07/11/2016 13:49, Stefan Hajnoczi wrote:
> On Wed, Nov 02, 2016 at 05:24:01PM +0100, Paolo Bonzini wrote:
>> Unnesting variables spends a lot of time parsing and executing foreach
>> and if functions.  Because actually very few variables have to be
>> saved and restored, a good strategy is to remember what has to be done
>> in load-vars, and only iterate the right variables in load-vars.
>> For save-vars, unroll the foreach loop to provide another small
>> improvement.
>>
>> This speeds up a "noop" build from around 15.5 seconds on my laptop
>> to 11.7 (25% roughly).
>>
>> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
>> ---
>> 	I'm wondering if this would be acceptable for 2.8.
>> 	I also have sent patches to GNU make that save another
>> 	20%, down to 9.8 seconds.
> 
> Sorry but I'd like to stick to the soft freeze policy.  This patch is a
> nice improvement but it's not a bug fix.  Let's merge it for 2.9.

Fine by me, thanks!

Paolo

>>  rules.mak | 22 ++++++++++------------
>>  1 file changed, 10 insertions(+), 12 deletions(-)
>>
>> diff --git a/rules.mak b/rules.mak
>> index 0333ae3..c0777d7 100644
>> --- a/rules.mak
>> +++ b/rules.mak
>> @@ -192,15 +192,15 @@ clean: clean-timestamp
>>  # save-vars
>>  # Usage: $(call save-vars, vars)
>>  # Save each variable $v in $vars as save-vars-$v, save their object's
>> -# variables, then clear $v.
>> +# variables, then clear $v.  saved-vars-$v caches the list of variables
>> +# that were saved for the objects, in order to speedup load-vars.
>>  define save-vars
>>      $(foreach v,$1,
>>          $(eval save-vars-$v := $(value $v))
>> -        $(foreach o,$($v),
>> -            $(foreach k,cflags libs objs,
>> -                $(if $($o-$k),
>> -                    $(eval save-vars-$o-$k := $($o-$k))
>> -                    $(eval $o-$k := ))))
>> +        $(eval saved-vars-$v := $(foreach o,$($v), \
>> +            $(if $($o-cflags), $o-cflags $(eval save-vars-$o-cflags := $($o-cflags))$(eval $o-cflags := )) \
>> +            $(if $($o-libs), $o-libs $(eval save-vars-$o-libs := $($o-libs))$(eval $o-libs := )) \
>> +            $(if $($o-objs), $o-objs $(eval save-vars-$o-objs := $($o-objs))$(eval $o-objs := ))))
>>          $(eval $v := ))
>>  endef
>>  
>> @@ -213,12 +213,10 @@ define load-vars
>>      $(eval $2-new-value := $(value $2))
>>      $(foreach v,$1,
>>          $(eval $v := $(value save-vars-$v))
>> -        $(foreach o,$($v),
>> -            $(foreach k,cflags libs objs,
>> -                $(if $(save-vars-$o-$k),
>> -                    $(eval $o-$k := $(save-vars-$o-$k))
>> -                    $(eval save-vars-$o-$k := ))))
>> -        $(eval save-vars-$v := ))
>> +        $(foreach o,$(saved-vars-$v),
>> +            $(eval $o := $(save-vars-$o)) $(eval save-vars-$o := ))
>> +        $(eval save-vars-$v := )
>> +        $(eval saved-vars-$v := ))
>>      $(eval $2 := $(value $2) $($2-new-value))
>>  endef
>>  
>> -- 
>> 2.7.4
>>
>>