branch-1_4 reduce memory footprint

[Eric Blake]

I had no idea we were hammering malloc this badly.  I temporarily instrumented 
xmalloc to show usage patterns, then ran 'M4=src/m4 autoreconf -v' to profile 
the m4 configure script before and after this patch.

before:
autoreconf: Entering directory `.'
autoreconf: configure.ac: not using Gettext
autoreconf: running: aclocal -I m4
~~~ 13999747 cumulative bytes malloc'd, 4189 calls
~~~ 13764114 cumulative bytes malloc'd, 4130 calls
~~~ 12513859 cumulative bytes malloc'd, 3991 calls
autoreconf: configure.ac: tracing
~~~ 19272282 cumulative bytes malloc'd, 5097 calls
~~~ 19426793 cumulative bytes malloc'd, 5134 calls
~~~ 20182885 cumulative bytes malloc'd, 5328 calls
autoreconf: configure.ac: not using Libtool
autoreconf: running: /usr/local/bin/autoconf
~~~ 19272282 cumulative bytes malloc'd, 5097 calls
~~~ 19426793 cumulative bytes malloc'd, 5134 calls
autoreconf: running: /usr/local/bin/autoheader
~~~ 19272282 cumulative bytes malloc'd, 5097 calls
~~~ 19426793 cumulative bytes malloc'd, 5134 calls
~~~ 17110293 cumulative bytes malloc'd, 4566 calls
autoreconf: running: automake --no-force
~~~ 19272282 cumulative bytes malloc'd, 5097 calls
~~~ 19426793 cumulative bytes malloc'd, 5134 calls
~~~ 50728568 cumulative bytes malloc'd, 12861 calls
autoreconf: Leaving directory `.'

after:
autoreconf: Entering directory `.'
autoreconf: configure.ac: not using Gettext
autoreconf: running: aclocal -I m4
~~~ 108995 cumulative bytes malloc'd, 771 calls
~~~ 109074 cumulative bytes malloc'd, 770 calls
~~~ 110531 cumulative bytes malloc'd, 939 calls
autoreconf: configure.ac: tracing
~~~ 33306 cumulative bytes malloc'd, 363 calls
~~~ 33385 cumulative bytes malloc'd, 362 calls
~~~ 33573 cumulative bytes malloc'd, 370 calls
autoreconf: configure.ac: not using Libtool
autoreconf: running: /usr/local/bin/autoconf
~~~ 33306 cumulative bytes malloc'd, 363 calls
~~~ 33385 cumulative bytes malloc'd, 362 calls
autoreconf: running: /usr/local/bin/autoheader
~~~ 33306 cumulative bytes malloc'd, 363 calls
~~~ 33385 cumulative bytes malloc'd, 362 calls
~~~ 33365 cumulative bytes malloc'd, 364 calls
autoreconf: running: automake --no-force
~~~ 33306 cumulative bytes malloc'd, 363 calls
~~~ 33385 cumulative bytes malloc'd, 362 calls
~~~ 34232 cumulative bytes malloc'd, 387 calls
autoreconf: Leaving directory `.'

Timing-wise, with instrumentation turned off, I'm not seeing much difference on 
cygwin.  This is due in part to the fact that the working set of allocated 
memory pages is about the same between the two versions, at least with 
autoreconf's usage pattern: the biggest benefit of this patch is on nested 
macro calls, but autoconf encourages one level of quotes per macro invocation, 
so not many nested calls are occuring during autoreconf, and the pre-patch 
usage pattern ends up just freeing and then reallocating the same chunk of 
obstack memory multiple times, which a good malloc implementation will cater 
to.  But I suspect that platforms with a poorer algorithm behind malloc may 
notice the difference of fewer calls to malloc.  Also, other clients of m4 may 
have a usage pattern that is more affected with nested macro calls.  And if 
pressed, I could probably come up with a usage case that would trigger "memory 
exhausted" pre-patch but work post-patch.

At any rate, here is the patch for the branch, and I will be porting it to 
head.  Also on head, I may experiment with adding an obstack_regrow macro that 
I documented in the bug-m4 list.

2006-10-10  Eric Blake  <address@hidden>

        * src/macro.c (argcstack, argvstack): New variables for sharing
        obstacks across multiple macro calls.
        (expand_input): Initialize and tear down stack once per input
        file, instead of once per macro.
        (expand_macro): Reuse existing stacks when possible.
        (collect_arguments): Simplify slightly.

Index: src/macro.c
===================================================================
RCS file: /sources/m4/m4/src/Attic/macro.c,v
retrieving revision 1.1.1.1.2.12
diff -u -r1.1.1.1.2.12 macro.c
--- src/macro.c 10 Oct 2006 03:27:15 -0000      1.1.1.1.2.12
+++ src/macro.c 10 Oct 2006 16:29:25 -0000
@@ -33,6 +33,23 @@
 /* The number of the current call of expand_macro ().  */
 static int macro_call_id = 0;
 
+/* The shared stack of collected arguments for macro calls; as each
+   argument is collected, it is finished and its location stored in
+   argv_stack.  Normally, this stack can be used simultaneously by
+   multiple macro calls; the exception is when an outer macro has
+   generated some text, then calls a nested macro, in which case the
+   nested macro must use a local stack to leave the unfinished text
+   alone.  Too bad obstack.h does not provide an easy way to reopen a
+   finished object for further growth, but in practice this does not
+   hurt us too much.  */
+static struct obstack argc_stack;
+
+/* The shared stack of pointers to collected arguments for macro
+   calls.  This object is never finished; we exploit the fact that
+   obstack_blank is documented to take a negative size to reduce the
+   size again.  */
+static struct obstack argv_stack;
+
 /*----------------------------------------------------------------------.
 | This function read all input, and expands each token, one at a time.  |
 `----------------------------------------------------------------------*/
@@ -43,8 +60,14 @@
   token_type t;
   token_data td;
 
+  obstack_init (&argc_stack);
+  obstack_init (&argv_stack);
+
   while ((t = next_token (&td)) != TOKEN_EOF)
     expand_token ((struct obstack *) NULL, t, &td);
+
+  obstack_free (&argc_stack, NULL);
+  obstack_free (&argv_stack, NULL);
 }
 
 
@@ -211,8 +234,8 @@
 
   TOKEN_DATA_TYPE (&td) = TOKEN_TEXT;
   TOKEN_DATA_TEXT (&td) = SYMBOL_NAME (sym);
-  tdp = (token_data *) obstack_copy (arguments, &td, sizeof (td));
-  obstack_grow (argptr, &tdp, sizeof (tdp));
+  tdp = (token_data *) obstack_copy (arguments, &td, sizeof td);
+  obstack_ptr_grow (argptr, tdp);
 
   if (peek_token () == TOKEN_OPEN)
     {
@@ -226,9 +249,8 @@
              TOKEN_DATA_TYPE (&td) = TOKEN_TEXT;
              TOKEN_DATA_TEXT (&td) = "";
            }
-         tdp = (token_data *)
-           obstack_copy (arguments, &td, sizeof (td));
-         obstack_grow (argptr, &tdp, sizeof (tdp));
+         tdp = (token_data *) obstack_copy (arguments, &td, sizeof td);
+         obstack_ptr_grow (argptr, tdp);
        }
       while (more_args);
     }
@@ -278,8 +300,9 @@
 static void
 expand_macro (symbol *sym)
 {
-  struct obstack arguments;
-  struct obstack argptr;
+  struct obstack arguments;    /* Alternate obstack if argc_stack is busy.  */
+  unsigned argv_base;          /* Size of argv_stack on entry.  */
+  boolean use_argc_stack = TRUE;       /* Whether argc_stack is safe.  */
   token_data **argv;
   int argc;
   struct obstack *expansion;
@@ -299,16 +322,25 @@
 
   traced = (boolean) ((debug_level & DEBUG_TRACE_ALL) || SYMBOL_TRACED (sym));
 
-  obstack_init (&argptr);
-  obstack_init (&arguments);
+  argv_base = obstack_object_size (&argv_stack);
+  if (obstack_object_size (&argc_stack) > 0)
+  {
+    /* We cannot use argc_stack if this is a nested invocation, and an
+       outer invocation has an unfinished argument being
+       collected.  */
+     obstack_init (&arguments);
+     use_argc_stack = FALSE;
+  }
 
   if (traced && (debug_level & DEBUG_TRACE_CALL))
     trace_prepre (SYMBOL_NAME (sym), my_call_id);
 
-  collect_arguments (sym, &argptr, &arguments);
+  collect_arguments (sym, &argv_stack,
+                    use_argc_stack ? &argc_stack : &arguments);
 
-  argc = obstack_object_size (&argptr) / sizeof (token_data *);
-  argv = (token_data **) obstack_finish (&argptr);
+  argc = ((obstack_object_size (&argv_stack) - argv_base)
+         / sizeof (token_data *));
+  argv = (token_data **) (obstack_base (&argv_stack) + argv_base);
 
   if (traced)
     trace_pre (SYMBOL_NAME (sym), my_call_id, argc, argv);
@@ -326,6 +358,9 @@
   if (SYMBOL_DELETED (sym))
     free_symbol (sym);
 
-  obstack_free (&arguments, NULL);
-  obstack_free (&argptr, NULL);
+  if (use_argc_stack)
+    obstack_free (&argc_stack, argv[0]);
+  else
+    obstack_free (&arguments, NULL);
+  obstack_blank (&argv_stack, -argc * sizeof (token_data *));
 }