[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: m4_joinall
From: |
Eric Blake |
Subject: |
Re: m4_joinall |
Date: |
Wed, 23 Jul 2008 16:55:46 +0000 (UTC) |
User-agent: |
Loom/3.14 (http://gmane.org/) |
Eric Blake <ebb9 <at> byu.net> writes:
> > I've got a pending patch series to add m4_set_* where I wanted to use
> > m4_join, but not have the empty argument omitted. I'm borrowing this from
> > the m4 manual, and committing.
>
> It turns out that m4_joinall is quadratic on m4 1.4.x (just as any other
> recursive algorithm on $@), so I didn't end up using it in my m4_set
> implementation after all. But it is still a useful interface, and with the
$@
> algorithm fix m4 1.6, m4_joinall becomes linear, so I won't revert it.
With some more experimenting, I found that it is possible to rewrite m4_foreach
in a linear manner even for m4 1.4.x by avoiding recursion on $@ (the trick
involves using m4_for to explicitly spell out $# copies of the iteration). The
rewrite increases the constant factor of m4_foreach: on m4 1.6, avoiding
recursion consistently costs more than twice the memory and slightly more time
than the current implementation. But for m4 1.4.x, it does not take a very
large n for the benefit of linear to provide noticeable improvement over the
quadratic nature of the current implementation. The alternate implementation
also depends on $10 expanding to the tenth argument rather than the first
argument concatenated with a literal 0; but since this violates POSIX, newer m4
versions might start warning on this construct, so this serves as another
reason for not rewriting m4_foreach for m4 1.6.
Therefore, I will probably be committing some patches that rewrite m4_foreach
to choose between two different implementations based on the presence of
__m4_version__ (I'm still debating on making the decision at the time m4sugar
is frozen, or making it dynamically when m4_init is called to allow upgrading
m4 without having to re-freeze m4sugar). It is then possible to rewrite
m4_joinall in terms of linear m4_foreach rather than quadratic recursion on $@,
so that m4_joinall can also be linear even on m4 1.4.x. Again, if m4_joinall
is already linear, then rewriting it in terms of m4_foreach makes it slower, so
it would also have to be conditional on which underlying m4 is detected.
--
Eric Blake