Stage 18: try harder to reuse argv in recursion.

* m4/macro.c (make_argv_ref): Avoid wrapping $@ when possible.
(m4_push_args): Let make_argv_ref take care of pending data.
* doc/m4.texinfo (Improved foreach): Tweak wording to match new
performance capability.
* tests/others.at (recursion): Add tests to avoid performance
regression.

Signed-off-by: Eric Blake <ebb9@byu.net>

4 files changed, 117 insertions, 48 deletions

diff --git a/ChangeLog b/ChangeLog
index 8e55fdbd..877cda72 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,18 @@
+2008-02-23  Eric Blake  <ebb9@byu.net>
+
+	Stage 18: try harder to reuse argv in recursion.
+	When pushing arguments that contain an existing $@ ref, reuse the
+	ref rather than creating another layer of wrappers.
+	Memory impact: noticeable improvement, due to better $@ reuse.
+	Speed impact: noticeable improvement, due to O(n^2) to O(n)
+	reduction in unboxed recursion.
+	* m4/macro.c (make_argv_ref): Avoid wrapping $@ when possible.
+	(m4_push_args): Let make_argv_ref take care of pending data.
+	* doc/m4.texinfo (Improved foreach): Tweak wording to match new
+	performance capability.
+	* tests/others.at (recursion): Add tests to avoid performance
+	regression.
+
 2008-02-22  Eric Blake  <ebb9@byu.net>
 
 	Update NEWS.
diff --git a/doc/m4.texinfo b/doc/m4.texinfo
index ffc19495..909f8e3e 100644
--- a/doc/m4.texinfo
+++ b/doc/m4.texinfo
@@ -8406,17 +8406,16 @@ helper method immediately, the @samp{defn(`@var{iterator}')} no longer
 contains unexpanded macros.
 
 The astute m4 programmer might notice that the solution above still uses
-more memory, and thus more time, than strictly necessary.  Note that
-@samp{$2}, which contains an arbitrarily long quoted list, is expanded
-and rescanned three times per iteration of @code{_foreachq}.
-Furthermore, every iteration of the algorithm effectively unboxes then
-reboxes the list, which costs a couple of macro invocations.  It is
-possible to rewrite the algorithm for a bit more speed 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
-@file{m4-@value{VERSION}/@/examples/@/foreach3.m4}:
+more macro invocations than strictly necessary.  Note that @samp{$2},
+which contains an arbitrarily long quoted list, is expanded and
+rescanned three times per iteration of @code{_foreachq}.  Furthermore,
+every iteration of the algorithm effectively unboxes then reboxes the
+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 @file{m4-@value{VERSION}/@/examples/@/foreach3.m4}:
 
 @comment examples
 @example
@@ -8459,6 +8458,20 @@ foreachq(`x', ``1', `2', `3', `4'', `x
 @result{}4
 @end example
 
+Prior to M4 1.4.11, every instance of @samp{$@@} was rescanned as it was
+encountered.  Thus, the @file{foreachq3.m4} alternative used much less
+memory than @file{foreachq2.m4}, and executed as much as 10% faster,
+since each iteration encountered fewer @samp{$@@}.  However, the
+implementation of rescanning every byte in @samp{$@@} was quadratic in
+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.4.11 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.
+
 For yet another approach, the improved version of @code{foreach},
 available in @file{m4-@value{VERSION}/@/examples/@/foreach2.m4}, simply
 overquotes the arguments to @code{@w{_foreach}} to begin with, using
diff --git a/m4/macro.c b/m4/macro.c
index 0b860181..743d3266 100644
--- a/m4/macro.c
+++ b/m4/macro.c
@@ -1081,24 +1081,56 @@ make_argv_ref (m4 *context, m4_symbol_value *value, m4_obstack *obs,
 {
   m4__symbol_chain *chain;
 
-  assert (obstack_object_size (obs) == 0);
-  /* TODO reuse $@ even if argv has multiple array slots.  */
-  if (argv->wrapper && argv->arraylen == 1)
-    {
-      assert (argv->array[0]->type == M4_SYMBOL_COMP
-	      && argv->array[0]->u.u_c.wrapper);
-      chain= argv->array[0]->u.u_c.chain;
-      assert (!chain->next && chain->type == M4__CHAIN_ARGV
-	      && !chain->u.u_a.skip_last);
-      argv = chain->u.u_a.argv;
-      index += chain->u.u_a.index - 1;
-    }
   if (argv->argc <= index)
     return NULL;
+  value->type = M4_SYMBOL_COMP;
+  value->u.u_c.chain = value->u.u_c.end = NULL;
+
+  /* Cater to the common idiom of $0(`$1',shift(shift($@))), by
+     inlining the first few arguments and reusing the original $@ ref,
+     rather than creating another layer of wrappers.  */
+  while (argv->wrapper)
+    {
+      size_t i;
+      for (i = 0; i < argv->arraylen; i++)
+	{
+	  if (argv->array[i]->type == M4_SYMBOL_COMP
+	      && argv->array[i]->u.u_c.wrapper)
+	    break;
+	  if (index == 1)
+	    {
+	      m4__push_arg_quote (context, obs, argv, i + 1, quotes);
+	      /* TODO support M4_SYNTAX_COMMA.  */
+	      obstack_1grow (obs, ',');
+	    }
+	  else
+	    index--;
+	}
+      assert (i < argv->arraylen);
+      if (i + 1 == argv->arraylen)
+	{
+	  assert (argv->array[i]->type == M4_SYMBOL_COMP
+		  && argv->array[i]->u.u_c.wrapper);
+	  chain = argv->array[i]->u.u_c.chain;
+	  assert (!chain->next && chain->type == M4__CHAIN_ARGV
+		  && !chain->u.u_a.skip_last);
+	  argv = chain->u.u_a.argv;
+	  index += chain->u.u_a.index - 1;
+	}
+      else
+	{
+	  index += i;
+	  break;
+	}
+    }
 
+  m4__make_text_link (obs, &value->u.u_c.chain, &value->u.u_c.end);
   chain = (m4__symbol_chain *) obstack_alloc (obs, sizeof *chain);
-  value->type = M4_SYMBOL_COMP;
-  value->u.u_c.chain = value->u.u_c.end = chain;
+  if (value->u.u_c.end)
+    value->u.u_c.end->next = chain;
+  else
+    value->u.u_c.chain = chain;
+  value->u.u_c.end = chain;
   value->u.u_c.wrapper = true;
   value->u.u_c.has_func = argv->has_func;
   chain->next = NULL;
@@ -1591,11 +1623,8 @@ m4_push_args (m4 *context, m4_obstack *obs, m4_macro_args *argv, bool skip,
 {
   m4_symbol_value tmp;
   m4_symbol_value *value;
-  m4__symbol_chain *chain;
   size_t i = skip ? 2 : 1;
   const m4_string_pair *quotes = m4_get_syntax_quotes (M4SYNTAX);
-  char *str = NULL;
-  size_t len = obstack_object_size (obs);
 
   if (argv->argc <= i)
     return;
@@ -1606,30 +1635,10 @@ m4_push_args (m4 *context, m4_obstack *obs, m4_macro_args *argv, bool skip,
       return;
     }
 
-  /* Since make_argv_ref puts data on obs, we must first close any
-     pending data.  The resulting symbol contents live entirely on
-     obs, so we call push_symbol with a level of -1.  */
-  if (len)
-    {
-      obstack_1grow (obs, '\0');
-      str = (char *) obstack_finish (obs);
-    }
-
   /* TODO allow shift, $@, to push builtins without flatten.  */
   value = make_argv_ref (context, &tmp, obs, -1, argv, i, true,
 			 quote ? quotes : NULL);
   assert (value == &tmp);
-  if (len)
-    {
-      chain = (m4__symbol_chain *) obstack_alloc (obs, sizeof *chain);
-      chain->next = value->u.u_c.chain;
-      value->u.u_c.chain = chain;
-      chain->type = M4__CHAIN_STR;
-      chain->quote_age = 0;
-      chain->u.u_s.str = str;
-      chain->u.u_s.len = len;
-      chain->u.u_s.level = SIZE_MAX;
-    }
   if (m4__push_symbol (context, value, -1, argv->inuse))
     arg_mark (argv);
 }
diff --git a/tests/others.at b/tests/others.at
index 0b58c29b..fbd692b9 100644
--- a/tests/others.at
+++ b/tests/others.at
@@ -332,6 +332,38 @@ AT_CHECK_M4(["$abs_srcdir/null.m4"], [2],
 AT_CLEANUP
 
 
+## --------- ##
+## recursion ##
+## --------- ##
+
+AT_SETUP([recursion])
+
+dnl This input exploits contents of loop.m4 to print out the final value
+dnl of the recursion.
+AT_DATA([in.m4],
+[[define(`debug', `define(`popdef', `divert`'i')')dnl
+include(`loop.m4')dnl
+]])
+
+dnl boxed recursion
+AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10 -Dverbose loop.m4], [0],
+[[ 1 2 3 4 5 6 7 8 9 10
+]])
+AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=2500 loop.m4], [0])
+AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10000 in.m4], [0], [[10000
+]])
+
+dnl unboxed recursion
+AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10 -Dverbose -Dalt loop.m4], [0],
+[[ 1 2 3 4 5 6 7 8 9 10
+]])
+AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=2500 -Dalt loop.m4], [0])
+AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10000 -Dalt in.m4], [0], [[10000
+]])
+
+AT_CLEANUP
+
+
 ## ------- ##
 ## reverse ##
 ## ------- ##