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=10c8443af9ee9497b9bb896cfd0475208aefe9fc The branch, master has been updated via 10c8443af9ee9497b9bb896cfd0475208aefe9fc (commit) from 9ede0e4cda99d061ba9cceb07a8b11efb69a7049 (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 10c8443af9ee9497b9bb896cfd0475208aefe9fc Author: Eric Blake <[EMAIL PROTECTED]> Date: Mon Jul 28 16:38:17 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 | 82 ++++++++++++++++++++++++++++++------------------ examples/foreachq3.m4 | 11 +++--- examples/forloop2.m4 | 8 ++-- 4 files changed, 70 insertions(+), 41 deletions(-) diff --git a/ChangeLog b/ChangeLog index 3d89fb8..2eb684e 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 67421eb..862dac3 100644 --- a/doc/m4.texinfo +++ b/doc/m4.texinfo @@ -8922,8 +8922,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 @@ -8934,12 +8935,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{} @@ -8950,7 +8951,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 input: (b) >= (a) [EMAIL PROTECTED]:stdin:6: Warning: eval: bad input: (a) <= (b) @result{} @end example @@ -8975,8 +8976,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{} @@ -9097,8 +9098,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. 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 @@ -9109,12 +9112,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{} @@ -9122,23 +9124,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 @@ -9150,10 +9157,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 @@ -9167,7 +9178,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 @@ -9175,11 +9186,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 @@ -9250,6 +9264,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}. + @cindex filtering defined symbols @cindex subset of defined symbols @cindex defined symbols, filtering @@ -9290,7 +9309,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
