[SCM] GNU M4 source repository branch, master, updated. cvs-readonly-146-g10c8443

[Eric Blake]

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