Re: [PATCH v7 09/17] string: Improve generic strcmp

[Noah Goldstein <goldstein.w.n@gmail.com>]

On Wed, Jan 11, 2023 at 12:46 PM Adhemerval Zanella
<adhemerval.zanella@linaro.org> wrote:
>
> From: Adhemerval Zanella Netto <adhemerval.zanella@linaro.org>
>
> New generic implementation tries to use word operations along with
> the new string-fz{b,i} functions even for inputs with different
> alignments (with still uses aligned access plus merge operation
> to get a correct word by word comparison).
>
> Checked on x86_64-linux-gnu, i686-linux-gnu, powerpc64-linux-gnu,
> and powerpc-linux-gnu by removing the arch-specific assembly
> implementation and disabling multi-arch (it covers both LE and BE
> for 64 and 32 bits).
>
> Co-authored-by: Richard Henderson <richard.henderson@linaro.org>
> ---
>  string/strcmp.c | 119 +++++++++++++++++++++++++++++++++++++++++-------
>  1 file changed, 103 insertions(+), 16 deletions(-)
>
> diff --git a/string/strcmp.c b/string/strcmp.c
> index 053f5a8d2b..fafd967567 100644
> --- a/string/strcmp.c
> +++ b/string/strcmp.c
> @@ -15,33 +15,120 @@
>     License along with the GNU C Library; if not, see
>     <https://www.gnu.org/licenses/>.  */
>
> +#include <stdint.h>
> +#include <string-extbyte.h>
> +#include <string-fzb.h>
> +#include <string-fzi.h>
>  #include <string.h>
> +#include <memcopy.h>
>
> -#undef strcmp
> -
> -#ifndef STRCMP
> -# define STRCMP strcmp
> +#ifdef STRCMP
> +# define strcmp STRCMP
>  #endif
>
> +static inline int
> +final_cmp (const op_t w1, const op_t w2)
> +{
> +  /* It can not use index_first_zero_ne because it must not compare past the
> +     final '/0' is present (and final_cmp is called before has_zero check).
> +   */
> +  for (size_t i = 0; i < sizeof (op_t); i++)
> +    {
> +      unsigned char c1 = extractbyte (w1, i);
> +      unsigned char c2 = extractbyte (w2, i);
> +      if (c1 == '\0' || c1 != c2)
> +        return c1 - c2;
> +    }
> +  return 0;
> +}
> +
> +/* Aligned loop: if a difference is found, exit to compare the bytes.  Else
> +   if a zero is found we have equal strings.  */
> +static inline int
> +strcmp_aligned_loop (const op_t *x1, const op_t *x2, op_t w1)
> +{
> +  op_t w2 = *x2++;
> +
> +  while (w1 == w2)
> +    {
> +      if (has_zero (w1))
> +       return 0;
> +      w1 = *x1++;
> +      w2 = *x2++;
> +    }
> +
> +  return final_cmp (w1, w2);
> +}
> +
> +/* Unaligned loop: align the first partial of P2, with 0xff for the rest of
> +   the bytes so that we can also apply the has_zero test to see if we have
> +   already reached EOS.  If we have, then we can simply fall through to the
> +   final comparison.  */
> +static inline int
> +strcmp_unaligned_loop (const op_t *x1, const op_t *x2, op_t w1, uintptr_t ofs)
> +{
> +  op_t w2a = *x2++;
> +  uintptr_t sh_1 = ofs * CHAR_BIT;
> +  uintptr_t sh_2 = sizeof(op_t) * CHAR_BIT - sh_1;
> +
> +  op_t w2 = MERGE (w2a, sh_1, (op_t)-1, sh_2);
> +  if (!has_zero (w2))
> +    {
> +      op_t w2b;
> +
> +      /* Unaligned loop.  The invariant is that W2B, which is "ahead" of W1,
> +        does not contain end-of-string.  Therefore it is safe (and necessary)
> +        to read another word from each while we do not have a difference.  */
> +      while (1)
> +       {
> +         w2b = *x2++;
> +         w2 = MERGE (w2a, sh_1, w2b, sh_2);
> +         if (w1 != w2)
> +           return final_cmp (w1, w2);
> +         if (has_zero (w2b))
> +           break;
> +         w1 = *x1++;
> +         w2a = w2b;
> +       }
> +
> +      /* Zero found in the second partial of P2.  If we had EOS in the aligned
> +        word, we have equality.  */
> +      if (has_zero (w1))
Can't the zero in w1 and w2b be at different bytes? I.e even
though they both contain zero the strings are not-equal?

Imo it would be make more sense to just replace the `if
(has_zero(w2b)) break` above
with `if(has_zero (w1)) return 0;` and entirely remove the tail.
> +       return 0;
> +
> +      /* Load the final word of P1 and align the final partial of P2.  */
> +      w1 = *x1++;
> +      w2 = MERGE (w2b, sh_1, 0, sh_2);
> +    }
> +
> +  return final_cmp (w1, w2);
> +}
> +
>  /* Compare S1 and S2, returning less than, equal to or
>     greater than zero if S1 is lexicographically less than,
>     equal to or greater than S2.  */
>  int
> -STRCMP (const char *p1, const char *p2)
> +strcmp (const char *p1, const char *p2)
>  {
> -  const unsigned char *s1 = (const unsigned char *) p1;
> -  const unsigned char *s2 = (const unsigned char *) p2;
> -  unsigned char c1, c2;
> -
> -  do
> +  /* Handle the unaligned bytes of p1 first.  */
> +  uintptr_t n = -(uintptr_t)p1 % sizeof(op_t);
> +  for (int i = 0; i < n; ++i)
>      {
> -      c1 = (unsigned char) *s1++;
> -      c2 = (unsigned char) *s2++;
> -      if (c1 == '\0')
> -       return c1 - c2;
> +      unsigned char c1 = *p1++;
> +      unsigned char c2 = *p2++;
> +      int diff = c1 - c2;
> +      if (c1 == '\0' || diff != 0)
> +       return diff;
>      }
> -  while (c1 == c2);
>
> -  return c1 - c2;
> +  /* P1 is now aligned to unsigned long.  P2 may or may not be.  */
> +  const op_t *x1 = (const op_t *) p1;
> +  op_t w1 = *x1++;
> +  uintptr_t ofs = (uintptr_t) p2 % sizeof(op_t);
> +  return ofs == 0
> +    ? strcmp_aligned_loop (x1, (const op_t *)p2, w1)
> +    : strcmp_unaligned_loop (x1, (const op_t *)(p2 - ofs), w1, ofs);
>  }
> +#ifndef STRCMP
>  libc_hidden_builtin_def (strcmp)
> +#endif
> --
> 2.34.1
>