[PATCH] spp: optimize strip_common_prefix function

[PATCH] spp: optimize strip_common_prefix function

[Zhaolong Zhang]

strip_common_prefix() is the hot path that executes on every input file.
This patch sorts and uniqs the $include_paths by length descreasingly.
And with the sorted $include_paths, the for-loop inside strip_common_prefix
can break earlier, thus kernel_metadata task can be sped up by multiple times.

Signed-off-by: Zhaolong Zhang <zhangzl2013@126.com>
---
 tools/spp | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/tools/spp b/tools/spp
index 1150ff3..cba52bb 100755
--- a/tools/spp
+++ b/tools/spp
@@ -125,6 +125,7 @@ strip_common_prefix()
 	if [ $this_len -lt $out_len ]; then
 	    relocated_name=$t
 	    out_len=$this_len
+	    break
 	fi
 	# add a trailing slash to get corner cases where one may
 	# have been added or not dropped
@@ -133,6 +134,7 @@ strip_common_prefix()
 	if [ $this_len -lt $out_len ]; then
 	    relocated_name=$t
 	    out_len=$this_len
+	    break
 	fi
     done
 
@@ -297,6 +299,16 @@ infiles=$@
 
 processed_files=""
 
+# this function also removes duplicated lines by `sort -u`
+sort_by_len_dec()
+{
+        for i in $@; do
+                echo $i
+        done | sort -u | awk '{ print length($0) " " $0; }' | sort -nr | cut -d ' ' -f 2-
+}
+
+include_paths=$(sort_by_len_dec $include_paths)
+
 ##
 ## create variables for use in scripts
 ##
-- 
1.9.1

Re: [PATCH] spp: optimize strip_common_prefix function

[zhangzl2013]

On a Haswell Xeon 3.2GHz machine, iteration on each include_path costs ~12.5ms.
And the total time we can save at best is (0.0125s * n_patches * n_include_paths)

On 8/30/19 10:39 AM, Zhaolong Zhang wrote:
> strip_common_prefix() is the hot path that executes on every input file.
> This patch sorts and uniqs the $include_paths by length descreasingly.
> And with the sorted $include_paths, the for-loop inside strip_common_prefix
> can break earlier, thus kernel_metadata task can be sped up by multiple times.
>
> Signed-off-by: Zhaolong Zhang <zhangzl2013@126.com>
> ---
>   tools/spp | 12 ++++++++++++
>   1 file changed, 12 insertions(+)
>
> diff --git a/tools/spp b/tools/spp
> index 1150ff3..cba52bb 100755
> --- a/tools/spp
> +++ b/tools/spp
> @@ -125,6 +125,7 @@ strip_common_prefix()
>   	if [ $this_len -lt $out_len ]; then
>   	    relocated_name=$t
>   	    out_len=$this_len
> +	    break
>   	fi
>   	# add a trailing slash to get corner cases where one may
>   	# have been added or not dropped
> @@ -133,6 +134,7 @@ strip_common_prefix()
>   	if [ $this_len -lt $out_len ]; then
>   	    relocated_name=$t
>   	    out_len=$this_len
> +	    break
>   	fi
>       done
>   
> @@ -297,6 +299,16 @@ infiles=$@
>   
>   processed_files=""
>   
> +# this function also removes duplicated lines by `sort -u`
> +sort_by_len_dec()
> +{
> +        for i in $@; do
> +                echo $i
> +        done | sort -u | awk '{ print length($0) " " $0; }' | sort -nr | cut -d ' ' -f 2-
> +}
> +
> +include_paths=$(sort_by_len_dec $include_paths)
> +
>   ##
>   ## create variables for use in scripts
>   ##

✗ patchtest: failure for spp: optimize strip_common_prefix function

[Patchwork]

== Series Details ==

Series: spp: optimize strip_common_prefix function
Revision: 1
URL   : https://patchwork.openembedded.org/series/19578/
State : failure

== Summary ==


Thank you for submitting this patch series to OpenEmbedded Core. This is
an automated response. Several tests have been executed on the proposed
series by patchtest resulting in the following failures:



* Issue             Series does not apply on top of target branch [test_series_merge_on_head] 
  Suggested fix    Rebase your series on top of targeted branch
  Targeted branch  master (currently at c8f329fc56)



If you believe any of these test results are incorrect, please reply to the
mailing list (openembedded-core@lists.openembedded.org) raising your concerns.
Otherwise we would appreciate you correcting the issues and submitting a new
version of the patchset if applicable. Please ensure you add/increment the
version number when sending the new version (i.e. [PATCH] -> [PATCH v2] ->
[PATCH v3] -> ...).

---
Guidelines:     https://www.openembedded.org/wiki/Commit_Patch_Message_Guidelines
Test framework: http://git.yoctoproject.org/cgit/cgit.cgi/patchtest
Test suite:     http://git.yoctoproject.org/cgit/cgit.cgi/patchtest-oe

Re: [PATCH] spp: optimize strip_common_prefix function

[Bruce Ashfield]

This needs to go to the linux-yocto list.

Cheers,

Bruce

On Thu, Aug 29, 2019 at 10:42 PM Zhaolong Zhang <zhangzl2013@126.com> wrote:
>
> strip_common_prefix() is the hot path that executes on every input file.
> This patch sorts and uniqs the $include_paths by length descreasingly.
> And with the sorted $include_paths, the for-loop inside strip_common_prefix
> can break earlier, thus kernel_metadata task can be sped up by multiple times.
>
> Signed-off-by: Zhaolong Zhang <zhangzl2013@126.com>
> ---
>  tools/spp | 12 ++++++++++++
>  1 file changed, 12 insertions(+)
>
> diff --git a/tools/spp b/tools/spp
> index 1150ff3..cba52bb 100755
> --- a/tools/spp
> +++ b/tools/spp
> @@ -125,6 +125,7 @@ strip_common_prefix()
>         if [ $this_len -lt $out_len ]; then
>             relocated_name=$t
>             out_len=$this_len
> +           break
>         fi
>         # add a trailing slash to get corner cases where one may
>         # have been added or not dropped
> @@ -133,6 +134,7 @@ strip_common_prefix()
>         if [ $this_len -lt $out_len ]; then
>             relocated_name=$t
>             out_len=$this_len
> +           break
>         fi
>      done
>
> @@ -297,6 +299,16 @@ infiles=$@
>
>  processed_files=""
>
> +# this function also removes duplicated lines by `sort -u`
> +sort_by_len_dec()
> +{
> +        for i in $@; do
> +                echo $i
> +        done | sort -u | awk '{ print length($0) " " $0; }' | sort -nr | cut -d ' ' -f 2-
> +}
> +
> +include_paths=$(sort_by_len_dec $include_paths)
> +
>  ##
>  ## create variables for use in scripts
>  ##
> --
> 1.9.1
>


-- 
- Thou shalt not follow the NULL pointer, for chaos and madness await
thee at its end
- "Use the force Harry" - Gandalf, Star Trek II