* Re: master eb83344: Speed up (nthcdr N L) when L is circular
[not found] ` <20180820230136.541D8204F3@vcs0.savannah.gnu.org>
@ 2018-08-21 2:05 ` Glenn Morris
2018-08-21 6:36 ` [Emacs-diffs] " Pip Cet
1 sibling, 0 replies; 4+ messages in thread
From: Glenn Morris @ 2018-08-21 2:05 UTC (permalink / raw)
To: emacs-devel; +Cc: Paul Eggert
Paul Eggert wrote:
> branch: master
> commit eb83344fc7c08ec08b51e7700f1ac2632afa462c
> Speed up (nthcdr N L) when L is circular
This seems to cause build failures on RHEL 7.5 (gcc 4.8.5) and
hydra.nixos.org (gcc 4.8.3). Ref eg https://hydra.nixos.org/build/79942082 .
In toplevel form:
ecomplete.el:111:1:Error: Wrong type argument: listp, (type . elems)
make[2]: *** [ecomplete.elc] Error 1
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [Emacs-diffs] master eb83344: Speed up (nthcdr N L) when L is circular
[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 ` Pip Cet
2018-08-21 7:42 ` Pip Cet
1 sibling, 1 reply; 4+ messages in thread
From: Pip Cet @ 2018-08-21 6:36 UTC (permalink / raw)
To: emacs-devel, eggert; +Cc: emacs-diffs
On Mon, Aug 20, 2018 at 11:01 PM Paul Eggert <eggert@cs.ucla.edu> wrote:
> Speed up (nthcdr N L) when L is circular
...but slow it down when it isn't. May I suggest we fall back to the
old implementation for small n, maybe n <= 128 or something like that?
> + if (tail == li.tortoise)
> + tortoise_num = num;
I would prefer EQ (tail, li.tortoise) in the condition.
> + /* TAIL is part of a cycle. Reduce NUM modulo the cycle length to
> + avoid going around this cycle repeatedly. */
> + intptr_t cycle_length = tortoise_num - num;
I'm unsure about this line. I might be being stupid, but it seems to
me tortoise_num is always num + 1, given the code above:
FOR_EACH_TAIL_SAFE (tail)
{
if (num <= 0)
return tail;
if (tail == li.tortoise)
tortoise_num = num;
saved_tail = XCDR (tail);
num--;
rarely_quit (num);
}
We exit this loop if EQ (tail, li.tortoise), in which case
tortoise_num = num + 1, or if !CONSP (tail), in which case we have
returned by the time we assign to cycle_length.
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [Emacs-diffs] master eb83344: Speed up (nthcdr N L) when L is circular
2018-08-21 6:36 ` [Emacs-diffs] " Pip Cet
@ 2018-08-21 7:42 ` Pip Cet
2018-08-21 9:10 ` Paul Eggert
0 siblings, 1 reply; 4+ messages in thread
From: Pip Cet @ 2018-08-21 7:42 UTC (permalink / raw)
To: emacs-devel, eggert; +Cc: emacs-diffs
On Tue, Aug 21, 2018 at 6:36 AM Pip Cet <pipcet@gmail.com> wrote:
> I'm unsure about this line. I might be being stupid
I was, sorry. (nthcdr 1 (cons 'a 'b)) should probably be 'b, though.
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [Emacs-diffs] master eb83344: Speed up (nthcdr N L) when L is circular
2018-08-21 7:42 ` Pip Cet
@ 2018-08-21 9:10 ` Paul Eggert
0 siblings, 0 replies; 4+ messages in thread
From: Paul Eggert @ 2018-08-21 9:10 UTC (permalink / raw)
To: Pip Cet, emacs-devel; +Cc: Glenn Morris, emacs-diffs
[-- 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
^ permalink raw reply related [flat|nested] 4+ messages in thread
end of thread, other threads:[~2018-08-21 9:10 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
[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
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.