[PATCH] Improve strstr performance of short needles

[Wilco Dijkstra <Wilco dot Dijkstra at arm dot com>]

Improve strstr performance for the common case of short needles.  For 2-4 
characters a small loop is typically fastest.  On large strings the speedup
with a needle size of 4 is about 65%.

Passes GLIBC regression tests. OK for commit?

ChangeLog:
2018-09-05  Wilco Dijkstra  <wdijkstr@arm.com>

	* string/strstr.c (strstr2): Add new function.
	(strstr3): Likewise.
	(strstr3): Likewise.
	(STRSTR): Add special cases for short needles.

--

diff --git a/string/strstr.c b/string/strstr.c
index 33acdc5442d3e9031298a56e4f52a19e2ffa7d84..dd8663494ef391f34f7ed0a961d6c0e399bfdda9 100644
--- a/string/strstr.c
+++ b/string/strstr.c
@@ -46,6 +46,50 @@
 #define STRSTR strstr
 #endif
 
+
+static inline char *
+strstr2 (const char *hs, const char *ne)
+{
+  uint32_t h1 = (ne[0] << 16) | ne[1];
+  uint32_t h2 = 0;
+  int c = hs[0];
+  while (h1 != h2 && c != 0)
+    {
+      h2 = (h2 << 16) | c;
+      c = *++hs;
+    }
+  return h1 == h2 ? (char *)hs - 2 : NULL;
+}
+
+static inline char *
+strstr3 (const char *hs, const char *ne)
+{
+  uint32_t h1 = (ne[0] << 24) | (ne[1] << 16) | (ne[2] << 8);
+  uint32_t h2 = 0;
+  int c = hs[0];
+  while (h1 != h2 && c != 0)
+    {
+      h2 = (h2 | c) << 8;
+      c = *++hs;
+    }
+  return h1 == h2 ? (char *)hs - 3 : NULL;
+}
+
+static inline char *
+strstr4 (const char *hs, const char *ne)
+{
+  uint32_t h1 = (ne[0] << 24) | (ne[1] << 16) | (ne[2] << 8) | ne[3];
+  uint32_t h2 = 0;
+  int c = hs[0];
+  while (h1 != h2 && c != 0)
+    {
+      h2 = (h2 << 8) | c;
+      c = *++hs;
+    }
+  return h1 == h2 ? (char *)hs - 4 : NULL;
+}
+
+
 /* Return the first occurrence of NEEDLE in HAYSTACK.  Return HAYSTACK
    if NEEDLE is empty, otherwise NULL if NEEDLE is not found in
    HAYSTACK.  */
@@ -64,6 +108,13 @@ STRSTR (const char *haystack, const char *needle)
   if (haystack == NULL || needle[1] == '\0')
     return (char *) haystack;
 
+  if (needle[2] == '\0')
+    return strstr2 (haystack, needle);
+  if (needle[3] == '\0')
+    return strstr3 (haystack, needle);
+  if (needle[4] == '\0')
+    return strstr4 (haystack, needle);
+
   /* Ensure HAYSTACK length is at least as long as NEEDLE length.
      Since a match may occur early on in a huge HAYSTACK, use strnlen
      and read ahead a few cachelines for improved performance.  */