O(n^2) regression in m4_stack_foreach,m4_set_contents

[Eric Blake]

I noticed that in recent testsuite runs, the 'm4_set' test was taking a long 
time to complete.  This test is intentionally designed to take just a couple of 
seconds if all goes well, but take forever if a quadratic regression sneaks 
in.  Sure enough, I was able to isolate a smaller test case that exhibits the 
quadratic behavior.  'git bisect' is a cool command, using my testcase to 
identify the cause of the regression in less than a minute:

$ git bisect start HEAD v2.63 -- lib/m4sugar/
$ git bisect run sh -c 'echo '\''m4_divert_push([0])[]m4_for([i],[1],[4000],[],
[m4_set_add([a],i)])m4_len(m4_set_contents([a]))'\'' | timeout 5 m4 -Ilib 
m4sugar/m4sugar.m4 -'
...
commit 44579b83165eae1c2300e559eae5b697c685c2f7
Author: Eric Blake <address@hidden>
Date:   Thu Dec 18 17:15:13 2008 -0700

Ouch - the addition of two characters in m4sugar.m4 changed an algorithm from 
linear to quadratic.  Basically, each iteration adds an additional [] to the 
prefix from the previous round, so 10000 rounds of successively longer 
arguments means m4 has to parse well over 200,000,000 additional bytes with no 
impact to the output.

Since _m4_stack_reverse is an internal command, the fix is simple - hoist the 
[] to all callers, rather than adding another round each iteration.  I'm 
applying this:


From: Eric Blake <address@hidden>
Date: Thu, 12 Feb 2009 08:27:18 -0700
Subject: [PATCH] Fix m4_set speed regression introduced 2008-12-18.

* lib/m4sugar/m4sugar.m4 (_m4_stack_reverse): Alter API to avoid
creating larger argument on each iteration.
(m4_stack_foreach_sep, m4_stack_foreach_sep_lifo)
(_m4_set_contents_2): Adjust all four-argument callers.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog              |    8 ++++++++
 lib/m4sugar/m4sugar.m4 |   21 +++++++++++----------
 2 files changed, 19 insertions(+), 10 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index c72253a..90f8cd8 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,11 @@
+2009-02-12  Eric Blake  <address@hidden>
+
+       Fix m4_set speed regression introduced 2008-12-18.
+       * lib/m4sugar/m4sugar.m4 (_m4_stack_reverse): Alter API to avoid
+       creating larger argument on each iteration.
+       (m4_stack_foreach_sep, m4_stack_foreach_sep_lifo)
+       (_m4_set_contents_2): Adjust all four-argument callers.
+
 2009-02-05  Eric Blake  <address@hidden>

        Mention new AC_DEFUN_ONCE clients.
diff --git a/lib/m4sugar/m4sugar.m4 b/lib/m4sugar/m4sugar.m4
index 55dc644..8356d08 100644
--- a/lib/m4sugar/m4sugar.m4
+++ b/lib/m4sugar/m4sugar.m4
@@ -1295,10 +1295,10 @@ m4_define([m4_stack_foreach_lifo],
 # is equivalent to m4_stack_foreach_sep([a], [b(], [)]).
 m4_define([m4_stack_foreach_sep],
 [_m4_stack_reverse([$1], [m4_tmp-$1])]dnl
-[_m4_stack_reverse([m4_tmp-$1], [$1], [$2[]_m4_defn([m4_tmp-$1])$3], [$4])])
+[_m4_stack_reverse([m4_tmp-$1], [$1], [$2[]_m4_defn([m4_tmp-$1])$3], [$4[]])])

 m4_define([m4_stack_foreach_sep_lifo],
-[_m4_stack_reverse([$1], [m4_tmp-$1], [$2[]_m4_defn([m4_tmp-$1])$3], [$4])]dnl
+[_m4_stack_reverse([$1], [m4_tmp-$1], [$2[]_m4_defn([m4_tmp-$1])$3], [$4[]])]
dnl
 [_m4_stack_reverse([m4_tmp-$1], [$1])])


@@ -1307,15 +1307,16 @@ m4_define([m4_stack_foreach_sep_lifo],
 # A recursive worker for pushdef stack manipulation.  Destructively
 # copy the OLD stack into the NEW, and expanding ACTION for each
 # iteration.  After the first iteration, SEP is promoted to the front
-# of ACTION.  The current definition is examined after the NEW has
-# been pushed but before OLD has been popped; this order is important,
-# as ACTION is permitted to operate on either _m4_defn([OLD]) or
-# _m4_defn([NEW]).  Since the operation is destructive, this macro is
-# generally used twice, with a temporary macro name holding the
-# swapped copy.
+# of ACTION (note that SEP should include a trailing [] if it is to
+# avoid interfering with ACTION).  The current definition is examined
+# after the NEW has been pushed but before OLD has been popped; this
+# order is important, as ACTION is permitted to operate on either
+# _m4_defn([OLD]) or _m4_defn([NEW]).  Since the operation is
+# destructive, this macro is generally used twice, with a temporary
+# macro name holding the swapped copy.
 m4_define([_m4_stack_reverse],
 [m4_ifdef([$1], [m4_pushdef([$2],
-  _m4_defn([$1]))$3[]_m4_popdef([$1])$0([$1], [$2], [$4[]$3])])])
+  _m4_defn([$1]))$3[]_m4_popdef([$1])$0([$1], [$2], [$4$3])])])



@@ -2955,7 +2956,7 @@ m4_define([_m4_set_contents_1c],

 m4_define([_m4_set_contents_2],
 [_m4_stack_reverse([_m4_set_($1)], [_m4_set([$1])],
-  [$2[]_m4_defn([_m4_set_($1)])$3], [$4])])
+  [$2[]_m4_defn([_m4_set_($1)])$3], [$4[]])])

 # m4_set_delete(SET)
 # ------------------
-- 
1.6.1.2