[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: reduce forks during autoconf
From: |
Eric Blake |
Subject: |
Re: reduce forks during autoconf |
Date: |
Fri, 11 Jul 2008 18:24:31 +0000 (UTC) |
User-agent: |
Loom/3.14 (http://gmane.org/) |
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
- Re: reduce forks during autoconf,
Eric Blake <=