another m4sugar speedup

[Eric Blake]

I was shocked at the extent of the improvement this little patch made!  Here's 
my timings running the head of the tree on coreutils, pre- and post-patch.

$ time autoconf -f

real    0m30.750s
user    0m29.908s
sys     0m4.074s

$ PATH=/usr/local/autoconf-patch/bin:$PATH
$ time autoconf -f

real    0m20.125s
user    0m19.316s
sys     0m4.387s

2007-10-02  Eric Blake  <address@hidden>

        Optimize recursion.
        * lib/m4sugar/m4sugar.m4 (m4_shiftn): This macro is called in a
        lot of hot spots; optimize it for 2 and 3 shifts.


From: Eric Blake <address@hidden>
Date: Tue, 2 Oct 2007 15:26:34 -0600
Subject: [PATCH] Optimize recursion.

* lib/m4sugar/m4sugar.m4 (m4_shiftn): This macro is called in a
lot of hot spots; optimize it for 2 and 3 shifts.

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

diff --git a/ChangeLog b/ChangeLog
index 2dcf677..13aa85a 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,9 @@
 2007-10-02  Eric Blake  <address@hidden>
 
+       Optimize recursion.
+       * lib/m4sugar/m4sugar.m4 (m4_shiftn): This macro is called in a
+       lot of hot spots; optimize it for 2 and 3 shifts.
+
        Optimize AC_PREREQ and other m4sugar numerics.
        * lib/m4sugar/m4sugar.m4 (m4_sign): Write with m4_eval.
        (m4_cmp): Compare arbitrary expressions, without overflow.
diff --git a/lib/m4sugar/m4sugar.m4 b/lib/m4sugar/m4sugar.m4
index 2070daa..7b20095 100644
--- a/lib/m4sugar/m4sugar.m4
+++ b/lib/m4sugar/m4sugar.m4
@@ -551,9 +551,16 @@ m4_define([m4_noquote],
 # m4_shiftn(N, ...)
 # -----------------
 # Returns ... shifted N times.  Useful for recursive "varargs" constructs.
+#
+# Internally, other m4sugar macros frequently use m4_shiftn(2, $@) and
+# m4_shiftn(3, $@).  Optimize these cases to avoid extra recursion and
+# expansion.
 m4_define([m4_shiftn],
-[m4_assert(($1 >= 0) && ($# > $1))dnl
-_m4_shiftn($@)])
+[m4_if(m4_eval(($1 >= 0) && ($# > $1)), 0,
+         [m4_assert(($1 >= 0) && ($# > $1))],
+       [$1], 2, [m4_shift(m4_shift(m4_shift($@)))],
+       [$1], 3, [m4_shift(m4_shift(m4_shift(m4_shift($@))))],
+       [_m4_shiftn($@)])])
 
 m4_define([_m4_shiftn],
 [m4_if([$1], 0,
-- 
1.5.3.2