Re: m4_joinall

[Eric Blake]

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