From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Paul Eggert Newsgroups: gmane.emacs.devel,gmane.emacs.diffs Subject: Re: [Emacs-diffs] master eb83344: Speed up (nthcdr N L) when L is circular Date: Tue, 21 Aug 2018 02:10:45 -0700 Organization: UCLA Computer Science Department Message-ID: References: <20180820230135.12359.43125@vcs0.savannah.gnu.org> <20180820230136.541D8204F3@vcs0.savannah.gnu.org> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="------------AE574FC1CB1E333F29BCA87A" X-Trace: blaine.gmane.org 1534842535 17999 195.159.176.226 (21 Aug 2018 09:08:55 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Tue, 21 Aug 2018 09:08:55 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.9.1 Cc: Glenn Morris , emacs-diffs@gnu.org To: Pip Cet , emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Tue Aug 21 11:08:51 2018 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1fs2eg-0004Zt-II for ged-emacs-devel@m.gmane.org; Tue, 21 Aug 2018 11:08:50 +0200 Original-Received: from localhost ([::1]:51682 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fs2gm-0007mq-Lj for ged-emacs-devel@m.gmane.org; Tue, 21 Aug 2018 05:11:00 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:36788) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fs2gf-0007ma-TR for emacs-devel@gnu.org; Tue, 21 Aug 2018 05:10:54 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fs2gb-0007JU-TY for emacs-devel@gnu.org; Tue, 21 Aug 2018 05:10:53 -0400 Original-Received: from zimbra.cs.ucla.edu ([131.179.128.68]:51822) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fs2gb-0007Fr-Hm; Tue, 21 Aug 2018 05:10:49 -0400 Original-Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id CD9E11600CC; Tue, 21 Aug 2018 02:10:47 -0700 (PDT) Original-Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id vhdC8DGDRI9p; Tue, 21 Aug 2018 02:10:46 -0700 (PDT) Original-Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id A647D160192; Tue, 21 Aug 2018 02:10:46 -0700 (PDT) X-Virus-Scanned: amavisd-new at zimbra.cs.ucla.edu Original-Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id qDksLsPDXtYK; Tue, 21 Aug 2018 02:10:46 -0700 (PDT) Original-Received: from [192.168.1.9] (unknown [47.154.30.119]) by zimbra.cs.ucla.edu (Postfix) with ESMTPSA id 3EF581600CC; Tue, 21 Aug 2018 02:10:46 -0700 (PDT) In-Reply-To: Content-Language: en-US X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 131.179.128.68 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.org gmane.emacs.devel:228780 gmane.emacs.diffs:146728 Archived-At: This is a multi-part message in MIME format. --------------AE574FC1CB1E333F29BCA87A Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Pip Cet wrote: > (nthcdr 1 (cons 'a 'b)) should probably be 'b, though. Yes, Glenn also noted that bug. I fixed it by installing the attached patch. It also follows your suggestion of a quick path for small N (where we can omit both circularity and quit testing), plus to use EQ to compare objects. Thanks for checking the patch. --------------AE574FC1CB1E333F29BCA87A Content-Type: text/x-patch; name="0001-Fix-glitches-introduced-by-nthcdr-changes.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0001-Fix-glitches-introduced-by-nthcdr-changes.patch" >From 77fc2725985b4e5ef977ae6930835c7f0771c61c Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Tue, 21 Aug 2018 02:05:07 -0700 Subject: [PATCH] Fix glitches introduced by nthcdr changes * src/fns.c (Fnthcdr): Fix recently-introduced bug when nthcdr is supposed to yield a non-nil non-cons. Reported by Glenn Morris and by Pip Cet here: https://lists.gnu.org/r/emacs-devel/2018-08/msg00699.html https://lists.gnu.org/r/emacs-devel/2018-08/msg00708.html Speed up nthcdr for small N, as suggested by Pip Cet here: https://lists.gnu.org/r/emacs-devel/2018-08/msg00707.html * test/src/fns-tests.el (test-nthcdr-simple): New test. --- src/fns.c | 35 +++++++++++++++++++++++++++-------- test/src/fns-tests.el | 5 +++++ 2 files changed, 32 insertions(+), 8 deletions(-) diff --git a/src/fns.c b/src/fns.c index 8cff6b1b6c..9d681017c1 100644 --- a/src/fns.c +++ b/src/fns.c @@ -1402,6 +1402,8 @@ DEFUN ("nthcdr", Fnthcdr, Snthcdr, 2, 2, 0, doc: /* Take cdr N times on LIST, return the result. */) (Lisp_Object n, Lisp_Object list) { + Lisp_Object tail = list; + CHECK_INTEGER (n); /* A huge but in-range EMACS_INT that can be substituted for a @@ -1412,24 +1414,41 @@ DEFUN ("nthcdr", Fnthcdr, Snthcdr, 2, 2, 0, EMACS_INT num; if (FIXNUMP (n)) - num = XFIXNUM (n); + { + num = XFIXNUM (n); + + /* Speed up small lists by omitting circularity and quit checking. */ + if (num < 128) + { + for (; 0 < num; num--, tail = XCDR (tail)) + if (! CONSP (tail)) + { + CHECK_LIST_END (tail, list); + return Qnil; + } + return tail; + } + } else { - num = mpz_sgn (XBIGNUM (n)->value); - if (0 < num) - num = large_num; + if (mpz_sgn (XBIGNUM (n)->value) < 0) + return tail; + num = large_num; } EMACS_INT tortoise_num = num; - Lisp_Object tail = list, saved_tail = tail; + Lisp_Object saved_tail = tail; FOR_EACH_TAIL_SAFE (tail) { - if (num <= 0) - return tail; - if (tail == li.tortoise) + /* If the tortoise just jumped (which is rare), + update TORTOISE_NUM accordingly. */ + if (EQ (tail, li.tortoise)) tortoise_num = num; + saved_tail = XCDR (tail); num--; + if (num == 0) + return saved_tail; rarely_quit (num); } diff --git a/test/src/fns-tests.el b/test/src/fns-tests.el index 92dc18fa03..b180f30f28 100644 --- a/test/src/fns-tests.el +++ b/test/src/fns-tests.el @@ -624,6 +624,11 @@ dot2 (should (eq (gethash b2 hash) (funcall test b1 b2))))))) +(ert-deftest test-nthcdr-simple () + (should (eq (nthcdr 0 'x) 'x)) + (should (eq (nthcdr 1 '(x . y)) 'y)) + (should (eq (nthcdr 2 '(x y . z)) 'z))) + (ert-deftest test-nthcdr-circular () (dolist (len '(1 2 5 37 120 997 1024)) (let ((cycle (make-list len nil))) -- 2.17.1 --------------AE574FC1CB1E333F29BCA87A--