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