From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: David Kastrup Newsgroups: gmane.lisp.guile.bugs Subject: bug#17049: [PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST Date: Thu, 20 Mar 2014 15:19:09 +0100 Message-ID: <1395325149-23272-1-git-send-email-dak@gnu.org> References: <1395314582-22733-1-git-send-email-dak@gnu.org> NNTP-Posting-Host: plane.gmane.org X-Trace: ger.gmane.org 1395325209 18556 80.91.229.3 (20 Mar 2014 14:20:09 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 20 Mar 2014 14:20:09 +0000 (UTC) Cc: David Kastrup To: 17049@debbugs.gnu.org Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Thu Mar 20 15:20:17 2014 Return-path: Envelope-to: guile-bugs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1WQdpJ-0001OS-4z for guile-bugs@m.gmane.org; Thu, 20 Mar 2014 15:20:09 +0100 Original-Received: from localhost ([::1]:47301 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQdpI-0008Te-Ko for guile-bugs@m.gmane.org; Thu, 20 Mar 2014 10:20:08 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:39580) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQdpE-0008SA-3P for bug-guile@gnu.org; Thu, 20 Mar 2014 10:20:05 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WQdpD-0002xr-18 for bug-guile@gnu.org; Thu, 20 Mar 2014 10:20:04 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:41188) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQdpC-0002xj-UU for bug-guile@gnu.org; Thu, 20 Mar 2014 10:20:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1WQdpB-0006Bu-JA for bug-guile@gnu.org; Thu, 20 Mar 2014 10:20:01 -0400 X-Loop: help-debbugs@gnu.org In-Reply-To: <1395314582-22733-1-git-send-email-dak@gnu.org> Resent-From: David Kastrup Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Thu, 20 Mar 2014 14:20:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17049 X-GNU-PR-Package: guile X-GNU-PR-Keywords: patch Original-Received: via spool by 17049-submit@debbugs.gnu.org id=B17049.139532515823732 (code B ref 17049); Thu, 20 Mar 2014 14:20:01 +0000 Original-Received: (at 17049) by debbugs.gnu.org; 20 Mar 2014 14:19:18 +0000 Original-Received: from localhost ([127.0.0.1]:42370 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WQdoT-0006Ah-Ej for submit@debbugs.gnu.org; Thu, 20 Mar 2014 10:19:17 -0400 Original-Received: from fencepost.gnu.org ([208.118.235.10]:43294) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WQdoR-0006AZ-Iu for 17049@debbugs.gnu.org; Thu, 20 Mar 2014 10:19:16 -0400 Original-Received: from localhost ([127.0.0.1]:50601 helo=lola) by fencepost.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQdoQ-0005cm-Tf; Thu, 20 Mar 2014 10:19:15 -0400 Original-Received: by lola (Postfix, from userid 1000) id 88EBEE08C6; Thu, 20 Mar 2014 15:19:14 +0100 (CET) X-Mailer: git-send-email 1.9.1 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 140.186.70.43 X-BeenThere: bug-guile@gnu.org List-Id: "Bug reports for GUILE, GNU's Ubiquitous Extension Language" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Original-Sender: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.bugs:7416 Archived-At: 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 --- 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