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
