[Top][All Lists]

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

Re: complexity of repeated use of m4_append

From: Eric Blake
Subject: Re: complexity of repeated use of m4_append
Date: Tue, 15 Jul 2008 21:22:10 -0600
User-agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv: Gecko/20080421 Thunderbird/ Mnenhy/

Hash: SHA1

According to Ralf Wildenhues on 7/14/2008 1:23 PM:
| 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.
| 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.  ;-)

I've now checked in my working patch to the argv_ref branch (it might be
further refined before merging to branch-1.6 and master).  Some more test
runs, with all of 1.4.11, branch-1.6, and argv_ref compiled with the same
optimization levels:

                                1.4.11  branch-1.6  argv_ref,pre/post
append.m4, -Dlimit=1000          0.077   0.093       0.077   0.061
append.m4, -Dlimit=2000          0.186   0.296       0.140   0.124
append.m4, -Dlimit=10000         3.390   7.265       1.077   0.452
append.m4, -Dlimit=20000        14.905  32.406       3.577   0.890
autoconf -f for coreutils       20.219  20.844      18.279  18.015

I think the biggest reason that branch-1.6 is so much slower than 1.4.11
is that I haven't yet ported the argv_ref patch to use block reads of
back-references into branch-1.6; but at least the argv_ref branch before
this week's patches consistently performed faster than 1.4.11, even if it
was quadratic at appends.  But after today's patches, argv_ref is
definitely linear at appends.  The impact on the best case timing for
real-life usage of autoconf on coreutils didn't have much impact, so as
Ralf surmised, appends don't seem to be the hot spot there.

- --
Don't work too hard, make some time for fun as well!

Eric Blake             address@hidden
Version: GnuPG v1.4.9 (Cygwin)
Comment: Public key at
Comment: Using GnuPG with Mozilla -


reply via email to

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