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
