[PATCH 2/2] string: vectorize strspn single-accept-char case

[Matt Turner]

The single-accept-character fast path was a byte-at-a-time scalar loop.
Scan a word at a time instead, using find_ne_all () to locate the first
byte that differs from the broadcast accept character.  ACCEPT[0] is not
NUL there, so a NUL byte differs from it and the search for inequality
also stops at the end of the string.

The multi-character case keeps the existing bitmap-table scan.

Checked against strspn () for lengths 0 to 300 at every byte alignment,
with the run ended both by NUL and by a differing byte, on x86_64, s390x,
powerpc64, arm and alpha, covering the generic, cmpb, uqsub8 and cmpbge
string-fza.h implementations.  The riscv one was built but not run.

Speedup over the scalar loop it replaces, on an Alpha EV68 and on a Core
i7-1370P (which uses the generic C string-fza.h, and only reaches this
code where SSE4.2 is unavailable):

  length       8    32   128   512    2K    8K   32K
  Alpha EV68 1.4x  3.3x  4.5x  5.7x  6.4x  6.6x  6.6x
  i7-1370P   0.8x  1.6x  4.3x  3.6x  2.7x  2.8x  2.9x

Below 16 bytes on x86_64 the broadcast and the unaligned first word cost
more than the scalar loop, which the uniform benchmark input lets the
branch predictor run at nearly a byte per cycle; the loss there is under
half a nanosecond per call.
---
 string/strspn.c | 27 ++++++++++++++++++++++++---
 1 file changed, 24 insertions(+), 3 deletions(-)

diff --git ./string/strspn.c ./string/strspn.c
index 9b90ae61e7..2dea03704a 100644
--- ./string/strspn.c
+++ ./string/strspn.c
@@ -18,6 +18,10 @@
 #include <string.h>
 #include <stdint.h>
 #include <libc-pointer-arith.h>
+#include <string-fza.h>
+#include <string-fzc.h>
+#include <string-fzi.h>
+#include <string-shift.h>
 
 #undef strspn
 #ifndef STRSPN
@@ -33,9 +37,26 @@ 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 the bytes equal to ACCEPT[0] a word at a time.  ACCEPT[0] is
+	 not NUL here, so a NUL byte differs from it and the search for
+	 inequality also stops at the end of the string.  */
+      const uintptr_t s_int = (uintptr_t) str;
+      const op_t *word_ptr = (const op_t *) PTR_ALIGN_DOWN (str, sizeof (op_t));
+      const op_t repeated_c = repeat_bytes (accept[0]);
+
+      op_t word = *word_ptr;
+      find_t mask = shift_find (find_ne_all (word, repeated_c), s_int);
+      if (mask != 0)
+	return index_first (mask);
+
+      do
+	{
+	  word = *++word_ptr;
+	  mask = find_ne_all (word, repeated_c);
+	}
+      while (mask == 0);
+
+      return (const char *) word_ptr - str + index_first (mask);
     }
 
   /* Use multiple small memsets to enable inlining on most targets.  */
-- 
2.54.0