Eric Blake <ebb9 <at> byu.net> writes: > Fortunately, autoconf had already resolved the issue, as a side effect of > writing a more efficient copy algorithm. So I'm applying this followup to > branch-1.6 and master, then backporting the series of doc patches to branch- 1.4:
> +++ b/examples/stack_sep.m4 > @@ -0,0 +1,17 @@ > +divert(`-1') > +# stack_foreach_sep(macro, pre, post, sep) > +# Invoke PRE`'defn`'POST with a single argument of each definition > +# from the definition stack of MACRO, starting with the oldest, and > +# separated by SEP between definitions. > +define(`stack_foreach_sep', > +`_stack_reverse_sep(`$1', `tmp-$1')'dnl > +`_stack_reverse_sep(`tmp-$1', `$1', `$2`'defn(`$1')$3', `$4')') > +# stack_foreach_sep_lifo(macro, pre, post, sep) > +# Like stack_foreach_sep, but starting with the newest definition. > +define(`stack_foreach_sep_lifo', > +`_stack_reverse_sep(`$1', `tmp-$1', `$2`'defn(`$1')$3', `$4')'dnl > +`_stack_reverse_sep(`tmp-$1', `$1')') > +define(`_stack_reverse_sep', > +`ifdef(`$1', `pushdef(`$2', defn(`$1'))$3`'popdef(`$1')$0( > + `$1', `$2', `$4`'$3')')') > +divert`'dnl Oops. That implementation is quadratic, as I just discovered on the autoconf list today. I'm installing this on all three branches, to provide a linear alternative. From: Eric Blake <[email protected]> Date: Thu, 12 Feb 2009 14:59:08 -0700 Subject: [PATCH] Avoid quadratic code when walking definition stack. * examples/stack_sep.m4: Use linear, not quadratic implementation. * doc/m4.texinfo (Improved copy): Fix documentation and add test, based on recent autoconf bug fix. Signed-off-by: Eric Blake <[email protected]> --- ChangeLog | 8 ++++++++ doc/m4.texinfo | 45 +++++++++++++++++++++++++++++++++++---------- examples/stack_sep.m4 | 6 +++--- 3 files changed, 46 insertions(+), 13 deletions(-) diff --git a/ChangeLog b/ChangeLog index c55e79f..3495018 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,11 @@ +2009-02-12 Eric Blake <[email protected]> + + Avoid quadratic code when walking definition stack. + * examples/stack_sep.m4: Use linear, not quadratic + implementation. + * doc/m4.texinfo (Improved copy): Fix documentation and add test, + based on recent autoconf bug fix. + 2009-01-24 Eric Blake <[email protected]> Add URLs to --help output. diff --git a/doc/m4.texinfo b/doc/m4.texinfo index c09d771..9bbfcfd 100644 --- a/doc/m4.texinfo +++ b/doc/m4.texinfo @@ -8199,13 +8199,21 @@ Improved copy construct macro calls with more than one argument, without passing builtin tokens through a macro call. It is likewise possible to directly reference the stack definitions without a macro call, by -leaving @var{pre} and @var{post} empty. The new macro also adds a -separator that is only output after the first iteration of the helper -...@code{_stack_reverse_sep}, implemented by prepending the original -...@var{sep} to @var{pre} and omitting a @var{sep} argument in subsequent -iterations. As an added bonus, using @code{stack_foreach_sep} to -implement @code{copy} performs fewer macro invocations. The improved -stack walking macros are available in +leaving @var{pre} and @var{post} empty. Thus, in addition to fixing +...@code{copy} on builtin tokens, it also executes with fewer macro +invocations. + +The new macro also adds a separator that is only output after the first +iteration of the helper @code{_stack_reverse_sep}, implemented by +prepending the original @var{sep} to @var{pre} and omitting a @var{sep} +argument in subsequent iterations. Note that the empty string that +separates @var{sep} from @var{pre} is provided as part of the fourth +argument when originally calling @code{_stack_reverse_sep}, and not by +writing @code{$4`'$3} as the third argument in the recursive call; while +the other approach would give the same output, it does so at the expense +of increasing the argument size on each iteration of +...@code{_stack_reverse_sep}, which results in quadratic instead of linear +execution time. The improved stack walking macros are available in @file{...@value{version}/@/examples/@/stack_sep.m4}: @comment examples @@ -8238,18 +8246,35 @@ Improved copy @result{}# separated by SEP between definitions. @result{}define(`stack_foreach_sep', @result{}`_stack_reverse_sep(`$1', `tmp-$1')'dnl -...@result{}`_stack_reverse_sep(`tmp-$1', `$1', `$2`'defn(`$1')$3', `$4')') +...@result{}`_stack_reverse_sep(`tmp-$1', `$1', `$2`'defn(`$1')$3', `$4`'')') @result{}# stack_foreach_sep_lifo(macro, pre, post, sep) @result{}# Like stack_foreach_sep, but starting with the newest definition. @result{}define(`stack_foreach_sep_lifo', -...@result{}`_stack_reverse_sep(`$1', `tmp-$1', `$2`'defn(`$1')$3', `$4')'dnl +...@result{}`_stack_reverse_sep(`$1', `tmp-$1', `$2`'defn(`$1')$3', `$4`'')'dnl @result{}`_stack_reverse_sep(`tmp-$1', `$1')') @result{}define(`_stack_reverse_sep', @result{}`ifdef(`$1', `pushdef(`$2', defn(`$1'))$3`'popdef(`$1')$0( -...@result{} `$1', `$2', `$4`'$3')')') +...@result{} `$1', `$2', `$4$3')')') @result{}divert`'dnl @end example +...@ignore +...@comment Not worth putting in the manual, but make sure that +...@comment stack_foreach_sep has linear performance. + +...@comment examples +...@example +$ @kbd {m4 -I examples} +include(`forloop3.m4')include(`stack_sep.m4')dnl +forloop(`i', `1', `10000', `pushdef(`s', i)') +...@result{} +define(`colon', `:')define(`dash', `-') +...@result{} +len(stack_foreach_sep(`s', `dash', `', `colon')) +...@result{}58893 +...@end example +...@end ignore + @node Improved m4wrap @section Solution for @code{m4wrap} diff --git a/examples/stack_sep.m4 b/examples/stack_sep.m4 index b11bc83..767d15e 100644 --- a/examples/stack_sep.m4 +++ b/examples/stack_sep.m4 @@ -5,13 +5,13 @@ divert(`-1') # separated by SEP between definitions. define(`stack_foreach_sep', `_stack_reverse_sep(`$1', `tmp-$1')'dnl -`_stack_reverse_sep(`tmp-$1', `$1', `$2`'defn(`$1')$3', `$4')') +`_stack_reverse_sep(`tmp-$1', `$1', `$2`'defn(`$1')$3', `$4`'')') # stack_foreach_sep_lifo(macro, pre, post, sep) # Like stack_foreach_sep, but starting with the newest definition. define(`stack_foreach_sep_lifo', -`_stack_reverse_sep(`$1', `tmp-$1', `$2`'defn(`$1')$3', `$4')'dnl +`_stack_reverse_sep(`$1', `tmp-$1', `$2`'defn(`$1')$3', `$4`'')'dnl `_stack_reverse_sep(`tmp-$1', `$1')') define(`_stack_reverse_sep', `ifdef(`$1', `pushdef(`$2', defn(`$1'))$3`'popdef(`$1')$0( - `$1', `$2', `$4`'$3')')') + `$1', `$2', `$4$3')')') divert`'dnl -- 1.6.1.2 _______________________________________________ M4-patches mailing list [email protected] http://lists.gnu.org/mailman/listinfo/m4-patches
