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. > > And making append operations linear will probably make a noticeable > speedup in real-life cases, too.
That may well be, and hopefully will be, but ... > 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 ... these numbers, together with the ones from the test above, do not especially support your claim. 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. ;-) Cheers, Ralf
