Subject: Re: Bash-specific performance by avoiding sed

From: Pavel Raiskup <[email-masked]>
Date: Mon, 05 Oct 2015 01:25:24 +0200

On Monday 05 of October 2015 00:45:50 Pavel Raiskup wrote:
> > should we test the size of the string first ?  i've written such raw shell 
> > string parsing functions before, and once you hit a certain size (like 1k+ 
> > iirc), forking out to sed is way faster, especially when running in multibyte 
> > locales (like UTF8) which most people are doing nowadays.
> > -mike
> 
> Well, that optimization would require (fast) strlen()-like construct.
> Anyway, the vast majority of calls to func_quote () function will have
> short ARG, and its complexity is still "just" linear.  We could optimize
> later if that was a real issue.
> 
> I would like to propose solution based on Eric's one, without using of
> '${VAR%.}' and '${VAR#.}' constructs -- sounds like this could be even
> more portable while it keeps almost the same speed (if we can use += its
> even faster).
> 
> I have yet a another patch trying to minimize option-parser overhead
> (that is focused on the POV of Richard, but that needs to be cleaned up a
> bit, I'll post hopefully tomorrow).
> 
> Any comment is welcome!

Re-attached (fixes for 'make syntax-check' and fixed one comment).

Pavel
>From f6935309a07b2a4797ff5612bff00ced4842c3e5 Mon Sep 17 00:00:00 2001
From: Pavel Raiskup <[email-masked]>
Date: Sun, 4 Oct 2015 21:55:03 +0200
Subject: [PATCH] libtool: mitigate the $sed_quote_subst slowdown

References:
http://lists.gnu.org/archive/html/libtool/2015-03/msg00005.html
http://lists.gnu.org/archive/html/libtool/2015-02/msg00000.html
https://debbugs.gnu.org/cgi/bugreport.cgi?bug=20006

* gl/build-aux/funclib.sh (func_quote): New function that can be
used as substition for '$SED $sed_quote_subst' call.
* build-aux/ltmain.in (func_emit_wrapper): Use func_quote instead
of '$SED $sed_quote_subst'.
(func_mode_link): Likewise.
* NEWS: Document.
* bootstrap: Sync with funclib.sh.
---
 NEWS                    |  3 +++
 bootstrap               | 49 +++++++++++++++++++++++++++++++++++++++++++++++--
 build-aux/ltmain.in     | 10 ++++++----
 gl/build-aux/funclib.sh | 49 +++++++++++++++++++++++++++++++++++++++++++++++--
 4 files changed, 103 insertions(+), 8 deletions(-)

diff --git a/NEWS b/NEWS
index a3c5b12..7c23d03 100644
--- a/NEWS
+++ b/NEWS
@@ -17,6 +17,9 @@ NEWS - list of user-visible changes between releases of GNU Libtool
   - Fix significant slowdown of libtoolize for certain projects (regression
     introduced in 2.4.3 release) caused by infinite m4 macro recursion.
 
+  - Mitigate the slowdown of libtool script (introduced in v2.4.3) caused by
+    increased number of calls to '$SED $sed_quote_subst' (bug#20006).
+
 * Noteworthy changes in release 2.4.6 (2015-02-15) [stable]
 
 ** New features:
diff --git a/bootstrap b/bootstrap
index c179f51..c2f6545 100755
--- a/bootstrap
+++ b/bootstrap
@@ -230,7 +230,7 @@ vc_ignore=
 
 # Source required external libraries:
 # Set a version string for this script.
-scriptversion=2015-01-20.17; # UTC
+scriptversion=2015-10-04.22; # UTC
 
 # General shell script boiler plate, and helper functions.
 # Written by Gary V. Vaughan, 2004
@@ -1257,6 +1257,50 @@ func_relative_path ()
 }

+# func_quote ARG
+# --------------
+# Aesthetically quote one ARG, store the result into $func_quote_result.  Note
+# that we keep attention to performance here (so far O(N) complexity as long as
+# func_append is O(1)).
+func_quote ()
+{
+    $debug_cmd
+
+    func_quote_result=$1
+    func_quote_old_IFS=$IFS
+
+    case $func_quote_result in
+      *[\\\`\"\$]*)
+        for _G_char in '\' '`' '"' '$'
+        do
+          # STATE($1) PREV($2) SEPARATOR($3)
+          set start "" ""
+          func_quote_result=dummy"$_G_char$func_quote_result$_G_char"dummy
+          IFS=$_G_char
+          for _G_part in $func_quote_result
+          do
+            case $1 in
+            quote)
+              func_append func_quote_result "$3$2"
+              set quote "$_G_part" "\\$_G_char"
+              ;;
+            start)
+              set first "" ""
+              func_quote_result=
+              ;;
+            first)
+              set quote "$_G_part" ""
+              ;;
+            esac
+          done
+          IFS=$func_quote_old_IFS
+        done
+        ;;
+      *) ;;
+    esac
+}
+
+
 # func_quote_for_eval ARG...
 # --------------------------
 # Aesthetically quote ARGs to be evaled later.
@@ -1275,7 +1319,8 @@ func_quote_for_eval ()
     while test 0 -lt $#; do
       case $1 in
         *[\\\`\"\$]*)
-	  _G_unquoted_arg=`printf '%s\n' "$1" |$SED "$sed_quote_subst"` ;;
+          func_quote "$1"
+          _G_unquoted_arg=$func_quote_result ;;
         *)
           _G_unquoted_arg=$1 ;;
       esac
diff --git a/build-aux/ltmain.in b/build-aux/ltmain.in
index 0c40da0..24acefd 100644
--- a/build-aux/ltmain.in
+++ b/build-aux/ltmain.in
@@ -3346,7 +3346,8 @@ else
   if test \"\$libtool_execute_magic\" != \"$magic\"; then
     file=\"\$0\""
 
-    qECHO=`$ECHO "$ECHO" | $SED "$sed_quote_subst"`
+    func_quote "$ECHO"
+    qECHO=$func_quote_result
     $ECHO "\
 
 # A function that is used when there is no print builtin or printf.
@@ -8596,8 +8597,8 @@ EOF
 	    relink_command="$var=$func_quote_for_eval_result; export $var; $relink_command"
 	  fi
 	done
-	relink_command="(cd `pwd`; $relink_command)"
-	relink_command=`$ECHO "$relink_command" | $SED "$sed_quote_subst"`
+	func_quote "(cd `pwd`; $relink_command)"
+	relink_command=$func_quote_result
       fi
 
       # Only actually do things if not in dry run mode.
@@ -8843,7 +8844,8 @@ EOF
       done
       # Quote the link command for shipping.
       relink_command="(cd `pwd`; $SHELL \"$progpath\" $preserve_args --mode=relink $libtool_args @inst_prefix_dir@)"
-      relink_command=`$ECHO "$relink_command" | $SED "$sed_quote_subst"`
+      func_quote "$relink_command"
+      relink_command=$func_quote_result
       if test yes = "$hardcode_automatic"; then
 	relink_command=
       fi
diff --git a/gl/build-aux/funclib.sh b/gl/build-aux/funclib.sh
index 39d972e..1a406cd 100644
--- a/gl/build-aux/funclib.sh
+++ b/gl/build-aux/funclib.sh
@@ -1,5 +1,5 @@
 # Set a version string for this script.
-scriptversion=2015-01-20.17; # UTC
+scriptversion=2015-10-04.22; # UTC
 
 # General shell script boiler plate, and helper functions.
 # Written by Gary V. Vaughan, 2004
@@ -1026,6 +1026,50 @@ func_relative_path ()
 }

+# func_quote ARG
+# --------------
+# Aesthetically quote one ARG, store the result into $func_quote_result.  Note
+# that we keep attention to performance here (so far O(N) complexity as long as
+# func_append is O(1)).
+func_quote ()
+{
+    $debug_cmd
+
+    func_quote_result=$1
+    func_quote_old_IFS=$IFS
+
+    case $func_quote_result in
+      *[\\\`\"\$]*)
+        for _G_char in '\' '`' '"' '$'
+        do
+          # STATE($1) PREV($2) SEPARATOR($3)
+          set start "" ""
+          func_quote_result=dummy"$_G_char$func_quote_result$_G_char"dummy
+          IFS=$_G_char
+          for _G_part in $func_quote_result
+          do
+            case $1 in
+            quote)
+              func_append func_quote_result "$3$2"
+              set quote "$_G_part" "\\$_G_char"
+              ;;
+            start)
+              set first "" ""
+              func_quote_result=
+              ;;
+            first)
+              set quote "$_G_part" ""
+              ;;
+            esac
+          done
+          IFS=$func_quote_old_IFS
+        done
+        ;;
+      *) ;;
+    esac
+}
+
+
 # func_quote_for_eval ARG...
 # --------------------------
 # Aesthetically quote ARGs to be evaled later.
@@ -1044,7 +1088,8 @@ func_quote_for_eval ()
     while test 0 -lt $#; do
       case $1 in
         *[\\\`\"\$]*)
-	  _G_unquoted_arg=`printf '%s\n' "$1" |$SED "$sed_quote_subst"` ;;
+          func_quote "$1"
+          _G_unquoted_arg=$func_quote_result ;;
         *)
           _G_unquoted_arg=$1 ;;
       esac
-- 
2.5.0