Re: autoconf 2.5x slowness analysis

[Akim Demaille]

| 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.  

Yes, it is precisely to protect the items and to preserve quotation.
I didn't find any means to preserve the quotation and to be eager.

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

Right :(  I didn't think that m4_foreach could be _the_ responsible :(

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

Because split has changed too.

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

I am now more convinced than I was before that m4_foreach and friends
are wrong, we really ought to work with recursion instead of pseudo
for loops.

| 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?

Yep, this is really impressive, congrats!

I have one question though: did you run the test suite?  How does your
proposal behave?