This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "GNU M4 source repository".
http://git.sv.gnu.org/gitweb/?p=m4.git;a=commitdiff;h=12a62477d77990112a98d3c785818f17d7b5a392 The branch, branch-1.6 has been updated via 12a62477d77990112a98d3c785818f17d7b5a392 (commit) from eeaceb311464f6d88d2782ed8773c01d49f83aba (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit 12a62477d77990112a98d3c785818f17d7b5a392 Author: Eric Blake <[EMAIL PROTECTED]> Date: Mon Jul 28 16:17:04 2008 -0600 Optimize iteration examples. * examples/forloop2.m4: Avoid excess indir, by passing current counter value as parameter. * examples/foreachq3.m4: Avoid unneeded ifelse, by injecting an ignored argument. * doc/m4.texinfo (Improved forloop, Improved foreach): Update the documentation to match. Signed-off-by: Eric Blake <[EMAIL PROTECTED]> ----------------------------------------------------------------------- Summary of changes: ChangeLog | 10 ++++++ doc/m4.texinfo | 83 ++++++++++++++++++++++++++++++------------------- examples/foreachq3.m4 | 11 +++--- examples/forloop2.m4 | 8 ++-- 4 files changed, 70 insertions(+), 42 deletions(-) diff --git a/ChangeLog b/ChangeLog index 9572436..47449f2 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,13 @@ +2008-07-28 Eric Blake <[EMAIL PROTECTED]> + + Optimize iteration examples. + * examples/forloop2.m4: Avoid excess indir, by passing current + counter value as parameter. + * examples/foreachq3.m4: Avoid unneeded ifelse, by injecting an + ignored argument. + * doc/m4.texinfo (Improved forloop, Improved foreach): Update the + documentation to match. + 2008-07-26 Eric Blake <[EMAIL PROTECTED]> Give example for O(n) foreach on m4 1.4.x. diff --git a/doc/m4.texinfo b/doc/m4.texinfo index 0185ba5..f8b3998 100644 --- a/doc/m4.texinfo +++ b/doc/m4.texinfo @@ -7645,8 +7645,9 @@ into an infinite loop if given an iterator that is not parsed as a macro name. It does not do any sanity checking on its numeric bounds, and only permits decimal numbers for bounds. Here is an improved version, shipped as @[EMAIL PROTECTED]/@/examples/@/forloop2.m4}; this -version also optimizes based on the fact that the starting bound does -not need to be passed to the helper @[EMAIL PROTECTED] +version also optimizes overhead by calling four macros instead of six +per iteration (excluding those in @var{text}), by not dereferencing the [EMAIL PROTECTED] in the helper @[EMAIL PROTECTED] @comment examples @example @@ -7657,12 +7658,12 @@ undivert(`forloop2.m4')dnl @result{}# works even if VAR is not a strict macro name @result{}# performs sanity check that FROM is larger than TO @result{}# allows complex numerical expressions in TO and FROM [EMAIL PROTECTED](`forloop', `ifelse(eval(`($3) >= ($2)'), `1', [EMAIL PROTECTED] `pushdef(`$1', eval(`$2'))_$0(`$1', [EMAIL PROTECTED](`forloop', `ifelse(eval(`($2) <= ($3)'), `1', [EMAIL PROTECTED] `pushdef(`$1')_$0(`$1', eval(`$2'), @result{} eval(`$3'), `$4')popdef(`$1')')') @result{}define(`_forloop', [EMAIL PROTECTED] `$3`'ifelse(indir(`$1'), `$2', `', [EMAIL PROTECTED] `define(`$1', incr(indir(`$1')))$0($@@)')') [EMAIL PROTECTED] `define(`$1', `$2')$4`'ifelse(`$2', `$3', `', [EMAIL PROTECTED] `$0(`$1', incr(`$2'), `$3', `$4')')') @result{}divert`'dnl include(`forloop2.m4') @result{} @@ -7673,7 +7674,7 @@ forloop(`', `1', `2', ` odd iterator name') forloop(`i', `5 + 5', `0xc', ` 0x`'eval(i, `16')') @result{} 0xa 0xb 0xc forloop(`i', `a', `b', `non-numeric bounds') [EMAIL PROTECTED]:stdin:6: Warning: eval: bad expression (bad input): (b) >= (a) [EMAIL PROTECTED]:stdin:6: Warning: eval: bad expression (bad input): (a) <= (b) @result{} @end example @@ -7698,8 +7699,8 @@ define(`double', `define(`$1'`2', arg1(patsubst(dquote(defn(`$1')), `[`']', `\&\&')))') @result{} double(`forloop')double(`_forloop')defn(`forloop2') [EMAIL PROTECTED](eval(``($3) >= ($2)''), ``1'', [EMAIL PROTECTED] ``pushdef(``$1'', eval(``$2''))_$0(``$1'', [EMAIL PROTECTED](eval(``($2) <= ($3)''), ``1'', [EMAIL PROTECTED] ``pushdef(``$1'')_$0(``$1'', eval(``$2''), @result{} eval(``$3''), ``$4'')popdef(``$1'')'') forloop(i, 1, 5, `ifelse(')forloop(i, 1, 5, `)') @result{} @@ -7820,9 +7821,10 @@ list, which costs a couple of macro invocations. It is possible to rewrite the algorithm by swapping the order of the arguments to @code{_foreachq} in order to operate on an unboxed list in the first place, and by using the fixed-length @samp{$#} instead of an arbitrary -length list as the key to end recursion. The result is eight macro -invocations per loop, instead of nine. This alternative approach is -available as @[EMAIL PROTECTED]/@/examples/@/foreach3.m4}: +length list as the key to end recursion. The result is an overhead of +six macro invocations per loop (excluding any macros in @var{text}), +instead of eight. This alternative approach is available as [EMAIL PROTECTED]@value{VERSION}/@/examples/@/foreach3.m4}: @comment examples @example @@ -7833,12 +7835,11 @@ undivert(`foreachq3.m4')dnl @result{}divert(`-1') @result{}# foreachq(x, `item_1, item_2, ..., item_n', stmt) @result{}# quoted list, alternate improved version [EMAIL PROTECTED](`foreachq', [EMAIL PROTECTED](`$1')_$0(`$1', `$3'ifelse(`$2', `', `', [EMAIL PROTECTED] `, $2'))popdef(`$1')') [EMAIL PROTECTED](`_foreachq', `ifelse(`$#', `2', `', [EMAIL PROTECTED] `define(`$1', `$3')$2`'$0(`$1', `$2'ifelse(`$#', `3', `', [EMAIL PROTECTED] `, shift(shift(shift($@@)))'))')') [EMAIL PROTECTED](`foreachq', `ifelse(`$2', `', `', [EMAIL PROTECTED] `pushdef(`$1')_$0(`$1', `$3', `', $2)popdef(`$1')')') [EMAIL PROTECTED](`_foreachq', `ifelse(`$#', `3', `', [EMAIL PROTECTED] `define(`$1', `$4')$2`'$0(`$1', `$2', [EMAIL PROTECTED] shift(shift(shift($@@))))')') @result{}divert`'dnl traceon(`shift')debugmode(`aq') @result{} @@ -7846,23 +7847,28 @@ foreachq(`x', ``1', `2', `3', `4'', `x ')dnl @result{}1 @error{}m4trace: -4- shift(`x', `x [EMAIL PROTECTED]', `', `1', `2', `3', `4') [EMAIL PROTECTED]: -3- shift(`x [EMAIL PROTECTED]', `', `1', `2', `3', `4') [EMAIL PROTECTED]: -2- shift(`', `1', `2', `3', `4') [EMAIL PROTECTED] [EMAIL PROTECTED]: -4- shift(`x', `x @error{}', `1', `2', `3', `4') @error{}m4trace: -3- shift(`x @error{}', `1', `2', `3', `4') @error{}m4trace: -2- shift(`1', `2', `3', `4') [EMAIL PROTECTED] [EMAIL PROTECTED] @error{}m4trace: -4- shift(`x', `x @error{}', `2', `3', `4') @error{}m4trace: -3- shift(`x @error{}', `2', `3', `4') @error{}m4trace: -2- shift(`2', `3', `4') [EMAIL PROTECTED] [EMAIL PROTECTED] @error{}m4trace: -4- shift(`x', `x @error{}', `3', `4') @error{}m4trace: -3- shift(`x @error{}', `3', `4') @error{}m4trace: -2- shift(`3', `4') [EMAIL PROTECTED] @end example Prior to M4 1.6, every instance of @samp{$@@} was rescanned as it was @@ -7874,10 +7880,14 @@ the number of bytes scanned (for example, making the broken version in @file{foreachq.m4} cubic, rather than quadratic, in behavior). Once the underlying M4 implementation was improved in 1.6 to reuse results of previous scans, both styles of @code{foreachq} become linear in the -number of bytes scanned, and the difference in timing is no longer -noticeable; in fact, after the change, the @file{foreachq2.m4} version -uses slightly less memory since it tracks fewer arguments per macro -invocation. +number of bytes scanned, but the @file{foreachq3.m4} version remains +noticeably faster because of fewer macro invocations. Notice how the +implementation injects an empty argument prior to expanding @samp{$2} +within @code{foreachq}; the helper macro @code{_foreachq} then ignores +the third argument altogether, and ends recursion when there are three +arguments left because there was nothing left to pass through [EMAIL PROTECTED] Thus, each iteration only needs one @code{ifelse}, rather +than the two conditionals used in the version from @file{foreachq2.m4}. @cindex nine arguments, more than @cindex more than nine arguments @@ -7891,7 +7901,7 @@ result even with older M4 implementations. This implementation relies on the @acronym{GNU} extension that @samp{$10} expands to the tenth argument rather than the first argument concatenated with @samp{0}. The trick is to define an intermediate macro that repeats the text [EMAIL PROTECTED](`$1', `$n')$2`'}, with @samp{n} set to successive [EMAIL PROTECTED](`$1', [EMAIL PROTECTED]')$2`'}, with @samp{n} set to successive integers corresponding to each argument. The helper macro @code{_foreachq_} is needed in order to generate the literal sequences such as @samp{$1} into the intermediate macro, rather than expanding @@ -7899,11 +7909,14 @@ them as the arguments of @code{_foreachq}. With this approach, no @code{shift} calls are even needed! However, when linear recursion is available in new enough M4, the time and memory cost of using @code{forloop} to build an intermediate macro outweigh the costs of any -of the previous implementations. Additionally, this approach will need -adjustment when a future version of M4 follows @acronym{POSIX} by no -longer treating @samp{$10} as the tenth argument; the anticipation is -that @[EMAIL PROTECTED]@}} can be used instead, although that alternative -syntax is not yet supported. +of the previous implementations (there are seven macros of overhead per +iteration instead of six in @file{foreachq3.m4}, and the entire +intermediate macro must be built in memory before any iteration is +expanded). Additionally, this approach will need adjustment when a +future version of M4 follows @acronym{POSIX} by no longer treating [EMAIL PROTECTED] as the tenth argument; the anticipation is that [EMAIL PROTECTED]@[EMAIL PROTECTED] can be used instead, although that alternative syntax is +not yet supported. @comment examples @example @@ -7974,6 +7987,11 @@ foreach(`x', `(`1', `2', `3', `4')', `x @error{}m4trace: -3- shift(``4'') @end example +It is likewise possible to write a variant of @code{foreach} that +performs in linear time on M4 1.4.x; the easiest method is probably +writing a version of @code{foreach} that unboxes its list, then invokes [EMAIL PROTECTED] as previously defined in @file{foreachq4.m4}. + In summary, recursion over list elements is trickier than it appeared at first glance, but provides a powerful idiom within @code{m4} processing. As a final demonstration, both list styles are now able to handle @@ -7981,7 +7999,8 @@ several scenarios that would wreak havoc on one or both of the original implementations. This points out one other difference between the list styles. @code{foreach} evaluates unquoted list elements only once, in preparation for calling @[EMAIL PROTECTED], similary for [EMAIL PROTECTED] as provided by @file{foreachq3.m4}. But [EMAIL PROTECTED] as provided by @file{foreachq3.m4} or [EMAIL PROTECTED] But @code{foreachq}, as provided by @file{foreachq2.m4}, evaluates unquoted list elements twice while visiting the first list element, once in @[EMAIL PROTECTED] and once in @[EMAIL PROTECTED] When diff --git a/examples/foreachq3.m4 b/examples/foreachq3.m4 index beab455..5e65672 100644 --- a/examples/foreachq3.m4 +++ b/examples/foreachq3.m4 @@ -1,10 +1,9 @@ divert(`-1') # foreachq(x, `item_1, item_2, ..., item_n', stmt) # quoted list, alternate improved version -define(`foreachq', -`pushdef(`$1')_$0(`$1', `$3'ifelse(`$2', `', `', - `, $2'))popdef(`$1')') -define(`_foreachq', `ifelse(`$#', `2', `', - `define(`$1', `$3')$2`'$0(`$1', `$2'ifelse(`$#', `3', `', - `, shift(shift(shift($@)))'))')') +define(`foreachq', `ifelse(`$2', `', `', + `pushdef(`$1')_$0(`$1', `$3', `', $2)popdef(`$1')')') +define(`_foreachq', `ifelse(`$#', `3', `', + `define(`$1', `$4')$2`'$0(`$1', `$2', + shift(shift(shift($@))))')') divert`'dnl diff --git a/examples/forloop2.m4 b/examples/forloop2.m4 index 41e0e16..b7154e8 100644 --- a/examples/forloop2.m4 +++ b/examples/forloop2.m4 @@ -3,10 +3,10 @@ divert(`-1') # works even if VAR is not a strict macro name # performs sanity check that FROM is larger than TO # allows complex numerical expressions in TO and FROM -define(`forloop', `ifelse(eval(`($3) >= ($2)'), `1', - `pushdef(`$1', eval(`$2'))_$0(`$1', +define(`forloop', `ifelse(eval(`($2) <= ($3)'), `1', + `pushdef(`$1')_$0(`$1', eval(`$2'), eval(`$3'), `$4')popdef(`$1')')') define(`_forloop', - `$3`'ifelse(indir(`$1'), `$2', `', - `define(`$1', incr(indir(`$1')))$0($@)')') + `define(`$1', `$2')$4`'ifelse(`$2', `$3', `', + `$0(`$1', incr(`$2'), `$3', `$4')')') divert`'dnl hooks/post-receive -- GNU M4 source repository
