[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: 
Sat, 12 Jul 2008 21:40:51 0600 
Useragent: 
Mozilla/5.0 (Windows; U; Windows NT 5.1; enUS; rv:1.8.1.14) Gecko/20080421 Thunderbird/2.0.0.14 Mnenhy/0.7.5.666 
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 (overallocated) 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 secondtolast reallocation,
 ...
 (at most log n / log q + O(1) reallocations).
 So in total : <= n * (q + q^2 + ...) + O(log n) = n *q/(1q) + O(log n)
 = O(n).
Thanks for your analysis. While it is true that any O(n) algorithm is
also O(n log n) (BigO 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 branch1.6 (compiled g), as well as m4 1.4.11
(compiled O).
 Dlimit= m41.6 m41.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 reallife 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