bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: complexity of repeated use of m4_append


From: Ralf Wildenhues
Subject: Re: complexity of repeated use of m4_append
Date: Mon, 14 Jul 2008 21:23:38 +0200
User-agent: Mutt/1.5.18 (2008-05-17)

Hi Eric,

* Eric Blake wrote on Sun, Jul 13, 2008 at 05:40:51AM CEST:
> In the meantime, I coded up a test; I will probably commit it as
> m4/examples/append.m4 and add it to the m4 testsuite if I can get m4 sped
> up.  The test shows that the current behavior is indeed quadratic:
[...]
> - -Dlimit=   m4-1.6   m4-1.4.11
> ~ 250       0.030    0.030
> ~ 500       0.061    0.062
> 1000       0.093    0.077
> 2000       0.280    0.171
> 4000       1.030    0.577
>
> Once the size of the appending starts to dominate execution time, then it
> becomes obvious that doubling the limit quadruples the time with current m4.
>
> And making append operations linear will probably make a noticeable
> speedup in real-life cases, too.

That may well be, and hopefully will be, but ...

> When configuring coreutils, I see the
> following evidence that we do some large appends:
>
> $ autoconf --trace m4_append:'$1' | sort | uniq -c | sort -n -k1,1
> ...
> ~     12 _AC_USER_OPTS
> ~    229 gl_LIBSOURCES_LIST
> ~    470 _AC_SUBST_VARS

... these numbers, together with the ones from the test above, do not
especially support your claim.  The quadratic behavior does not set in
until well after 1000 elements, and you may safely assume that a linear
algorithm will have a larger linearity factor.

Anyway, this is just mumbling, as going for the linear algorithm is
still the right way to go.  ;-)

Cheers,
Ralf




reply via email to

[Prev in Thread] Current Thread [Next in Thread]