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: Fri, 21 Mar 2014 17:56:58 +0100 Message-ID: <1395421018-29987-1-git-send-email-dak@gnu.org> References: <87pplgnp2h.fsf@yeeloong.lan> NNTP-Posting-Host: plane.gmane.org X-Trace: ger.gmane.org 1395421084 3247 80.91.229.3 (21 Mar 2014 16:58:04 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 21 Mar 2014 16:58:04 +0000 (UTC) Cc: David Kastrup To: 17049@debbugs.gnu.org Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Fri Mar 21 17:58:11 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 1WR2lm-0000XH-RS for guile-bugs@m.gmane.org; Fri, 21 Mar 2014 17:58:11 +0100 Original-Received: from localhost ([::1]:53855 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WR2lm-0004KZ-E8 for guile-bugs@m.gmane.org; Fri, 21 Mar 2014 12:58:10 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:58357) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WR2li-0004H6-GU for bug-guile@gnu.org; Fri, 21 Mar 2014 12:58:07 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WR2lg-0003XP-Tb for bug-guile@gnu.org; Fri, 21 Mar 2014 12:58:06 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:42633) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WR2lg-0003XK-Ph for bug-guile@gnu.org; Fri, 21 Mar 2014 12:58:04 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1WR2lg-0001QL-8h for bug-guile@gnu.org; Fri, 21 Mar 2014 12:58:04 -0400 X-Loop: help-debbugs@gnu.org Resent-From: David Kastrup Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Fri, 21 Mar 2014 16:58:04 +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.13954210455378 (code B ref 17049); Fri, 21 Mar 2014 16:58:04 +0000 Original-Received: (at 17049) by debbugs.gnu.org; 21 Mar 2014 16:57:25 +0000 Original-Received: from localhost ([127.0.0.1]:43813 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WR2l1-0001Ob-7J for submit@debbugs.gnu.org; Fri, 21 Mar 2014 12:57:24 -0400 Original-Received: from fencepost.gnu.org ([208.118.235.10]:54866) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WR2ky-0001OT-Ok for 17049@debbugs.gnu.org; Fri, 21 Mar 2014 12:57:21 -0400 Original-Received: from localhost ([127.0.0.1]:33939 helo=lola) by fencepost.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WR2ky-0002eB-1A; Fri, 21 Mar 2014 12:57:20 -0400 Original-Received: by lola (Postfix, from userid 1000) id 32A44E09F9; Fri, 21 Mar 2014 17:57:08 +0100 (CET) X-Mailer: git-send-email 1.9.1 In-Reply-To: <87pplgnp2h.fsf@yeeloong.lan> 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:7420 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 --- Formatting changes. Also renamed oldlst to old_lst to match the existing variable name style better. libguile/list.c | 41 ++++++++++++++++++++++++++++++++++++----- 1 file changed, 36 insertions(+), 5 deletions(-) diff --git a/libguile/list.c b/libguile/list.c index 1f44ad0..9b2a0d7 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 old_lst = 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, new_tail); - new_tail = lst; + SCM_SETCDR (lst, tail); + tail = lst; lst = old_tail; } - return new_tail; + + if (SCM_LIKELY (SCM_NULL_OR_NIL_P (lst))) + { + SCM_SETCDR (old_lst, new_tail); + return 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