[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: autoconf 2.5x slowness analysis
From: |
Akim Demaille |
Subject: |
Re: autoconf 2.5x slowness analysis |
Date: |
12 Nov 2001 16:14:45 +0100 |
User-agent: |
Gnus/5.0808 (Gnus v5.8.8) XEmacs/21.4 (Artificial Intelligence) |
| 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?