[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[SCM] GNU M4 source repository branch, master, updated. cvs-readonly-146
From: |
Eric Blake |
Subject: |
[SCM] GNU M4 source repository branch, master, updated. cvs-readonly-146-g10c8443 |
Date: |
Mon, 28 Jul 2008 23:06:47 +0000 |
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 <address@hidden>
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 <address@hidden>
-----------------------------------------------------------------------
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 <address@hidden>
+
+ 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 <address@hidden>
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 @address@hidden/@/examples/@/forloop2.m4}; this
-version also optimizes based on the fact that the starting bound does
-not need to be passed to the helper @address@hidden
+version also optimizes overhead by calling four macros instead of six
+per iteration (excluding those in @var{text}), by not dereferencing the
address@hidden in the helper @address@hidden
@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
address@hidden(`forloop', `ifelse(eval(`($3) >= ($2)'), `1',
address@hidden `pushdef(`$1', eval(`$2'))_$0(`$1',
address@hidden(`forloop', `ifelse(eval(`($2) <= ($3)'), `1',
address@hidden `pushdef(`$1')_$0(`$1', eval(`$2'),
@result{} eval(`$3'), `$4')popdef(`$1')')')
@result{}define(`_forloop',
address@hidden `$3`'ifelse(indir(`$1'), `$2', `',
address@hidden `define(`$1', incr(indir(`$1')))$0($@@)')')
address@hidden `define(`$1', `$2')$4`'ifelse(`$2', `$3', `',
address@hidden `$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')
address@hidden:stdin:6: Warning: eval: bad input: (b) >= (a)
address@hidden: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')
address@hidden(eval(``($3) >= ($2)''), ``1'',
address@hidden ``pushdef(``$1'', eval(``$2''))_$0(``$1'',
address@hidden(eval(``($2) <= ($3)''), ``1'',
address@hidden ``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 @address@hidden/@/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
address@hidden@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
address@hidden(`foreachq',
address@hidden(`$1')_$0(`$1', `$3'ifelse(`$2', `', `',
address@hidden `, $2'))popdef(`$1')')
address@hidden(`_foreachq', `ifelse(`$#', `2', `',
address@hidden `define(`$1', `$3')$2`'$0(`$1', `$2'ifelse(`$#', `3', `',
address@hidden `, shift(shift(shift($@@)))'))')')
address@hidden(`foreachq', `ifelse(`$2', `', `',
address@hidden `pushdef(`$1')_$0(`$1', `$3', `', $2)popdef(`$1')')')
address@hidden(`_foreachq', `ifelse(`$#', `3', `',
address@hidden `define(`$1', `$4')$2`'$0(`$1', `$2',
address@hidden 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
address@hidden', `', `1', `2', `3', `4')
address@hidden: -3- shift(`x
address@hidden', `', `1', `2', `3', `4')
address@hidden: -2- shift(`', `1', `2', `3', `4')
address@hidden
address@hidden: -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')
address@hidden
address@hidden
@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')
address@hidden
address@hidden
@error{}m4trace: -4- shift(`x', `x
@error{}', `3', `4')
@error{}m4trace: -3- shift(`x
@error{}', `3', `4')
@error{}m4trace: -2- shift(`3', `4')
address@hidden
@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
address@hidden 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
address@hidden(`$1', `$n')$2`'}, with @samp{n} set to successive
address@hidden(`$1', address@hidden')$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 @address@hidden@}} 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
address@hidden as the tenth argument; the anticipation is that
address@hidden@address@hidden 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
address@hidden 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 @address@hidden, similary for
address@hidden as provided by @file{foreachq3.m4}. But
address@hidden as provided by @file{foreachq3.m4} or
address@hidden But
@code{foreachq}, as provided by @file{foreachq2.m4},
evaluates unquoted list elements twice while visiting the first list
element, once in @address@hidden and once in @address@hidden 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
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [SCM] GNU M4 source repository branch, master, updated. cvs-readonly-146-g10c8443,
Eric Blake <=