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.