Re: complexity of repeated use of m4_append

[Eric Blake]

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

According to Bruno Haible on 7/12/2008 6:44 PM:
| Hi Eric,
|
|> I've added
|> documentation to the autoconf manual to mention the algorithmic speed
being
|> dependent on the quality of the underlying m4 implementation, and
recommending
|> m4_append over m4_append_uniq when duplicates can be tolerated.
|
| Thanks for doing that.
|
|> But I'm hoping that for M4 1.6, I can make m4_append behave
linearithmically (O
|> (n log n)), by implementing the same optimization as using bash's +=
operator
|> for growing the contents of variables.  The idea is that if the prefix
of the
|> new definition is the same pointer as the prior definition, then m4 should
|> geometrically grow the (over-allocated) storage ...
|
| With that implementation, m4_append behaves linearly: O(n) where n is the
| number of m4_append plus the total length of the arguments. Or, if you
| exclude m4_append calls that append the empty string, O(n) where n is
the total
| length of the arguments = length of the resulting string.
|
|> But since we can append an arbitrary
|> amount of bytes in one insertion, we can end up with fewer than n
insertions
|> between reallocs, so I think that the more pessamistic amortized O(n
log n) is
|> a better characterization of the overall growth.
|
| Eh? Even in that case it's O(n). Proof: Let n be the sum of lengths of the
| arguments. Let 1/q (0 < q < 1) be the growth factor. Then
|   - the number of byte copies from the argument strings to working memory is
|     exactly = n,
|   - the number of zeroed bytes and of copied bytes spent in reallocation is:
|       <= n*q + O(1) for the last reallocation,
|       <= n*q^2 + O(1) for the second-to-last reallocation,
|       ...
|       (at most log n / log q + O(1) reallocations).
|     So in total : <= n * (q + q^2 + ...) + O(log n) = n *q/(1-q) + O(log n)
|     = O(n).

Thanks for your analysis.  While it is true that any O(n) algorithm is
also O(n log n) (Big-O is about bounds, not precision, and any linear
algorithm fits within the bounds of a loglinear algorithm), it is nice to
have a tighter bound.  I'm updating the documentation to state that
m4_append can scale linearly, if the underlying m4 implementation permits
it; then I hope to be able to patch m4 to do just that.

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:

$ cat append.m4
include(`forloop2.m4')dnl
ifdef(`limit', `', `define(`limit', `1000')')dnl
ifdef(`verbose', `', `divert(`-1')')dnl
ifdef(`debug', `', `define(`debug')')dnl
define(`var')define(`append', `define(`var', defn(`var')`$1')')dnl
forloop(`i', `1', limit, `i append(i)')debug

Then I ran it with m4.git branch-1.6 (compiled -g), as well as m4 1.4.11
(compiled -O).

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

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

Eric Blake             address@hidden
-----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

iEYEARECAAYFAkh5eUMACgkQ84KuGfSFAYCCJQCfT8mxNOZQaL3lKOz+fjmrfWkO
8QUAnR4cMJIN7TYvRBbm1PZX3RPp4i/S
=xEWP
-----END PGP SIGNATURE-----