* 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.