[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: m4_reverse
From: |
Eric Blake |
Subject: |
Re: m4_reverse |
Date: |
Tue, 29 Jul 2008 15:48:15 +0000 (UTC) |
User-agent: |
Loom/3.14 (http://gmane.org/) |
Eric Blake <ebb9 <at> byu.net> writes:
> In the process of testing it, I discovered that the current m4_list_cmp
> implementation on an m4_reverse'd list was tricky enough to foil the
> current m4 branch-1.6 heuristics on whether $@ recursion is occurring:
> behavior broke down into quadratic time because the m4_cdr calls hid the
> lists to the point that m4 failed to create back-references and ended up
> reparsing the list on every iteration. This patch includes a rewrite of
> m4_list_cmp to skip m4_cdr and make the $@ recursion explicit to the
> current m4 (although I might still try to patch m4 to recognize the
> admittedly corner-case recursion pattern); in addition to giving linear
> instead of quadratic behavior, it also reduces m4_list_cmp from 17 to 15
> macros per iteration.
My rewrite was asymmetric - m4_list_cmp([lots of 0], [0]) was fast, but
m4_list_cmp([0], [lots of 0]) was slow. m4 still couldn't see through the
deferred m4_shift in _m4_list_cmp_1, so this fixes it (but requires 16 macros
per iteration).
From: Eric Blake <address@hidden>
Date: Tue, 29 Jul 2008 08:28:01 -0600
Subject: [PATCH] One more m4_list_cmp tweak.
* lib/m4sugar/m4sugar.m4 (_m4_list_cmp_1): Don't defer shift.
* lib/m4sugar/foreach.m4 (m4_list_cmp): Fix comment.
* tests/m4sugar.at (recursion): Test both directions of list
disparity.
Signed-off-by: Eric Blake <address@hidden>
---
ChangeLog | 6 ++++++
lib/m4sugar/foreach.m4 | 4 ++--
lib/m4sugar/m4sugar.m4 | 2 +-
tests/m4sugar.at | 10 ++++++++++
4 files changed, 19 insertions(+), 3 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index 7019f37..877eb28 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
2008-07-29 Eric Blake <address@hidden>
+ One more m4_list_cmp tweak.
+ * lib/m4sugar/m4sugar.m4 (_m4_list_cmp_1): Don't defer shift.
+ * lib/m4sugar/foreach.m4 (m4_list_cmp): Fix comment.
+ * tests/m4sugar.at (recursion): Test both directions of list
+ disparity.
+
Add m4_reverse, and improve m4_list_cmp.
* lib/m4sugar/m4sugar.m4 (m4_reverse): New macro.
(m4_list_cmp): Rewrite to give linear behavior with M4 1.6 on an
diff --git a/lib/m4sugar/foreach.m4 b/lib/m4sugar/foreach.m4
index 7cc4358..1b5d2f9 100644
--- a/lib/m4sugar/foreach.m4
+++ b/lib/m4sugar/foreach.m4
@@ -212,8 +212,8 @@ m4_define([m4_joinall],
# trailing +0 is necessary to handle a missing list. Next, create a
# temporary macro to perform pairwise comparisons until an inequality
# is found. For example, m4_list_cmp([1], [1,2]) creates _m4_cmp as
-# m4_if([($1) != ($3)], [1], [m4_cmp([$1], [$3])],
-# [($2) != ($4)], [1], [m4_cmp([$2], [$4])],
+# m4_if(m4_eval([($1) != ($3)]), [1], [m4_cmp([$1], [$3])],
+# m4_eval([($2) != ($4)]), [1], [m4_cmp([$2], [$4])],
# [0]_m4_popdef([_m4_cmp], [_m4_size]))
# then calls _m4_cmp([1+0], [0], [1], [2+0])
m4_define([m4_list_cmp],
diff --git a/lib/m4sugar/m4sugar.m4 b/lib/m4sugar/m4sugar.m4
index 54439ce..a605947 100644
--- a/lib/m4sugar/m4sugar.m4
+++ b/lib/m4sugar/m4sugar.m4
@@ -2169,7 +2169,7 @@ m4_define([_m4_list_cmp],
[m4_if([$1], [], [0m4_ignore], [$2], [0], [m4_unquote], [$2m4_ignore])])
m4_define([_m4_list_cmp_1],
-[_m4_list_cmp_2([$2], [m4_shift2($@)], $1)])
+[_m4_list_cmp_2([$2], m4_dquote(m4_shift2($@)), $1)])
m4_define([_m4_list_cmp_2],
[_m4_list_cmp([$1$3], m4_cmp([$3+0], [$1+0]))(
diff --git a/tests/m4sugar.at b/tests/m4sugar.at
index c69e37e..2b73188 100644
--- a/tests/m4sugar.at
+++ b/tests/m4sugar.at
@@ -778,6 +778,8 @@ m4_max(m4_min([1]m4_for([i], [2], [10000], [],
m4_case([10000]m4_for([i], [1], [10000], [], [,i]),[end])
m4_list_cmp(m4_dquote(1m4_for([i], [2], [10000], [], [,i])),
m4_dquote(m4_reverse(10000m4_for([i], [9999], [1], [], [,i])), [0]))
+m4_list_cmp([0], [0m4_for([i], [1], [10000], [], [,0])])
+m4_list_cmp([0m4_for([i], [1], [10000], [], [,0])], [0])
m4_for([i], [1], [10000], [], [m4_define(i)])dnl
m4_undefine(1m4_for([i], [2], [10000], [], [,i]))dnl
m4_divert_pop(0)
@@ -790,6 +792,8 @@ AT_CHECK_M4SUGAR([-o-], [0], [[48894
10000
end
0
+0
+0
]])
AT_DATA_M4SUGAR([script.4s],
@@ -802,6 +806,8 @@ AT_DATA_M4SUGAR([script.4s],
10000
end
0
+0
+0
m4_exit([0])])
m4_init
m4_divert_push(0)[]dnl
@@ -815,6 +821,8 @@ m4_max(m4_min([1]m4_for([i], [2], [10000], [],
m4_case([10000]m4_for([i], [1], [10000], [], [,i]),[end])
m4_list_cmp(m4_dquote(1m4_for([i], [2], [10000], [], [,i])),
m4_dquote(m4_reverse(10000m4_for([i], [9999], [1], [], [,i])), [0]))
+m4_list_cmp([0], [0m4_for([i], [1], [10000], [], [,0])])
+m4_list_cmp([0m4_for([i], [1], [10000], [], [,0])], [0])
m4_for([i], [1], [10000], [], [m4_define(i)])dnl
m4_undefine(1m4_for([i], [2], [10000], [], [,i]))dnl
m4_divert_pop(0)
@@ -827,6 +835,8 @@ AT_CHECK_M4SUGAR([-o-], [0], [[48894
10000
end
0
+0
+0
]])
AT_CLEANUP
--
1.5.6.4
- m4_reverse, Eric Blake, 2008/07/29
- Re: m4_reverse,
Eric Blake <=