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
])
