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 12:23:02 +0100 Message-ID: <1395314582-22733-1-git-send-email-dak@gnu.org> NNTP-Posting-Host: plane.gmane.org X-Trace: ger.gmane.org 1395314658 12698 80.91.229.3 (20 Mar 2014 11:24:18 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 20 Mar 2014 11:24:18 +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 12:24:26 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 1WQb5C-0000ng-Ns for guile-bugs@m.gmane.org; Thu, 20 Mar 2014 12:24:22 +0100 Original-Received: from localhost ([::1]:46363 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQb59-0007vT-9M for guile-bugs@m.gmane.org; Thu, 20 Mar 2014 07:24:19 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:59539) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQb50-0007n9-2D for bug-guile@gnu.org; Thu, 20 Mar 2014 07:24:15 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WQb4s-0002Ti-9l for bug-guile@gnu.org; Thu, 20 Mar 2014 07:24:10 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:40725) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQb4s-0002Te-6p for bug-guile@gnu.org; Thu, 20 Mar 2014 07:24:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1WQb4r-0000GO-UP for bug-guile@gnu.org; Thu, 20 Mar 2014 07:24:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: David Kastrup Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Thu, 20 Mar 2014 11:24:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 17049 X-GNU-PR-Package: guile X-GNU-PR-Keywords: patch X-Debbugs-Original-To: bug-guile@gnu.org Original-Received: via spool by submit@debbugs.gnu.org id=B.1395314606946 (code B ref -1); Thu, 20 Mar 2014 11:24:01 +0000 Original-Received: (at submit) by debbugs.gnu.org; 20 Mar 2014 11:23:26 +0000 Original-Received: from localhost ([127.0.0.1]:41907 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WQb4H-0000FB-N7 for submit@debbugs.gnu.org; Thu, 20 Mar 2014 07:23:26 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:57707) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WQb4E-0000F0-Q7 for submit@debbugs.gnu.org; Thu, 20 Mar 2014 07:23:23 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WQb49-0002NN-B9 for submit@debbugs.gnu.org; Thu, 20 Mar 2014 07:23:22 -0400 Original-Received: from lists.gnu.org ([2001:4830:134:3::11]:55211) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQb49-0002NH-7t for submit@debbugs.gnu.org; Thu, 20 Mar 2014 07:23:17 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:59412) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQb48-0007kz-3H for bug-guile@gnu.org; Thu, 20 Mar 2014 07:23:17 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WQb47-0002Mz-62 for bug-guile@gnu.org; Thu, 20 Mar 2014 07:23:16 -0400 Original-Received: from fencepost.gnu.org ([208.118.235.10]:41710) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQb47-0002Mv-2U for bug-guile@gnu.org; Thu, 20 Mar 2014 07:23:15 -0400 Original-Received: from localhost ([127.0.0.1]:47340 helo=lola) by fencepost.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQb46-00084z-J2; Thu, 20 Mar 2014 07:23:14 -0400 Original-Received: by lola (Postfix, from userid 1000) id 34F38E08C6; Thu, 20 Mar 2014 12:23:14 +0100 (CET) X-Mailer: git-send-email 1.9.1 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). 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:7414 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 --- libguile/list.c | 45 ++++++++++++++++++++++++++++++++++++++------- 1 file changed, 38 insertions(+), 7 deletions(-) diff --git a/libguile/list.c b/libguile/list.c index 1f44ad0..8cbdfcf 100644 --- a/libguile/list.c +++ b/libguile/list.c @@ -374,18 +374,49 @@ 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_CONS (1, lst); + + /* 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. + */ + + do { + SCM old_tail = SCM_CDR (lst); + SCM_SETCDR (lst, tail); + tail = lst; + lst = old_tail; + } while (scm_is_pair (lst)); + + 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. */ + + do { + SCM old_tail = SCM_CDR (tail); + SCM_SETCDR (tail, lst); + lst = tail; + tail = old_tail; + } while (scm_is_pair (tail)); + + scm_wrong_type_arg (FUNC_NAME, 1, lst); + return oldlst; } #undef FUNC_NAME -- 1.9.1