[0/18] new argv_ref branch for m4 speedup

[Eric Blake]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

For some background - up till now, m4 tail recursion (such as used in
m4sugar's m4_foreach) was inherently quadratic in operation when executed
on GNU m4:
http://lists.gnu.org/archive/html/autoconf-patches/2007-10/msg00145.html

(For the record, I tried to determine how other m4 implementations behave,
but Solaris m4 has a stupid limit of a maximum of 100 arguments to any
macro invocation, and I don't have access to a compiled BSD version).

I've been working on this for over a month, now, and am finally happy
enough with my series of patches to post it as a new branch named
'argv_ref'.  I still need to write the ChangeLogs, perform additional
regression testing (such as the complete autoconf testsuite, and
bootstrapping libtool), as well as port the technical content of the patch
series to the master branch, before releasing m4 1.4.11 (I might rewind
the argv_ref branch at times to fold in some of those improvements, but I
will not rewind the branch-1_4 branch).  Anyone that would like to help
out by building
http://git.sv.gnu.org/gitweb/?p=m4.git;a=shortlog;h=argv_ref and ensuring
that it has no difference from m4 1.4.10 (other than the speedups) is more
than welcome to give it a try.  I've added a lot of new assertions into
the code, and can't quite guarantee that awkward choices of quoting or
comment characters will lead to unintended semantics changes or assertion
failures.

For some numbers, based on testing on cygwin:

Best times, ~peak memory usage for:
[1] 'time M4=m4 autoconf -f' on coreutils (ensures that the output is
identical, and that large-scale real-life examples aren't adversely affected)
[2] 'time m4 -Dlimit=1500 loop.m4' in m4/examples (tests boxed recursion,
where each iteration takes three arguments and trims off an element of a
quoted list)
[3] 'time m4 -Dlimit=1500 -Dalt loop.m4' in m4/examples (tests unboxed
recursion, where each iteration uses one fewer argument)

          [1]              [2]             [3]
compiled at -O2
m4-1.4.10:29.812,  4.4      9.225, 40.7     8.683, 18.8

compiled at -g
master:   34.054,  4.3     10.698,  1.8     9.767,  1.8
stage 1:  34.959,  4.3     11.084,  1.8     9.879,  1.8
stage 2:  34.572,  4.3     10.657,  1.8     9.906,  1.8
stage 3:  32.821,  4.3     10.587,  1.8     9.991,  1.8
stage 4:  30.942,  4.3     10.738,  1.8    10.060,  1.8
stage 5:  32.389,  4.3     10.877,  1.8    10.095,  1.8
stage 6:  33.388,  4.3     10.737,  1.8     9.784,  1.8
stage 7:  32.729,  4.4     10.576,  2.0     9.924,  5.3
stage 8:  32.377,  4.5     10.608,  2.1     9.954,  2.2
stage 9:  34.862,  7.6     10.626, 33.3     9.481,  2.1
stage10:  33.730,  7.6     10.061, 35.3     8.888,  2.1
stage11:  31.903,  6.1      8.717,  2.1     8.959,  2.1
stage12:  32.480,  6.1      8.746,  2.2     8.977,  2.1
stage13:  32.875,  4.6      8.981, 10.5     8.999,  2.1
stage14:  34.190,  5.3      9.919, 10.6    10.260, 55.0
stage15:  32.670,  5.5      8.035, 10.7     6.953, 10.9
stage16:  31.769,  5.5      8.123, 10.6     7.002, 10.9
stage17:  29.833,  5.1      5.567,  2.1     6.582,  2.4
stage18:  30.201,  5.1      5.558,  1.8     5.571,  2.1

Other tests include checking for scaling behavior:

[1] m4 -Dlimit=n loop.m4
[2] m4 -Dlimit=n -Dalt loop.m4

n =     1500          3000          6000
[1]     0.192, 1.8    0.297, 1.9    0.548, 2.0
[2]     0.177, 2.1    0.320, 2.6    0.522, 3.4

Impressive! m4 1.4.10 was quadratic in both memory and time before the
patch series, and reduces to linear (plus fixed overhead) in both memory
and time afterwards.  And the performance of autoconf using an unoptimized
image at stage18 practically overtook the speed of the -O2 baseline of
1.4.10, all due to the algorithmic improvements.

I'll follow up with each of the 18 patches to just the m4-patches list.

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

Eric Blake             address@hidden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHQl6q84KuGfSFAYARAsGRAKCTTU0pw6xSfaybUMyhiFBFne//WgCfeu4p
OK0o+qMTMWlinsEBdCd37OU=
=LJhc
-----END PGP SIGNATURE-----