[1/3] configure: speed up flatten_extralibs_wrapper()

Message ID 20180917025301.10812-1-jamrial@gmail.com
State New
Headers show
Series
  • [1/3] configure: speed up flatten_extralibs_wrapper()
Related show

Commit Message

James Almer Sept. 17, 2018, 2:52 a.m.
From: Avi Halachmi <avihpit@yahoo.com>

x50 - x200 faster.

Currently configure spends 50-70% of its runtime inside a single
function: flatten_extralibs[_wrapper] - which does string processing.

During its run, nearly 20K command substitutions (subshells) are used,
including its callees unique() and resolve(), which is the reason
for its lengthy run.

This commit avoids all subshells during its execution, speeding it up
by about two orders of magnitude, and reducing the overall configure
runtime by 50-70% .

resolve() is rewritten to avoid subshells, and in unique() and
flatten_extralibs() we inline the filter[_out] functionality.

Note that logically, unique functionality has more than one possible
output (depending on which of the recurring items is kept). As it
turns out, other parts expect the last recurring item to be kept
(which was the original behavior of uniqie()). This patch preservs
its output order.

Signed-off-by: James Almer <jamrial@gmail.com>
---
 configure | 46 +++++++++++++++++++++++++++++++++-------------
 1 file changed, 33 insertions(+), 13 deletions(-)

Comments

Diego Biurrun Sept. 17, 2018, 6:49 p.m. | #1
On Sun, Sep 16, 2018 at 11:52:59PM -0300, James Almer wrote:
> From: Avi Halachmi <avihpit@yahoo.com>
> 
> x50 - x200 faster.

The set looks very interesting. I've had some ideas on how to speed up
this part of configure already, so I'm doubly happy to see some work
done in that area.

At a first glance these patches seem to apply several optimizations at
once. I'll have to study them in detail.

There is no flatten_extralibs_wrapper() though...

Diego
James Almer Sept. 17, 2018, 7:22 p.m. | #2
On 9/17/2018 3:49 PM, Diego Biurrun wrote:
> On Sun, Sep 16, 2018 at 11:52:59PM -0300, James Almer wrote:
>> From: Avi Halachmi <avihpit@yahoo.com>
>>
>> x50 - x200 faster.
> 
> The set looks very interesting. I've had some ideas on how to speed up
> this part of configure already, so I'm doubly happy to see some work
> done in that area.
> 
> At a first glance these patches seem to apply several optimizations at
> once. I'll have to study them in detail.
> 
> There is no flatten_extralibs_wrapper() though...

Forgot to rename that while porting the patch from ffmpeg, sorry.

On windows this set made a massive difference, going from several
minutes down to one.

> 
> Diego
> _______________________________________________
> libav-devel mailing list
> libav-devel@libav.org
> https://lists.libav.org/mailman/listinfo/libav-devel
>
avih Sept. 17, 2018, 7:42 p.m. | #3
( I'm not registered to the list)
The changes to unique/resolve/flatten_extralibs are all local to each function. That is, each modified function is a stand-alone drop-in replacement for the original function.
flatten_extralibs_wrapper itself was not modified at the original set, but its callees were.
While you don't have flatten_extralibs_wrapper, it seems that your file still has its functionality ( https://git.libav.org/?p=libav.git;a=blob;f=configure;h=48e8536b07cd5569565e5f9082adc9bb3ad1933c;hb=HEAD#l5129 ), and therefore will also gain from the change to unique (unique is not used by flatten_extralibs but is used - and was very slow, from the ffmpeg's wrapper or your equivalent code).
Bottom line, as far as I can tell it should have similar benefits as it did with ffmpeg's configure despite not having the explicit function flatten_extralibs_wrapper .
Avi

 

    On Monday, September 17, 2018 9:49 PM, Diego Biurrun <diego@biurrun.de> wrote:
 

 On Sun, Sep 16, 2018 at 11:52:59PM -0300, James Almer wrote:
> From: Avi Halachmi <avihpit@yahoo.com>
> 
> x50 - x200 faster.

The set looks very interesting. I've had some ideas on how to speed up
this part of configure already, so I'm doubly happy to see some work
done in that area.

At a first glance these patches seem to apply several optimizations at
once. I'll have to study them in detail.

There is no flatten_extralibs_wrapper() though...

Diego

Patch

diff --git a/configure b/configure
index 48e8536b0..be348e881 100755
--- a/configure
+++ b/configure
@@ -689,22 +689,37 @@  prepend(){
     eval "$var=\"$* \$$var\""
 }
 
+reverse () {
+    eval '
+        reverse_out=
+        for v in $'$1'; do
+            reverse_out="$v $reverse_out"
+        done
+        '$1'=$reverse_out
+    '
+}
+
+# keeps the last occurence of each non-unique item
 unique(){
-    var=$1
-    uniq_list=""
-    for tok in $(eval echo \$$var); do
-        uniq_list="$(filter_out $tok $uniq_list) $tok"
+    unique_out=
+    eval unique_in=\$$1
+    reverse unique_in
+    for v in $unique_in; do
+        # " $unique_out" +space such that every item is surrounded with spaces
+        case " $unique_out" in *" $v "*) continue; esac  # already in list
+        unique_out="$unique_out$v "
     done
-    eval "$var=\"${uniq_list}\""
+    reverse unique_out
+    eval $1=\$unique_out
 }
 
 resolve(){
-    var=$1
-    tmpvar=
-    for entry in $(eval echo \$$var); do
-        tmpvar="$tmpvar $(eval echo \$${entry})"
+    resolve_out=
+    eval resolve_in=\$$1
+    for v in $resolve_in; do
+        eval 'resolve_out="$resolve_out$'$v' "'
     done
-    eval "$var=\"${tmpvar}\""
+    eval $1=\$resolve_out
 }
 
 add_cppflags(){
@@ -5097,14 +5112,19 @@  check_deps $CONFIG_LIST       \
            $ALL_COMPONENTS    \
 
 flatten_extralibs(){
-    unset nested_entries
+    nested_entries=
     list_name=$1
     eval list=\$${1}
     for entry in $list; do
         entry_copy=$entry
         resolve entry_copy
-        append nested_entries $(filter '*_extralibs' $entry_copy)
-        flat_entries=$(filter_out '*_extralibs' $entry_copy)
+        flat_entries=
+        for e in $entry_copy; do
+            case $e in
+                *_extralibs) nested_entries="$nested_entries$e ";;
+                          *) flat_entries="$flat_entries$e ";;
+            esac
+        done
         eval $entry="\$flat_entries"
     done
     append $list_name "$nested_entries"