autoconf 2.5x slowness analysis

[Michael Matz]

Hi,

First: I'm not subscribed here, so please leave the cc:.
I have updated my (linux) distro, which uses autoconf 2.52 (I only used
exclusively 2.1x before), and now I were shocked how slow autoconf is.
The packages I'm concerned about are KDE ones (obviously ;) ), esp.
kdebase.  KDE's packages structure is such, that we have one configure
script, but heaps of Makefile.in's (one per subdir).  For kdebase that
makes a list of currently 334 Makefile's in AC_OUTPUT().  Apart from
anything else this is the situation just for autoconf (i.e. after
creating various other files, configure.in and such):

# time autoconf-2.13
real    0m0.861s
# time autoconf-2.52
real    6m31.288s

Yikes!  Someone must be kidding.  After some tracing it becomes obvious,
that AC_CONFIGURE_FILES is the culprit, or better said the AC_FOREACH it
uses.  To test this I've removed the _AC_CONFIG_UNIQUE and
_AC_CONFIG_DEPENDENCIES calls in a copy of AC_CONFIG_FILES and put that
into configure.in, and I'm down to:
# time autoconf-2.5x
real    2m59.557s

Hmm, well, better, but still...
So, after some more tracing and fiddling with m4, I think the definition
of m4_foreach in m4sugar.m4 is highly non-optimal.  Currently it is:

m4_define([m4_car], [$1])
m4_define([_m4_foreach],
[m4_if(m4_quote($2), [], [],
       [m4_define([$1], [m4_car($2)])$3[]_m4_foreach([$1],
                                                     [m4_shift($2)],
                                                     [$3])])])

A trace reveals, that the quoting of the m4_shift call makes all the
m4_shift's add up.  They get only evaluated for the m4_quote() and the
m4_car() calls in the next iteration.  This adds up like so: (quoting is
wrong)

m4_fe (f, (a,b,c), bla)
  quote(a,b,c) -> [a,b,c] != ""
  car(a,c,b) -> a
m4_fe (f, shift(a,b,c), bla)
  quote(shift(a,b,c)) -> quote(b,c) -> b,c != ""
  car(shift(a,b,c)) -> car(b,c) -> b
m4_fe (f, shift(shift(a,b,c)), bla)
  quote(shift(shift(a,b,c))) -> quote(shift(b,c)) -> quote(c) -> c != ""
  car(shift(shift(a,b,c))) -> car(shift(b,c)) -> car(c) -> c

Now guess what happens with 334 listitems.  shift's of the same argument
lists are evaluated again and again (i.e. quadratic behaviour).

Forthermore I believe the definition of m4_car is wrong.  If I test
m4_foreach with the example in the explanation in m4sugar.m4... :

 m4_define(a, 1)dnl
 m4_define(b, 2)dnl
 m4_define(c, 3)dnl
 m4_foreach([f], m4_split([a (b c)]), [echo f
 ])dnl

... the output is:
echo 1
echo (2
echo 3)

If I define m4_car like so:
 m4_define([m4_car], [[$1]])
it becomes
echo a
echo (b
echo c)

So, for now I work with that definition of mm_foreach and AC_FOREACH:

m4_define([mm_foreach],
[m4_pushdef([$1])_mm_foreach($@)m4_popdef([$1])])
m4_define([mm_car], [[$1]])
m4_define([mm_car2], address@hidden)
m4_define([_mm_foreach],
[m4_if(m4_quote($2), [], [],
       [m4_define([$1], [mm_car($2)])$3[]_mm_foreach([$1],
                                               mm_car2(m4_shift($2)),
                                                     [$3])])])
m4_define([AC_FOREACH],
[mm_foreach([$1], m4_split(m4_normalize([$2])), [$3])])


Note how mm_car2 is used for evaluating the m4_shift($2), but how it still
quotes it's own arguments.  The above mm_foreach produces the correct
output for the example above, and also, when inserted into configure.in
the same configure file.  I again use the autoconf version of
AC_CONFIG_FILES (i.e. without removing the .._UNIQUE and
..._DEPENDENCIES), and the only difference now is this:

# time autoconf-2.5x
real    0m18.634s

Much better.

Any comments?


Ciao,
Michael.