make libtool faster v3

[Ralf Wildenhues]

Episode 3.

There was a hint in the last change as to what happens in this one.

General clue how to find fork bottlenecks in shell scripts:
  ( LC_ALL=C; export LC_ALL;
    sh -x $libtool_cmline_with_many_many_args |
    sort | uniq -c | sort -k1n >output )

Look at both the end of this list and at the bulk with many similar
lines, go for the lines with several plus signs in front of them.
(Mind, the `.' shell command causes `+' AKA $PS4 to be added as well.)

Yes, this patch has to do with the basename thingy.

It does not change anything substantial, it merely factors out most of
the basename and dirname idioms to be found all over ltmain.m4sh using
computed functions $func_basename and $func_dirname.  (The fact that
$func_dirname does a little more than `dirname' should not worry the
user much, it's documented.)

We provide two implementations of each function, a Bourne shell com-
pliant one and an XSI compliant one (again, the latter without forks).
Since most systems either have a suitable shell already or are not used
primarily for application development anyway, this should benefit the
bulk of libtool users while /not/ compromising portability.

We portably try to detect whether the shell works with the XSI variants,
and fall back to the Bourne variants otherwise (the test has small
overhead, two forks).  This part should be checked the most accurately,
I need to know whether any shells barf over the test or maybe even over
parsing the *_xsi functions.  (Tested with ksh M-11/16/88f, M-12/28/93e,
modern pdksh and bash, and a version of the SVR3 Bourne shell, the only
one of them to actually use the *_bourne variants).


OK to apply to HEAD?  Should the functions rather go into general.m4sh?


Side note 1: IMVHO this patch actually enhances readability.  It's not
so much of a speed enhancement.  Testing it took longer than writing it.

Side note 2: Both old and new dirname fail to strip multiple contiguous
slashes when they occur right before the last path component.  I think
this is the wrong thing to do but I *really* didn't want to go through
all code that may rely on this brokenness.  This would take me a
considerable amount of time.

Side note 3: execution times (bash time builtin, fast machine):

      before      new HEAD  LT-1.5.6  thereof:
      speedup v1                      gcc -shared  ar cru
real  0m18.485s   0m9.091s  0m11.225s 0m2.306s     0m0.075s
user  0m7.346s    0m5.119s  0m5.679s  0m1.951s     0m0.056s
sys   0m12.111s   0m3.987s  0m6.599s  0m0.354s     0m0.019s

i.e. libtool proper uses 40% of the time it did before.  Cool.
Still takes almost as long as libtool-1.5.6.  Not great, but ok,
given that the logic is considerably more involved.  (For small
numbers of arguments, this difference is much less pronounced.)

Lowering this significantly will take reorganization of the code
(fewer passes over the arguments, factoring) or rewriting in a
compiled language.

BTW, the quadratic regime is still not visible -- linking half the
number of objects takes roughly 45% of the time for both the libtool
script and the ld/ar executions (I guess that could be different on
platforms other than linux, but is not in our hands anyway).

Regards,
Ralf

        * config/ltmain.m4sh (func_dirname_bourne, func_dirname_xsi,
        func_basename_bourne, func_basename_xsi): New functions,
        implement `basename' and a variant of `dirname', with either
        Bourne or XSI semantics.  $func_dirname and $func_basename
        are set to the appropriate version by detection.
        (all over the map): Make use of these in most occasions.


Index: config/ltmain.m4sh
===================================================================
RCS file: /cvsroot/libtool/libtool/config/ltmain.m4sh,v
retrieving revision 1.28
diff -u -r1.28 ltmain.m4sh
--- config/ltmain.m4sh  29 Nov 2004 21:18:26 -0000      1.28
+++ config/ltmain.m4sh  30 Nov 2004 19:16:44 -0000
@@ -616,6 +616,56 @@
 }
 
 
+# $func_dirname file append nondir_replacement
+# Compute the dirname of FILE.  If nonempty, add APPEND to the result,
+# otherwise set result to NONDIR_REPLACEMENT.  Does not strip multiple
+# contiguous slashes before the last path component.
+# This implementation is portable to all Bourne shells.
+func_dirname_bourne ()
+{
+  # Extract subdirectory from the argument.
+  func_dirname_result=`$ECHO "X$1" | $Xsed -e "$dirname"`
+  if test "X$func_dirname_result" = "X$1"; then
+    func_dirname_result="$3"
+  else
+    func_dirname_result="$func_dirname_result$2"
+  fi
+}
+
+# $func_dirname file append nondir_replacement
+# Compute the dirname of FILE.  If nonempty, add APPEND to the result,
+# otherwise set result to NONDIR_REPLACEMENT.  Does not strip multiple
+# contiguous slashes before the last path component.
+# This implementation is fast but works only for XSI-conformant shells.
+func_dirname_xsi ()
+{
+  case $1 in
+    */* ) func_dirname_result="${1%/*}$2" ;;
+    *   ) func_dirname_result="$3" ;;
+  esac
+}
+
+# $func_basename file
+func_basename_bourne ()
+{
+  func_basename_result=`$ECHO "X$1" | $Xsed -e "$basename"`
+}
+
+# $func_basename file
+func_basename_xsi ()
+{
+  func_basename_result="${1##*/}"
+}
+
+# detect whether to use the XSI or the Bourne variants
+func_dirname=func_dirname_bourne
+func_basename=func_basename_bourne
+( func_dirname_xsi "1/2/3" && test "1/2" = "$func_dirname_result" ) \
+  >/dev/null 2>&1 && func_dirname=func_dirname_xsi
+( func_basename_xsi "1/2/3" && test "3" = "$func_basename_result" ) \
+  >/dev/null 2>&1 && func_basename=func_basename_xsi
+
+
 # func_win32_libid arg
 # return the library type of file 'arg'
 #
@@ -811,7 +859,8 @@
 
        for dlprefile in $dlprefiles; do
          func_echo "extracting global C symbols from \`$dlprefile'"
-         name=`$ECHO "X$dlprefile" | $Xsed -e 's%^.*/%%'`
+         $func_basename "$dlprefile"
+         name="$func_basename_result"
          $opt_dry_run || {
            eval '$ECHO ": $name " >> "$nlist"'
            eval "$NM $dlprefile | $global_symbol_pipe >> '$nlist'"
@@ -971,7 +1020,8 @@
        [[\\/]]* | [[A-Za-z]]:[[\\/]]*) my_xabs="$my_xlib" ;;
        *) my_xabs=`pwd`"/$my_xlib" ;;
       esac
-      my_xlib=`$ECHO "X$my_xlib" | $Xsed -e 's%^.*/%%'`
+      $func_basename "$my_xlib"
+      my_xlib="$func_basename_result"
       my_xdir="$my_gentop/$my_xlib"
 
       func_mkdir_p "$my_xdir"
@@ -1149,7 +1199,10 @@
       ;;
     *)
       # Get the name of the library object.
-      test -z "$libobj" && libobj=`$ECHO "X$srcfile" | $Xsed -e 's%^.*/%%'`
+      test -z "$libobj" && {
+       $func_basename "$srcfile"
+       libobj="$func_basename_result"
+      }
       ;;
     esac
 
@@ -1210,13 +1263,10 @@
       esac
     done
 
-    objname=`$ECHO "X$obj" | $Xsed -e 's%^.*/%%'`
-    xdir=`$ECHO "X$obj" | $Xsed -e 's%/[[^/]]*$%%'`
-    if test "X$xdir" = "X$obj"; then
-      xdir=
-    else
-      xdir=$xdir/
-    fi
+    $func_basename "$obj"
+    objname="$func_basename_result"
+    $func_dirname "$obj" "/" ""
+    xdir="$func_dirname_result"
     lobj=${xdir}$objdir/$objname
 
     test -z "$base_compile" && \
@@ -1481,8 +1531,8 @@
          continue
        fi
 
-       dir=`$ECHO "X$file" | $Xsed -e 's%/[[^/]]*$%%'`
-       test "X$dir" = "X$file" && dir=.
+       $func_dirname "$file" "" "."
+       dir="$func_dirname_result"
 
        if test -f "$dir/$objdir/$dlname"; then
          dir="$dir/$objdir"
@@ -1493,8 +1543,8 @@
 
       *.lo)
        # Just add the directory containing the .lo file.
-       dir=`$ECHO "X$file" | $Xsed -e 's%/[[^/]]*$%%'`
-       test "X$dir" = "X$file" && dir=.
+       $func_dirname "$file" "" "."
+       dir="$func_dirname_result"
        ;;
 
       *)
@@ -1746,9 +1796,10 @@
       destdir="$dest"
       destname=
     else
-      destdir=`$ECHO "X$dest" | $Xsed -e 's%/[[^/]]*$%%'`
-      test "X$destdir" = "X$dest" && destdir=.
-      destname=`$ECHO "X$dest" | $Xsed -e 's%^.*/%%'`
+      $func_dirname "$dest" "" "."
+      destdir="$func_dirname_result"
+      $func_basename "$dest"
+      destname="$func_basename_result"
 
       # Not a directory, so check to see that there is only one file specified.
       set dummy $files
@@ -1813,8 +1864,8 @@
          esac
        fi
 
-       dir=`$ECHO "X$file" | $Xsed -e 's%/[[^/]]*$%%'`/
-       test "X$dir" = "X$file/" && dir=
+       $func_dirname "$file" "/" ""
+       dir="$func_dirname_result"
        dir="$dir$objdir"
 
        if test -n "$relink_command"; then
@@ -1891,7 +1942,8 @@
        fi
 
        # Install the pseudo-library for information purposes.
-       name=`$ECHO "X$file" | $Xsed -e 's%^.*/%%'`
+       $func_basename "$file"
+       name="$func_basename_result"
        instname="$dir/$name"i
        func_show_eval "$install_prog $instname $destdir/$name" 'exit $?'
 
@@ -1906,7 +1958,8 @@
        if test -n "$destname"; then
          destfile="$destdir/$destname"
        else
-         destfile=`$ECHO "X$file" | $Xsed -e 's%^.*/%%'`
+         $func_basename "$file"
+         destfile="$func_basename_result"
          destfile="$destdir/$destfile"
        fi
 
@@ -1942,7 +1995,8 @@
        if test -n "$destname"; then
          destfile="$destdir/$destname"
        else
-         destfile=`$ECHO "X$file" | $Xsed -e 's%^.*/%%'`
+         $func_basename "$file"
+         destfile="$func_basename_result"
          destfile="$destdir/$destfile"
        fi
 
@@ -2026,7 +2080,8 @@
            $opt_dry_run || {
              if test "$finalize" = yes; then
                tmpdir=`func_mktempdir`
-               file=`$ECHO "X$file$stripped_ext" | $Xsed -e 's%^.*/%%'`
+               $func_basename "$file$stripped_ext"
+               file="$func_basename_result"
                outputname="$tmpdir/$file"
                # Replace the output file specification.
                relink_command=`$ECHO "X$relink_command" | $Xsed -e 
'address@hidden@%'"$outputname"'%g'`
@@ -2078,7 +2133,8 @@
     done
 
     for file in $staticlibs; do
-      name=`$ECHO "X$file" | $Xsed -e 's%^.*/%%'`
+      $func_basename "$file"
+      name="$func_basename_result"
 
       # Set up the ranlib parameters.
       oldlib="$destdir/$name"
@@ -2340,12 +2396,8 @@
                fi
 
                # Extract subdirectory from the argument.
-               xdir=`$ECHO "X$arg" | $Xsed -e 's%/[[^/]]*$%%'`
-               if test "X$xdir" = "X$arg"; then
-                 xdir=
-               else
-                 xdir="$xdir/"
-               fi
+               $func_dirname "$arg" "/" ""
+               xdir="$func_dirname_result"
 
                if test "$pic_object" != none; then
                  # Prepend the subdirectory the object is found in.
@@ -2394,12 +2446,8 @@
                # Only an error if not doing a dry-run.
                if $opt_dry_run; then
                  # Extract subdirectory from the argument.
-                 xdir=`$ECHO "X$arg" | $Xsed -e 's%/[[^/]]*$%%'`
-                 if test "X$xdir" = "X$arg"; then
-                   xdir=
-                 else
-                   xdir="$xdir/"
-                 fi
+                 $func_dirname "$arg" "/" ""
+                 xdir="$func_dirname_result"
 
                  pic_object=`$ECHO "X${xdir}${objdir}/${arg}" | $Xsed -e 
"$lo2o"`
                  non_pic_object=`$ECHO "X${xdir}${arg}" | $Xsed -e "$lo2o"`
@@ -2833,12 +2881,8 @@
          fi
 
          # Extract subdirectory from the argument.
-         xdir=`$ECHO "X$arg" | $Xsed -e 's%/[[^/]]*$%%'`
-         if test "X$xdir" = "X$arg"; then
-           xdir=
-         else
-           xdir="$xdir/"
-         fi
+         $func_dirname "$arg" "/" ""
+         xdir="$func_dirname_result"
 
          if test "$pic_object" != none; then
            # Prepend the subdirectory the object is found in.
@@ -2887,12 +2931,8 @@
          # Only an error if not doing a dry-run.
          if $opt_dry_run; then
            # Extract subdirectory from the argument.
-           xdir=`$ECHO "X$arg" | $Xsed -e 's%/[[^/]]*$%%'`
-           if test "X$xdir" = "X$arg"; then
-             xdir=
-           else
-             xdir="$xdir/"
-           fi
+           $func_dirname "$arg" "/" ""
+           xdir="$func_dirname_result"
 
            pic_object=`$ECHO "X${xdir}${objdir}/${arg}" | $Xsed -e "$lo2o"`
            non_pic_object=`$ECHO "X${xdir}${arg}" | $Xsed -e "$lo2o"`
@@ -2955,7 +2995,8 @@
 
     oldlibs=
     # calculate the name of the file, without its directory
-    outputname=`$ECHO "X$output" | $Xsed -e 's%^.*/%%'`
+    $func_basename "$output"
+    outputname="$func_basename_result"
     libobjs_save="$libobjs"
 
     if test -n "$shlibpath_var"; then
@@ -2967,12 +3008,8 @@
     eval sys_lib_search_path=\"$sys_lib_search_path_spec\"
     eval sys_lib_dlsearch_path=\"$sys_lib_dlsearch_path_spec\"
 
-    output_objdir=`$ECHO "X$output" | $Xsed -e 's%/[[^/]]*$%%'`
-    if test "X$output_objdir" = "X$output"; then
-      output_objdir="$objdir"
-    else
-      output_objdir="$output_objdir/$objdir"
-    fi
+    $func_dirname "$output" "/" ""
+    output_objdir="$func_dirname_result$objdir"
     # Create the object directory.
     func_mkdir_p "$output_objdir"
 
@@ -3170,8 +3207,8 @@
                  done
                  if test "X$ll" = "X$old_library" ; then # only static version 
available
                    found=no
-                   ladir=`$ECHO "X$lib" | $Xsed -e 's%/[[^/]]*$%%'`
-                   test "X$ladir" = "X$lib" && ladir="."
+                   $func_dirname "$lib" "" "."
+                   ladir="$func_dirname_result"
                    lib=$ladir/$old_library
                    if test "$linkmode,$pass" = "prog,link"; then
                      compile_deplibs="$deplib $compile_deplibs"
@@ -3330,8 +3367,8 @@
        func_lalib_unsafe_p "$lib" \
          || func_fatal_error "\`$lib' is not a valid libtool archive"
 
-       ladir=`$ECHO "X$lib" | $Xsed -e 's%/[[^/]]*$%%'`
-       test "X$ladir" = "X$lib" && ladir="."
+       $func_dirname "$lib" "" "."
+       ladir="$func_dirname_result"
 
        dlname=
        dlopen=
@@ -3435,7 +3472,8 @@
          fi
          ;;
        esac
-       laname=`$ECHO "X$lib" | $Xsed -e 's%^.*/%%'`
+       $func_basename "$lib"
+       laname="$func_basename_result"
 
        # Find the relevant object directory and library name.
        if test "X$installed" = Xyes; then
@@ -3661,7 +3699,8 @@
 
            # Make a new name for the extract_expsyms_cmds to use
            soroot="$soname"
-           soname=`$ECHO "X$soroot" | $Xsed -e 's/^.*\///'`
+           $func_basename "$soroot"
+           soname="$func_basename_result"
            newlib=libimp-`$ECHO "X$soname" | $Xsed -e 's/^lib//;s/\.dll$//'`.a
 
            # If the library has no export list, then create one now
@@ -3926,8 +3965,8 @@
              case $deplib in
              -L*) path="$deplib" ;;
              *.la)
-               dir=`$ECHO "X$deplib" | $Xsed -e 's%/[[^/]]*$%%'`
-               test "X$dir" = "X$deplib" && dir="."
+               $func_dirname "$deplib" "" "."
+               dir="$func_dirname_result"
                # We need an absolute path.
                case $dir in
                [[\\/]]* | [[A-Za-z]]:[[\\/]]*) absdir="$dir" ;;
@@ -6252,7 +6291,8 @@
          # names appear in distinct ar calls; check, warn and compensate.
            if (for obj in $save_oldobjs
            do
-             $ECHO "X$obj" | $Xsed -e 's%^.*/%%'
+             $func_basename "$obj"
+             $ECHO "$func_basename_result"
            done | sort | sort -uc >/dev/null 2>&1); then
            :
          else
@@ -6343,7 +6383,8 @@
            for deplib in $dependency_libs; do
              case $deplib in
              *.la)
-               name=`$ECHO "X$deplib" | $Xsed -e 's%^.*/%%'`
+               $func_basename "$deplib"
+               name="$func_basename_result"
                eval libdir=`${SED} -n -e 's/^libdir=\(.*\)$/\1/p' $deplib`
                test -z "$libdir" && \
                  func_fatal_error "\`$deplib' is not a valid libtool archive"
@@ -6358,7 +6399,8 @@
            for lib in $dlfiles; do
              case $lib in
              *.la)
-               name=`$ECHO "X$lib" | $Xsed -e 's%^.*/%%'`
+               $func_basename "$lib"
+               name="$func_basename_result"
                eval libdir=`${SED} -n -e 's/^libdir=\(.*\)$/\1/p' $lib`
                test -z "$libdir" && \
                  func_fatal_error "\`$lib' is not a valid libtool archive"
@@ -6376,7 +6418,8 @@
                # eventual linking with the app. that links it) if we
                # didn't already link the preopened objects directly into
                # the library:
-               name=`$ECHO "X$lib" | $Xsed -e 's%^.*/%%'`
+               $func_basename "$lib"
+               name="$func_basename_result"
                eval libdir=`${SED} -n -e 's/^libdir=\(.*\)$/\1/p' $lib`
                test -z "$libdir" && \
                  func_fatal_error "\`$lib' is not a valid libtool archive"
@@ -6497,14 +6540,15 @@
 
     origobjdir="$objdir"
     for file in $files; do
-      dir=`$ECHO "X$file" | $Xsed -e 's%/[[^/]]*$%%'`
-      if test "X$dir" = "X$file"; then
-       dir=.
+      $func_dirname "$file" "" "."
+      dir="$func_dirname_result"
+      if test "X$dir" = X.; then
        objdir="$origobjdir"
       else
        objdir="$dir/$origobjdir"
       fi
-      name=`$ECHO "X$file" | $Xsed -e 's%^.*/%%'`
+      $func_basename "$file"
+      name="$func_basename_result"
       test "$mode" = uninstall && objdir="$dir"
 
       # Remember objdir for removal later, being careful to avoid duplicates