Re: master eb83344: Speed up (nthcdr N L) when L is circular

Re: master eb83344: Speed up (nthcdr N L) when L is circular

[Glenn Morris]

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

Re: [Emacs-diffs] master eb83344: Speed up (nthcdr N L) when L is circular

[Pip Cet]

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.

Re: [Emacs-diffs] master eb83344: Speed up (nthcdr N L) when L is circular

[Pip Cet]

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.

Re: [Emacs-diffs] master eb83344: Speed up (nthcdr N L) when L is circular

[Paul Eggert]

[-- 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