[Support] Add fast path for StringRef::find with needle of length 2.

[ishitatsuyuki]

Summary

InclusionRewriter on Windows (CRLF line endings) will exercise this in a
hot path. Calling memcmp repeatedly would be highly suboptimal for that
use case, so give it a specialized path.

[ishitatsuyuki]

(Carried over from D133658)

A note that the N=2 search code is mostly mirrored from glibc; I believe it's short enough to not cause copyright issues but please let me know if I should be more defensive here.

https://codebrowser.dev/glibc/glibc/string/memmem.c.html#70

[efriedma]

llvm/lib/Support/StringRef.cpp

165

How does this compare to just the following?

do {
  if (std::memcmp(Start, Needle, 2) == 0)
    return Start - Data;
  ++Start;
} while (Start < Stop);
return npos;

Much easier to read, and the performance is probably competitive.

[ishitatsuyuki]

Use a simplified implementation for clarity.

[ishitatsuyuki]

llvm/lib/Support/StringRef.cpp

165

Thanks, memcmp is not as fast (always loads the Needle in the loop and loads 2 byte of Start instead of 1) but it should still provide sufficient benefit from inline expansion, so I've adopted the strategy.

[efriedma]

LGTM

llvm/lib/Support/StringRef.cpp

179

As a future optimization, we could also look at making StringRef::count cache BadCharSkip.

[ishitatsuyuki]

I don’t have commit rights, so can anyone commit this and https://reviews.llvm.org/D133658?

[ishitatsuyuki]

Ping, can anyone commit this?

llvm/lib/Support/StringRef.cpp

if (Size < N)
     return npos;
   if (N == 1) {
     const char *Ptr = (const char *)::memchr(Start, Needle[0], Size);
     return Ptr == nullptr ? npos : Ptr - Data;
   }
 
   const char *Stop = Start + (Size - N + 1);
 
+  if (N == 2) {
+    // Provide a fast path for newline finding (CRLF case) in InclusionRewriter.
+    // This is basically a naive search with a little bit twiddling.
+
+    // In theory we could use uint16_t, but some architectures don't support
+    // 16-bit arithmetic and will require a (& 65535) after the bit operations.
+    // Using 32-bit arithmetic with a shift of 16 would be more efficient for
+    // those cases.
+    uint32_t NeedleWord =
+        (uint32_t)(uint8_t)Needle[0] << 16 | (uint8_t)Needle[1];
+    uint32_t HaystackWord =
+        (uint32_t)(uint8_t)Start[0] << 16 | (uint8_t)Start[1];
+    for (Start++; Start < Stop && NeedleWord != HaystackWord;)
+      HaystackWord = HaystackWord << 16 | (uint8_t) * ++Start;
+    return NeedleWord == HaystackWord ? Start - Data - 1 : npos;
+  }
+
   // For short haystacks or unsupported needles fall back to the naive algorithm
   if (Size < 16 || N > 255) {
     do {
       if (std::memcmp(Start, Needle, N) == 0)
         return Start - Data;
       ++Start;
     } while (Start < Stop);
     return npos;
   }
 
   // Build the bad char heuristic table, with uint8_t to reduce cache thrashing.
   uint8_t BadCharSkip[256];
   std::memset(BadCharSkip, N, 256);
   for (unsigned i = 0; i != N-1; ++i)
     BadCharSkip[(uint8_t)Str[i]] = N-1-i;
 
   do {
     uint8_t Last = Start[N - 1];
     if (LLVM_UNLIKELY(Last == (uint8_t)Needle[N - 1]))
       if (std::memcmp(Start, Needle, N - 1) == 0)