Re: [PATCH 16/20] alpha: add vectorized single-char fast path for strspn

On 11/08/26 22:19, Matt Turner wrote:
> The generic strspn's single-accept-char case was a byte-at-a-time scalar
> loop. Alpha has no hand-tuned strspn at all, so add one: the single-char
> case now scans a word at a time via cmpbge, finding the first byte that
> differs from the broadcast accept character (a NUL byte always differs
> from a non-NUL accept char, so this doubles as the string end check with
> no separate test). The multi-char case keeps the existing bitmap-table
> scan unchanged -- already efficient, nothing to gain there.
> 
> Measured on an EV68CB against the old scalar loop: 4.3x faster at 64B,
> 5.5-5.7x at 256B, ~6.8x at 4KB, ~7.7-7.8x at 64KB, converging toward the
> 8x ceiling the word width sets. Correctness verified against a reference
> scan at lengths 0 to 255 and all eight starting byte alignments,
> including runs that cross a word boundary and strings with a leading
> mismatch.

Why can't we optimize the generic implementation, instead of adding an
arch-specific code? Richard Henderson, Wilco, and myself have done a lot 
of optimization on generic code to avoid the need of such code.

The 'cmpbge' is already modeled by find_zero_ne_all (sysdeps/alpha/string-fza.h),
along with index_first (sysdeps/alpha/string-fzi.h) which will use cttz for
__alpha_cix__.

So we can expand the generic implementation as:

--
diff --git a/string/strspn.c b/string/strspn.c
index 9b90ae61e70..f01f9bbb32c 100644
--- a/string/strspn.c
+++ b/string/strspn.c
@@ -18,6 +18,9 @@
 #include <string.h>
 #include <stdint.h>
 #include <libc-pointer-arith.h>
+#include <string-fzc.h>
+#include <string-fzi.h>
+#include <string-shift.h>

 #undef strspn
 #ifndef STRSPN
@@ -33,9 +36,24 @@ STRSPN (const char *str, const char *accept)
     return 0;
   if (__glibc_unlikely (accept[1] == '\0'))
     {
-      const char *a = str;
-      for (; *str == *accept; str++);
-      return str - a;
+      /* Skip bytes equal to ACCEPT[0] one word at a time, stopping at the
+        first byte that differs from it.  */
+      uintptr_t s_int = (uintptr_t) str;
+      const op_t *word_ptr
+       = (const op_t *) PTR_ALIGN_DOWN (str, sizeof (op_t));
+      op_t repeated_c = repeat_bytes (accept[0]);
+
+      op_t word = *word_ptr;
+      find_t mask = shift_find (find_zero_ne_all (word, repeated_c), s_int);
+      if (mask != 0)
+       return index_first (mask);
+
+      do
+       word = *++word_ptr;
+      while (find_zero_ne_all (word, repeated_c) == 0);
+
+      return (const char *) word_ptr - str
+            + index_first_zero_ne (word, repeated_c);
     }

   /* Use multiple small memsets to enable inlining on most targets.  */
--

And this have the extra advantage of optimization not only alpha, but potentially
all other ABIs that uses the generic implementation.

> ---
>  sysdeps/alpha/strspn.c | 125 +++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 125 insertions(+)
>  create mode 100644 sysdeps/alpha/strspn.c
> 
> diff --git ./sysdeps/alpha/strspn.c ./sysdeps/alpha/strspn.c
> new file mode 100644
> index 0000000000..2ab11732a7
> --- /dev/null
> +++ ./sysdeps/alpha/strspn.c
> @@ -0,0 +1,125 @@
> +/* Copyright (C) 1991-2026 Free Software Foundation, Inc.
> +   This file is part of the GNU C Library.
> +
> +   The GNU C Library is free software; you can redistribute it and/or
> +   modify it under the terms of the GNU Lesser General Public
> +   License as published by the Free Software Foundation; either
> +   version 2.1 of the License, or (at your option) any later version.
> +
> +   The GNU C Library is distributed in the hope that it will be useful,
> +   but WITHOUT ANY WARRANTY; without even the implied warranty of
> +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> +   Lesser General Public License for more details.
> +
> +   You should have received a copy of the GNU Lesser General Public
> +   License along with the GNU C Library.  If not, see
> +   <https://www.gnu.org/licenses/>.  */
> +
> +#include <string.h>
> +#include <stdint.h>
> +#include <libc-pointer-arith.h>
> +
> +typedef unsigned long word;
> +
> +#define unlikely(X)	__builtin_expect ((X), 0)
> +
> +/* cmpbge(0, X) sets bit i iff byte i of X is zero.  For the single-char
> +   fast path we want the opposite -- the first byte that differs from the
> +   accept character -- so cmpbge(0, X ^ C) is inverted and masked to 8
> +   bits: bit i then set iff byte i of X differs from C.  */
> +#define cmpbeq0(X)	__builtin_alpha_cmpbge (0, (X))
> +#define diffmask(X, C)	((~cmpbeq0 ((X) ^ (C))) & 0xff)
> +
> +/* Return the length of the maximum initial segment
> +   of S which contains only characters in ACCEPT.  */
> +size_t
> +strspn (const char *str, const char *accept)
> +{
> +  if (accept[0] == '\0')
> +    return 0;
> +
> +  if (__glibc_unlikely (accept[1] == '\0'))
> +    {
> +      /* Single accept character: scan a word at a time for the first
> +	 byte that isn't it, rather than one byte per branch.  A NUL byte
> +	 always differs from a non-NUL accept char, so this naturally
> +	 stops at the end of the string with no separate check.  Measured
> +	 against libots' _OtsStringVerifyChar on an EV68CB: glibc's old
> +	 byte-at-a-time loop cost 2x at 8B, growing to ~14-15x by 4KB-64KB
> +	 runs, purely from one branch per byte versus one per word.  */
> +      const char *s = str;
> +      word t = (unsigned char) accept[0];
> +      t = (t << 8) | t;
> +      t = (t << 16) | t;
> +      const word c = (t << 32) | t;
> +
> +      const word *s_align = (const word *) ((word) s & -8);
> +      word current = *s_align;
> +      word mask = (1ul << ((word) s & 7)) - 1;
> +      word found = diffmask (current, c) & ~mask;
> +      if (unlikely (found))
> +	goto found_it;
> +
> +      for (;;)
> +	{
> +	  s_align++;
> +	  current = *s_align;
> +	  found = diffmask (current, c);
> +	  if (unlikely (found))
> +	    goto found_it;
> +	}
> +
> +    found_it:
> +#ifdef __alpha_cix__
> +      return ((word) s_align - (word) str) + 

 (found);
> +#else
> +      {
> +	word offset;
> +	found &= -found;
> +	offset  = (found & 0x0f ? 0 : 4);
> +	offset += (found & 0x33 ? 0 : 2);
> +	offset += (found & 0x55 ? 0 : 1);
> +	return ((word) s_align - (word) str) + offset;
> +      }
> +#endif
> +    }
> +
> +  /* General case: same bitmap-table scan as the generic implementation --
> +     already O(n) with no obvious win from vectorizing further here, and
> +     libots' equivalent multi-char path is an O(n*setlen) scalar scan that
> +     loses to this for any set beyond 1-2 characters, so there's nothing
> +     to take from it.  */
> +  unsigned char table[256];
> +  unsigned char *p = memset (table, 0, 64);
> +  memset (p + 64, 0, 64);
> +  memset (p + 128, 0, 64);
> +  memset (p + 192, 0, 64);
> +
> +  unsigned char *s = (unsigned char *) accept;
> +  do
> +    p[*s++] = 1;
> +  while (*s);
> +
> +  s = (unsigned char *) str;
> +  if (!p[s[0]]) return 0;
> +  if (!p[s[1]]) return 1;
> +  if (!p[s[2]]) return 2;
> +  if (!p[s[3]]) return 3;
> +
> +  s = (unsigned char *) PTR_ALIGN_DOWN (s, 4);
> +
> +  unsigned int c0, c1, c2, c3;
> +  do
> +    {
> +      s += 4;
> +      c0 = p[s[0]];
> +      c1 = p[s[1]];
> +      c2 = p[s[2]];
> +      c3 = p[s[3]];
> +    }
> +  while ((c0 & c1 & c2 & c3) != 0);
> +
> +  size_t count = s - (unsigned char *) str;
> +  return (c0 & c1) == 0 ? count + c0 : count + c2 + 2;
> +}
> +libc_hidden_builtin_def (strspn)