From: Paul Eggert <eggert@cs.ucla.edu>
To: Pip Cet <pipcet@gmail.com>, emacs-devel@gnu.org
Cc: Glenn Morris <rgm@gnu.org>, emacs-diffs@gnu.org
Subject: Re: [Emacs-diffs] master eb83344: Speed up (nthcdr N L) when L is circular
Date: Tue, 21 Aug 2018 02:10:45 -0700 [thread overview]
Message-ID: <a5f7ffa9-36bb-952b-2149-f7fb7452203a@cs.ucla.edu> (raw)
In-Reply-To: <CAOqdjBfT0Ky6gWB-UnJbmb2K589aZ9r29uY4o9NS714_Kzxpyg@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 334 bytes --]
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.
[-- Attachment #2: 0001-Fix-glitches-introduced-by-nthcdr-changes.patch --]
[-- Type: text/x-patch, Size: 2883 bytes --]
From 77fc2725985b4e5ef977ae6930835c7f0771c61c Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@Penguin.CS.UCLA.EDU>
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
prev parent reply other threads:[~2018-08-21 9:10 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <20180820230135.12359.43125@vcs0.savannah.gnu.org>
[not found] ` <20180820230136.541D8204F3@vcs0.savannah.gnu.org>
2018-08-21 2:05 ` master eb83344: Speed up (nthcdr N L) when L is circular Glenn Morris
2018-08-21 6:36 ` [Emacs-diffs] " Pip Cet
2018-08-21 7:42 ` Pip Cet
2018-08-21 9:10 ` Paul Eggert [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=a5f7ffa9-36bb-952b-2149-f7fb7452203a@cs.ucla.edu \
--to=eggert@cs.ucla.edu \
--cc=emacs-devel@gnu.org \
--cc=emacs-diffs@gnu.org \
--cc=pipcet@gmail.com \
--cc=rgm@gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).