Re: complexity of repeated use of m4_append

-----BEGIN PGP SIGNED MESSAGE-----
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             [email protected]
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkh9aWIACgkQ84KuGfSFAYBbWgCeJ9QlhgQBcRfHugGECY83lxC3
ZMcAn2RUb8heuSJV3W1HEx+GRWsycryx
=/Cez
-----END PGP SIGNATURE-----