-----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 [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 iEYEARECAAYFAkh5eUMACgkQ84KuGfSFAYCCJQCfT8mxNOZQaL3lKOz+fjmrfWkO 8QUAnR4cMJIN7TYvRBbm1PZX3RPp4i/S =xEWP -----END PGP SIGNATURE-----
