[PATCH v2 3/3] 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 here, so a NUL byte differs from it and the search for inequality
also stops at the end of the string.

The word loop compares against the broadcast character directly rather
than building a mask each iteration, and calls find_ne_all () once at the
end.  Where find_ne_all () is an exclusive or the compiler already
generated this, but alpha builds the mask with cmpbge, and the comparison
halves its loop.

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

Checked against strspn () for lengths 0 to 300 at every byte alignment,
for several accept characters, with the run ended both by NUL and by a
differing byte.  Run on alpha (EV68CB), powerpc64 big-endian, 32-bit arm,
aarch64 and x86_64, covering the cmpbge, cmpb, uqsub8 and generic C
string-fza.h implementations.  The riscv ones were built but not run.

Speedup over the scalar loop it replaces:

  length        8    32   128   512    2K    8K   32K
  Alpha EV68  1.3x  3.3x  5.2x 11.7x 15.2x 16.4x 16.9x
  i7-1370P    1.9x  2.8x  5.5x  4.0x  5.2x  6.9x  7.6x

Both are the best of seven timed runs of each implementation, each run
calibrated to at least 0.3 s so that the millisecond clock granularity on
alpha does not quantize the result, and built with -falign-functions=64
so that code placement does not dominate the short lengths.  The i7-1370P
reaches this code only where SSE4.2 is unavailable, since the generic C
string-fza.h is what it would use there.

Suggested-by: Wilco Dijkstra <Wilco.Dijkstra@arm.com>
---
 string/strspn.c | 26 +++++++++++++++++++++++---
 1 file changed, 23 insertions(+), 3 deletions(-)

diff --git ./string/strspn.c ./string/strspn.c
index 9b90ae61e7..f8e869e176 100644
--- ./string/strspn.c
+++ ./string/strspn.c
@@ -18,6 +18,9 @@
 #include <string.h>
 #include <stdint.h>
 #include <libc-pointer-arith.h>
+#include <string-fza.h>
+#include <string-fzi.h>
+#include <string-shift.h>
 
 #undef strspn
 #ifndef STRSPN
@@ -33,9 +36,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);
+
+      /* Comparing the whole word is cheaper than building the mask on
+	 targets where find_ne_all () is more than an exclusive or.  */
+      do
+	word = *++word_ptr;
+      while (word == repeated_c);
+
+      return (const char *) word_ptr - str
+	     + index_first (find_ne_all (word, repeated_c));
     }
 
   /* Use multiple small memsets to enable inlining on most targets.  */
-- 
2.54.0