[PATCH 16/20] alpha: add vectorized single-char fast path for strspn
Adhemerval Zanella Netto
adhemerval.zanella@linaro.org
Wed Aug 12 20:05:06 GMT 2026
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)
More information about the Libc-alpha
mailing list