From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Mark H Weaver Newsgroups: gmane.lisp.guile.bugs Subject: bug#17049: [PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST Date: Mon, 31 Mar 2014 15:56:30 -0400 Message-ID: <87zjk6m9ap.fsf@yeeloong.lan> References: <87pplgnp2h.fsf@yeeloong.lan> <1395421018-29987-1-git-send-email-dak@gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1396295911 8165 80.91.229.3 (31 Mar 2014 19:58:31 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 31 Mar 2014 19:58:31 +0000 (UTC) Cc: 17049@debbugs.gnu.org To: David Kastrup Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Mon Mar 31 21:58:22 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 1WUiLc-0007wJ-CP for guile-bugs@m.gmane.org; Mon, 31 Mar 2014 21:58:20 +0200 Original-Received: from localhost ([::1]:51041 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WUiLb-0001k8-Ls for guile-bugs@m.gmane.org; Mon, 31 Mar 2014 15:58:19 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:34838) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WUiLS-0001eF-Bk for bug-guile@gnu.org; Mon, 31 Mar 2014 15:58:16 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WUiLK-0008AU-Gt for bug-guile@gnu.org; Mon, 31 Mar 2014 15:58:10 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:57070) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WUiLK-0008AP-DV for bug-guile@gnu.org; Mon, 31 Mar 2014 15:58:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1WUiLJ-0004fF-Tk for bug-guile@gnu.org; Mon, 31 Mar 2014 15:58:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Mark H Weaver Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Mon, 31 Mar 2014 19:58: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.139629585117885 (code B ref 17049); Mon, 31 Mar 2014 19:58:01 +0000 Original-Received: (at 17049) by debbugs.gnu.org; 31 Mar 2014 19:57:31 +0000 Original-Received: from localhost ([127.0.0.1]:58252 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WUiKo-0004eO-21 for submit@debbugs.gnu.org; Mon, 31 Mar 2014 15:57:30 -0400 Original-Received: from world.peace.net ([96.39.62.75]:48734) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WUiKl-0004eD-0Y for 17049@debbugs.gnu.org; Mon, 31 Mar 2014 15:57:27 -0400 Original-Received: from 209-6-91-212.c3-0.smr-ubr1.sbo-smr.ma.cable.rcn.com ([209.6.91.212] helo=yeeloong.lan) by world.peace.net with esmtpsa (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.72) (envelope-from ) id 1WUiKc-0006JP-Eq; Mon, 31 Mar 2014 15:57:18 -0400 In-Reply-To: <1395421018-29987-1-git-send-email-dak@gnu.org> (David Kastrup's message of "Fri, 21 Mar 2014 17:56:58 +0100") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) 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:7428 Archived-At: Hi David, This latest patch looks good to me, and Andy has agreed. Could you add a GNU ChangeLog-style commit log, according to our conventions, and send it in the format produced by "git format-patch"? Regards, Mark David Kastrup writes: > 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