speedup bootstrap

[Ralf Wildenhues]

While working on the outstanding patch queue, I finally got fed up
enough with CVS HEAD bootstrap and all the pizzas I had to eat each
time, that it needed to be fixed.  ;-)

m4 tail recursion sucks performance-wise, if the argument lists are
long, because: even if shift/m4_shiftn is fast(?), the whole stuff needs
to be copied anyway for the new macro call.

Just to make clear just how much of an issue this is: the code recurses
as much as 600 C function calls deep (as seen by randomly interrupting
m4 in a debugger; I haven't attempted to find the true maximum).

So, let's do in some manual tail recursion elimination.

Unmodified, CVS Autoconf:
$ \time ./bootstrap
688.51user 6.78system 12:00.46elapsed 96%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+1760773minor)pagefaults 0swaps

ditto, Autoconf-2.59:
676.61user 6.32system 11:39.15elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+1741926minor)pagefaults 0swaps

After rewriting lt_join and lt_dict_filter, CVS Autoconf:
$ \time ./bootstrap
188.87user 4.57system 3:36.43elapsed 89%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (5major+1202187minor)pagefaults 0swaps

After further rewriting lt_combine, CVS Autoconf:
$ \time ./bootstrap
158.85user 4.04system 3:02.42elapsed 89%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+1094468minor)pagefaults 0swaps

ditto, Autoconf-2.59:
138.17user 3.20system 2:42.03elapsed 87%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+897776minor)pagefaults 0swaps


OK to apply the combined patch below?

Remarks:
- I commented _lt_decl_filter in order to be able to understand it.
- lt_unquote is an ugly helper to get rid of the quotes introduced by
  m4_split.  Is there a documented way (macro to call) to do this?
- all generated configure scripts in the source tree compared equal to
  the previous version, with both CVS HEAD Autoconf and 2.59.
  I hope that uncovered all issues..
- I guess Autoconf could benefit as well from rewriting a few of their
  m4sugar functions.  I believe it can be done similarly, but haven't
  thought of whitespace-in-m4-lists issues yet -- ltsugar does not have
  to deal with those by preserving it.
- Libtool branch-1-5 is still faster to bootstrap (one configure script
  less, by the way; CVS Autoconf):
62.73user 1.79system 1:07.73elapsed 95%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+492214minor)pagefaults 0swaps

- Have I ever mentioned that I am a fan of procedural rather than
  functional languages?  :->
- Should you ever be offered a job that involves m4 macros and is paid
  by changed/created SLOC, no matter how much: turn it down!

With sincere apologies to Gary for doing this before finishing reviews.

Cheers,
Ralf

        * libltdl/m4/ltsugar.m4 (lt_join, lt_combine, lt_dict_filter):
        Rewrite to eliminate tail recursion; use ..
        (lt_unquote): New trivial helper macro.
        * libltdl/m4/libtool.m4 (_lt_decl_filter): Document.

Index: libltdl/m4/libtool.m4
===================================================================
RCS file: /cvsroot/libtool/libtool/libltdl/m4/libtool.m4,v
retrieving revision 1.27
diff -u -r1.27 libtool.m4
--- libltdl/m4/libtool.m4       13 Oct 2005 13:22:55 -0000      1.27
+++ libltdl/m4/libtool.m4       23 Oct 2005 09:02:45 -0000
@@ -335,6 +335,10 @@
 # -------------------------------------------------
 m4_define([lt_decl_tag_varnames],
 [_lt_decl_filter([tagged?], [yes], $@)])
+
+
+# _lt_decl_filter(SUBKEY, VALUE, [SEPARATOR], [VARNAME1..])
+# ---------------------------------------------------------
 m4_define([_lt_decl_filter],
 [m4_case([$#],
   [0], [m4_fatal([$0: too few arguments: $#])],
Index: libltdl/m4/ltsugar.m4
===================================================================
RCS file: /cvsroot/libtool/libtool/libltdl/m4/ltsugar.m4,v
retrieving revision 1.1
diff -u -r1.1 ltsugar.m4
--- libltdl/m4/ltsugar.m4       22 Aug 2005 22:33:35 -0000      1.1
+++ libltdl/m4/ltsugar.m4       23 Oct 2005 09:02:45 -0000
@@ -23,12 +23,12 @@
         [1], [],
         [2], [[$2]],
         [m4_ifval([$2],
-                  [m4_ifval([$3],
-                            [[$2][$1][]$0([$1], m4_shiftn(2, $@))],
-                      [m4_if([$#], [3],
-                             [$2],
-                          [$0([$1], [$2], m4_shiftn(3, $@))])])],
-             [$0([$1], m4_shiftn(2, $@))])])[]dnl
+                  [[$2][]m4_foreach(_lt_Arg, lt_car([m4_shiftn(2, $@)]),
+                          [_$0([$1], _lt_Arg)])],
+                  [$0([$1], m4_shiftn(2, $@))])])[]dnl
+])
+m4_define([_lt_join],
+[m4_ifval([$2],[$1][$2])[]dnl
 ])
 
 
@@ -43,6 +43,7 @@
 [m4_if([$#], 0, [m4_fatal([$0: cannot be called without arguments])],
        [$#], 1, [],
        [m4_dquote(m4_shift($@))])])
+m4_define([lt_unquote], $1)
 
 
 # lt_combine(SEP, PREFIX-LIST, INFIX, SUFFIX1, [SUFFIX2...])
@@ -52,14 +53,11 @@
 # has the form PREFIXmINFIXSUFFIXn.
 m4_define([lt_combine],
 [m4_if([$2], [], [],
-       [lt_join(m4_quote(m4_default([$1], [[, ]])),
-               _$0([$1], lt_car($2)[$3], m4_shiftn(3, $@)),
-               $0([$1], lt_cdr($2), m4_shiftn(2, $@)))])])
-m4_define([_lt_combine],
-[m4_if([$3], [], [],
-       [lt_join(m4_quote(m4_default([$1], [[, ]])),
-               [$2$3],
-               $0([$1], [$2], m4_shiftn(3, $@)))])[]dnl
+  [m4_if([$4], [], [],
+    [lt_join(m4_quote(m4_default([$1], [[, ]])),
+      lt_unquote(m4_split(m4_normalize(m4_foreach(_Lt_prefix, [$2],
+                          [m4_foreach(_Lt_suffix, lt_car([m4_shiftn(3, $@)]),
+                              [_Lt_prefix[]$3[]_Lt_suffix ])])))))])])dnl
 ])
 
 
@@ -104,10 +102,10 @@
 
 
 # lt_dict_filter(DICT, [SUBKEY], VALUE, [SEPARATOR], KEY, [...])
-# ------------------------------------------------------------
+# --------------------------------------------------------------
 m4_define([lt_dict_filter],
 [m4_if([$5], [], [],
   [lt_join(m4_quote(m4_default([$4], [[, ]])),
-          m4_quote(lt_if_dict_fetch([$1], [$5], [$2], [$3], [$5])),
-          m4_quote($0([$1], [$2], [$3], [$4], m4_shiftn(5, $@))))])dnl
+           lt_unquote(m4_split(m4_normalize(m4_foreach(_Lt_key, 
lt_car([m4_shiftn(4, $@)]),
+                     [lt_if_dict_fetch([$1], _Lt_key, [$2], [$3], [_Lt_key 
])])))))])[]dnl
 ])