Eric Blake <ebb9 <at> byu.net> writes:
> Based on my recent autoconf m4sugar patches, I figured I'd better document
> that it is possible to implement foreach in O(n) rather than O(n^2) even
> in m4 1.4.x.
And while working on that, I discovered some optimizations to make both forloop
and foreachq faster.
>From 12a62477d77990112a98d3c785818f17d7b5a392 Mon Sep 17 00:00:00 2001
From: Eric Blake <[EMAIL PROTECTED]>
Date: Mon, 28 Jul 2008 16:17:04 -0600
Subject: [PATCH] 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]>
---
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
--
1.5.6.4
_______________________________________________
M4-patches mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/m4-patches
