[SCM] GNU M4 source repository branch, branch-1.6, updated. v1.5.89a-43-g12a6247
"Eric Blake" <[email protected]> Mon, 28 Jul 2008 22:28:03 +0000
| Newsgroups | gmane.comp.gnu.m4.cvs |
|---|---|
| Message-ID | <[email protected]> |
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 @file{m4-@value{VERSION}/@/examples/@/forloop2.m4}; this
-version also optimizes based on the fact that the starting bound does
-not need to be passed to the helper @code{@w{_forloop}}.
+version also optimizes overhead by calling four macros instead of six
+per iteration (excluding those in @var{text}), by not dereferencing the
+@var{iterator} in the helper @code{@w{_forloop}}.
@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
-@result{}define(`forloop', `ifelse(eval(`($3) >= ($2)'), `1',
-@result{} `pushdef(`$1', eval(`$2'))_$0(`$1',
+@result{}define(`forloop', `ifelse(eval(`($2) <= ($3)'), `1',
+@result{} `pushdef(`$1')_$0(`$1', eval(`$2'),
@result{} eval(`$3'), `$4')popdef(`$1')')')
@result{}define(`_forloop',
-@result{} `$3`'ifelse(indir(`$1'), `$2', `',
-@result{} `define(`$1', incr(indir(`$1')))$0($@@)')')
+@result{} `define(`$1', `$2')$4`'ifelse(`$2', `$3', `',
+@result{} `$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')
-@error{}m4:stdin:6: Warning: eval: bad expression (bad input): (b) >= (a)
+@error{}m4: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')
-@result{}ifelse(eval(``($3) >= ($2)''), ``1'',
-@result{} ``pushdef(``$1'', eval(``$2''))_$0(``$1'',
+@result{}ifelse(eval(``($2) <= ($3)''), ``1'',
+@result{} ``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 @file{m4-@value{VERSION}/@/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
+@file{m4-@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
-@result{}define(`foreachq',
-@result{}`pushdef(`$1')_$0(`$1', `$3'ifelse(`$2', `', `',
-@result{} `, $2'))popdef(`$1')')
-@result{}define(`_foreachq', `ifelse(`$#', `2', `',
-@result{} `define(`$1', `$3')$2`'$0(`$1', `$2'ifelse(`$#', `3', `',
-@result{} `, shift(shift(shift($@@)))'))')')
+@result{}define(`foreachq', `ifelse(`$2', `', `',
+@result{} `pushdef(`$1')_$0(`$1', `$3', `', $2)popdef(`$1')')')
+@result{}define(`_foreachq', `ifelse(`$#', `3', `',
+@result{} `define(`$1', `$4')$2`'$0(`$1', `$2',
+@result{} 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
+@error{}', `', `1', `2', `3', `4')
+@error{}m4trace: -3- shift(`x
+@error{}', `', `1', `2', `3', `4')
+@error{}m4trace: -2- shift(`', `1', `2', `3', `4')
+@result{}2
+@error{}m4trace: -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')
-@result{}2
+@result{}3
@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')
-@result{}3
+@result{}4
@error{}m4trace: -4- shift(`x', `x
@error{}', `3', `4')
@error{}m4trace: -3- shift(`x
@error{}', `3', `4')
@error{}m4trace: -2- shift(`3', `4')
-@result{}4
@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
+@code{shift}. 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
-@code{m4_define(`$1', `$n')$2`'}, with @samp{n} set to successive
+@code{m4_define(`$1', `$@var{n}')$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 @samp{$@{10@}} 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
+@samp{$10} as the tenth argument; the anticipation is that
+@samp{$@{10@}} 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
+@code{_foreachq} 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 @code{@w{_foreach}}, similary for
-@code{foreachq} as provided by @file{foreachq3.m4}. But
+@code{foreachq} as provided by @file{foreachq3.m4} or
+@file{foreachq4.m4}. But
@code{foreachq}, as provided by @file{foreachq2.m4},
evaluates unquoted list elements twice while visiting the first list
element, once in @code{@w{_arg1q}} and once in @code{@w{_rest}}. 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