GNU bug report logs - #17049
[PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST

Previous Next

Full log

View this message in rfc822 format

From: David Kastrup <dak <at> gnu.org>
To: 17049 <at> debbugs.gnu.org
Cc: David Kastrup <dak <at> gnu.org>
Subject: bug#17049: [PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST
Date: Thu, 20 Mar 2014 15:19:09 +0100

Since reverse! is often used during list creation in C, an unvalidating
version could improve efficiency.

However, a validating version without the cost of validation also speeds
up existing code and does not require tradeoffs.

In contrast to most list operations, reverse! cannot get stuck in an
infinite loop but arrives back at the start when given an eventually or
fully circular list.  Because of that, one can save the cost of an
upfront proper list check at the price of having to do a double reversal
in the error case.

Signed-off-by: David Kastrup <dak <at> gnu.org>
---
As opposed to the previous patch, there is just a single error path,
making for a slightly nicer flow.

 libguile/list.c | 43 ++++++++++++++++++++++++++++++++++++-------
 1 file changed, 36 insertions(+), 7 deletions(-)

diff --git a/libguile/list.c b/libguile/list.c
index 1f44ad0..da99c8e 100644
--- a/libguile/list.c
+++ b/libguile/list.c
@@ -374,18 +374,47 @@ SCM_DEFINE (scm_reverse_x, "reverse!", 1, 1, 0,
 	    "@code{reverse!}")
 #define FUNC_NAME s_scm_reverse_x
 {
-  SCM_VALIDATE_LIST (1, lst);
+  SCM oldlst = lst;
+  SCM tail = SCM_BOOL_F;
+
   if (SCM_UNBNDP (new_tail))
     new_tail = SCM_EOL;
 
-  while (!SCM_NULL_OR_NIL_P (lst))
+  if (SCM_NULL_OR_NIL_P (lst))
+    return new_tail;
+
+  /* SCM_VALIDATE_LIST would run through the whole list to make sure it
+     is not eventually circular.  In contrast to most list operations,
+     reverse! cannot get stuck in an infinite loop but arrives back at
+     the start when given an eventually or fully circular list.  Because
+     of that, we can save the cost of an upfront proper list check at
+     the price of having to do a double reversal in the error case.
+  */
+
+  while (scm_is_pair (lst)) {
+    SCM old_tail = SCM_CDR (lst);
+    SCM_SETCDR (lst, tail);
+    tail = lst;
+    lst = old_tail;
+  };
+
+  if (SCM_LIKELY (SCM_NULL_OR_NIL_P (lst)))
     {
-      SCM old_tail = SCM_CDR (lst);
-      SCM_SETCDR (lst, new_tail);
-      new_tail = lst;
-      lst = old_tail;
+      SCM_SETCDR (oldlst, new_tail);
+      return tail;
     }
-  return new_tail;
+
+  /* We did not start with a proper list.  Undo the reversal. */
+
+  while (scm_is_pair (tail)) {
+    SCM old_tail = SCM_CDR (tail);
+    SCM_SETCDR (tail, lst);
+    lst = tail;
+    tail = old_tail;
+  };
+
+  scm_wrong_type_arg (FUNC_NAME, 1, lst);
+  return lst;
 }
 #undef FUNC_NAME
 
-- 
1.9.1

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.