Re: master b467bb5 4/4: Minimize ‘equal’ calls in (delete x vector)

Re: master b467bb5 4/4: Minimize ‘equal’ calls in (delete x vector)

[Pip Cet]

On Sat, Aug 15, 2020 at 6:20 PM Paul Eggert <eggert@cs.ucla.edu> wrote:
>
> branch: master
> commit b467bb531e1ab0eed57e1889004d2115e80e4292
> Author: Paul Eggert <eggert@cs.ucla.edu>
> Commit: Paul Eggert <eggert@cs.ucla.edu>
>
>     Minimize ‘equal’ calls in (delete x vector)
>
>     * src/fns.c (Fdelete): When deleting from a vector, call Fequal
>     only once per vector element.  This is faster when Fequal is slow,
>     and avoids the need to preinitialize the vector result.  Finish
>     when the result is exhausted, not when the input is exhausted;
>     the two are equivalent but the former may be faster.
>     * test/src/fns-tests.el (test-vector-delete): New test.
> ---
>  src/fns.c             | 38 +++++++++++++++++++++++++++++---------
>  test/src/fns-tests.el |  5 +++++
>  2 files changed, 34 insertions(+), 9 deletions(-)
>
> diff --git a/src/fns.c b/src/fns.c
> index c89bd81..069edbe 100644
> --- a/src/fns.c
> +++ b/src/fns.c
> @@ -1747,22 +1747,42 @@ changing the value of a sequence `foo'.  */)
>  {
>    if (VECTORP (seq))
>      {
> -      ptrdiff_t i, n;
> +      ptrdiff_t n = 0;
> +      ptrdiff_t size = ASIZE (seq);
> +      ptrdiff_t neqbits_words = ((size + BITS_PER_BITS_WORD - 1)
> +                                / BITS_PER_BITS_WORD);
> +      USE_SAFE_ALLOCA;
> +      bits_word *neqbits = SAFE_ALLOCA (neqbits_words * sizeof *neqbits);
> +      bits_word neqword = 0;
>
> -      for (i = n = 0; i < ASIZE (seq); ++i)
> -       if (NILP (Fequal (AREF (seq, i), elt)))
> -         ++n;

This code looks wrong to me:

> +      for (ptrdiff_t i = 0; i < size; i++)
> +       {
> +         bool neq = NILP (Fequal (AREF (seq, i), elt));
> +         n += neq;
> +         neqbits[i / BITS_PER_BITS_WORD] = neqword = (neqword << 1) + neq;
> +       }

That left-shifts the first sequence element's bit left by up to 63
times. But ...

> +             for (ptrdiff_t i = 0; ; i++)
> +               if (neqbits[i / BITS_PER_BITS_WORD]
> +                   & ((bits_word) 1 << (i % BITS_PER_BITS_WORD)))

this checks the non-left-shifted LSB for the first sequence element.

Indeed, we have

(delete t [nil t]) => [t]

which is nonsensical.

Re: master b467bb5 4/4: Minimize ‘equal’ calls in (delete x vector)

[Pip Cet]

[-- Attachment #1: Type: text/plain, Size: 265 bytes --]

On Sat, Aug 15, 2020 at 7:00 PM Pip Cet <pipcet@gmail.com> wrote:
> Indeed, we have
>
> (delete t [nil t]) => [t]
>
> which is nonsensical.

In fact, I'd prefer the attached: this is probably not worth worrying
too much about, so go with something straightforward?

[-- Attachment #2: 0001-Fix-delete-t-nil-t.patch --]
[-- Type: text/x-patch, Size: 1542 bytes --]

From 7e25be845efcb0ff6043b6100aaf81f6b8c9cafa Mon Sep 17 00:00:00 2001
From: Pip Cet <pipcet@gmail.com>
Date: Sat, 15 Aug 2020 19:20:27 +0000
Subject: [PATCH] Fix (delete t [nil t]).

---
 src/fns.c | 26 +++++---------------------
 1 file changed, 5 insertions(+), 21 deletions(-)

diff --git a/src/fns.c b/src/fns.c
index 069edbe90e..33c66aeef6 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -1749,35 +1749,19 @@ DEFUN ("delete", Fdelete, Sdelete, 2, 2, 0,
     {
       ptrdiff_t n = 0;
       ptrdiff_t size = ASIZE (seq);
-      ptrdiff_t neqbits_words = ((size + BITS_PER_BITS_WORD - 1)
-				 / BITS_PER_BITS_WORD);
       USE_SAFE_ALLOCA;
-      bits_word *neqbits = SAFE_ALLOCA (neqbits_words * sizeof *neqbits);
-      bits_word neqword = 0;
+      ptrdiff_t *posns = SAFE_ALLOCA (size * sizeof posns[0]);
 
       for (ptrdiff_t i = 0; i < size; i++)
-	{
-	  bool neq = NILP (Fequal (AREF (seq, i), elt));
-	  n += neq;
-	  neqbits[i / BITS_PER_BITS_WORD] = neqword = (neqword << 1) + neq;
-	}
+	if (NILP (Fequal (AREF (seq, i), elt)))
+	  posns[n++] = i;
 
       if (n != size)
 	{
 	  struct Lisp_Vector *p = allocate_vector (n);
 
-	  if (n != 0)
-	    {
-	      ptrdiff_t j = 0;
-	      for (ptrdiff_t i = 0; ; i++)
-		if (neqbits[i / BITS_PER_BITS_WORD]
-		    & ((bits_word) 1 << (i % BITS_PER_BITS_WORD)))
-		  {
-		    p->contents[j++] = AREF (seq, i);
-		    if (j == n)
-		      break;
-		  }
-	    }
+	  for (ptrdiff_t j = 0; j < n; j++)
+	    p->contents[j] = AREF (seq, posns[j]);
 
 	  XSETVECTOR (seq, p);
 	}
-- 
2.28.0

Re: master b467bb5 4/4: Minimize ‘equal’ calls in (delete x vector)

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 493 bytes --]

On 8/15/20 12:22 PM, Pip Cet wrote:

> I'd prefer the attached: this is probably not worth worrying
> too much about, so go with something straightforward?

Thanks for the quick review and patch. I came up with something a bit simpler 
and installed the attached.

It does bug me a bit that GCC generates bad code for 'NILP (Fequal (...))' here. 
I've been meaning to add a bool function equal (...) that would simplify the C 
source a bit and presumably let GCC do better, but that can wait.

[-- Attachment #2: 0001-Fix-recently-introduced-Fdelete-bug.patch --]
[-- Type: text/x-patch, Size: 2472 bytes --]

From 748afc183c2c44b7b2a582d3078cf3d8b4d5270a Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Sat, 15 Aug 2020 12:32:56 -0700
Subject: [PATCH] Fix recently-introduced Fdelete bug
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Problem reported by Pip Cet in:
https://lists.gnu.org/r/emacs-devel/2020-08/msg00444.html
* src/fns.c (Fdelete): Fix correctness bug via a simpler (though more
memory-intensive) approach.  It’s probably not worth optimizing
the memory usage yere.
* test/src/fns-tests.el (test-vector-delete): Add test for the bug.
---
 src/fns.c             | 29 ++++-------------------------
 test/src/fns-tests.el |  1 +
 2 files changed, 5 insertions(+), 25 deletions(-)

diff --git a/src/fns.c b/src/fns.c
index 069edbe90e..a3b8d6ef57 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -1749,38 +1749,17 @@ DEFUN ("delete", Fdelete, Sdelete, 2, 2, 0,
     {
       ptrdiff_t n = 0;
       ptrdiff_t size = ASIZE (seq);
-      ptrdiff_t neqbits_words = ((size + BITS_PER_BITS_WORD - 1)
-				 / BITS_PER_BITS_WORD);
       USE_SAFE_ALLOCA;
-      bits_word *neqbits = SAFE_ALLOCA (neqbits_words * sizeof *neqbits);
-      bits_word neqword = 0;
+      Lisp_Object *kept = SAFE_ALLOCA (size * sizeof *kept);
 
       for (ptrdiff_t i = 0; i < size; i++)
 	{
-	  bool neq = NILP (Fequal (AREF (seq, i), elt));
-	  n += neq;
-	  neqbits[i / BITS_PER_BITS_WORD] = neqword = (neqword << 1) + neq;
+	  kept[n] = AREF (seq, i);
+	  n += NILP (Fequal (AREF (seq, i), elt));
 	}
 
       if (n != size)
-	{
-	  struct Lisp_Vector *p = allocate_vector (n);
-
-	  if (n != 0)
-	    {
-	      ptrdiff_t j = 0;
-	      for (ptrdiff_t i = 0; ; i++)
-		if (neqbits[i / BITS_PER_BITS_WORD]
-		    & ((bits_word) 1 << (i % BITS_PER_BITS_WORD)))
-		  {
-		    p->contents[j++] = AREF (seq, i);
-		    if (j == n)
-		      break;
-		  }
-	    }
-
-	  XSETVECTOR (seq, p);
-	}
+	seq = Fvector (n, kept);
 
       SAFE_FREE ();
     }
diff --git a/test/src/fns-tests.el b/test/src/fns-tests.el
index 141de1d226..400e912648 100644
--- a/test/src/fns-tests.el
+++ b/test/src/fns-tests.el
@@ -898,5 +898,6 @@ test-secure-hash
 
 (ert-deftest test-vector-delete ()
   (let ((v1 (make-vector 1000 1)))
+    (should (equal (delete t [nil t]) [nil]))
     (should (equal (delete 1 v1) (vector)))
     (should (equal (delete 2 v1) v1))))
-- 
2.17.1

Re: master b467bb5 4/4: Minimize ‘equal’ calls in (delete x vector)

[Pip Cet]

On Sat, Aug 15, 2020 at 7:42 PM Paul Eggert <eggert@cs.ucla.edu> wrote:
> On 8/15/20 12:22 PM, Pip Cet wrote:
>
> > I'd prefer the attached: this is probably not worth worrying
> > too much about, so go with something straightforward?
>
> Thanks for the quick review and patch. I came up with something a bit simpler
> and installed the attached.

Looks correct, but establishes a rather questionable precedent of
putting Lisp_Objects in SAFE_ALLOCA'd space. That's okay in this
specific case, for a number of reasons, but it's bound to be copied by
someone in circumstances where it's not :-)

> It does bug me a bit that GCC generates bad code for 'NILP (Fequal (...))' here.
> I've been meaning to add a bool function equal (...) that would simplify the C
> source a bit and presumably let GCC do better, but that can wait.

What's GCC doing, for you? I see that it doesn't eliminate the
potentially dead store to kept[n] here, but other than that the code
looks okay to me.

Re: master b467bb5 4/4: Minimize ‘equal’ calls in (delete x vector)

[Paul Eggert]

On 8/15/20 1:21 PM, Pip Cet wrote:

> Looks correct, but establishes a rather questionable precedent of
> putting Lisp_Objects in SAFE_ALLOCA'd space. That's okay in this
> specific case, for a number of reasons, but it's bound to be copied by
> someone in circumstances where it's not :-)

It's not unprecedented, as there's one other instance of this, in 
font_sort_entities. Admittedly it's unusual; feel free to add a comment.
>> It does bug me a bit that GCC generates bad code for 'NILP (Fequal (...))' here.
>> I've been meaning to add a bool function equal (...) that would simplify the C
>> source a bit and presumably let GCC do better, but that can wait.
> 
> What's GCC doing, for you?

It's doing some weird thing involving cmp + adc. On second thought it's probably 
fine, as it is branch-free. Still, I always get confused when I write "!NILP 
(Fequal (a, b)' and too often I get it wrong. I'd rather write 'equal (a, b)'.