Re: reduce forks during autoconf

[Eric Blake]

Bruno Haible <bruno <at> clisp.org> writes:

> Btw, does the use of m4_append_uniq cause quadratic runtime? I.e. when
> there are n invocations of AC_LIBSOURCES, will the time spent in the
> m4_append_uniq calls be O(n²) total? Would it be O(n) total if m4_append was
> used instead?

It turns out that m4_append is currently O(n^2) when using M4 1.4.x, so while 
it has a smaller constant factor overhead than m4_append_uniq, it does not 
perform any better algorithmically.  This is because m4 1.4.x always allocates 
and copies the old definition into new storage for every redefinition.

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 reserved for holding the 
definition, so that in the common case, only the suffix is copied and length 
adjusted, rather than having to malloc new storage and copy the entire prefix.  
If we were always appending only one byte, then yes, this would be an amortized 
linear operation (O(1) cost per insertion in the good case, O(n) cost per 
insertion in the bad, but n insertions possible between bad cases, for O(n)/n 
cost * O(n) insertions = O(n) behavior).  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.  At any rate, 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.

-- 
Eric Blake