public inbox for libc-stable@sourceware.org
 help / color / mirror / Atom feed
* [2.26 COMMITTED] Backport strstr/memmem performance improvements
@ 2019-01-01  0:00 Wilco Dijkstra
  0 siblings, 0 replies; only message in thread
From: Wilco Dijkstra @ 2019-01-01  0:00 UTC (permalink / raw)
  To: libc-stable; +Cc: nd

[-- Attachment #1: Type: text/plain, Size: 6252 bytes --]

commit 612fba2fe9036732c5ee08f691c52365e5bd32c0
Author: Wilco Dijkstra <wdijkstr@arm.com>
Date:   Wed Jun 12 11:42:34 2019 +0100

    Improve performance of memmem
    
    This patch significantly improves performance of memmem using a novel
    modified Horspool algorithm.  Needles up to size 256 use a bad-character
    table indexed by hashed pairs of characters to quickly skip past mismatches.
    Long needles use a self-adapting filtering step to avoid comparing the whole
    needle repeatedly.
    
    By limiting the needle length to 256, the shift table only requires 8 bits
    per entry, lowering preprocessing overhead and minimizing cache effects.
    This limit also implies worst-case performance is linear.
    
    Small needles up to size 2 use a dedicated linear search.  Very long needles
    use the Two-Way algorithm (to avoid increasing stack size or slowing down
    the common case, inlining is disabled).
    
    The performance gain is 6.6 times on English text on AArch64 using random
    needles with average size 8.
    
    Tested against GLIBC testsuite and randomized tests.
    
    Reviewed-by: Szabolcs Nagy <szabolcs.nagy@arm.com>
    
        * string/memmem.c (__memmem): Rewrite to improve performance.
    
    (cherry picked from commit 680942b0167715e123d934b609060cd382f8e39f)

commit 796c5ee030deac07ed846d9531c1322d57c0a6c7
Author: Wilco Dijkstra <wdijkstr@arm.com>
Date:   Wed Jun 12 11:38:52 2019 +0100

    Improve performance of strstr
    
    This patch significantly improves performance of strstr using a novel
    modified Horspool algorithm.  Needles up to size 256 use a bad-character
    table indexed by hashed pairs of characters to quickly skip past mismatches.
    Long needles use a self-adapting filtering step to avoid comparing the whole
    needle repeatedly.
    
    By limiting the needle length to 256, the shift table only requires 8 bits
    per entry, lowering preprocessing overhead and minimizing cache effects.
    This limit also implies worst-case performance is linear.
    
    Small needles up to size 3 use a dedicated linear search.  Very long needles
    use the Two-Way algorithm.
    
    The performance gain using the improved bench-strstr on Cortex-A72 is 5.8
    times basic_strstr and 3.7 times twoway_strstr.
    
    Tested against GLIBC testsuite, randomized tests and the GNULIB strstr test
    (https://git.savannah.gnu.org/cgit/gnulib.git/tree/tests/test-strstr.c).
    
    Reviewed-by: Szabolcs Nagy <szabolcs.nagy@arm.com>
    
        * string/str-two-way.h (two_way_short_needle): Add inline to avoid
        warning.
        (two_way_long_needle): Block inlining.
        * string/strstr.c (strstr2): Add new function.
        (strstr3): Likewise.
        (STRSTR): Completely rewrite strstr to improve performance.
    
    (cherry picked from commit 5e0a7ecb6629461b28adc1a5aabcc0ede122f201)

commit cd3487afa276f817749d3a418e81849130e2dbce
Author: Wilco Dijkstra <wdijkstr@arm.com>
Date:   Wed Sep 19 16:50:18 2018 +0100

    Fix strstr bug with huge needles (bug 23637)
    
    The generic strstr in GLIBC 2.28 fails to match huge needles.  The optimized
    AVAILABLE macro reads ahead a large fixed amount to reduce the overhead of
    repeatedly checking for the end of the string.  However if the needle length
    is larger than this, two_way_long_needle may confuse this as meaning the end
    of the string and return NULL.  This is fixed by adding the needle length to
    the amount to read ahead.
    
        [BZ #23637]
        * string/test-strstr.c (pr23637): New function.
        (test_main): Add tests with longer needles.
        * string/strcasestr.c (AVAILABLE): Fix readahead distance.
        * string/strstr.c (AVAILABLE): Likewise.
    
    (cherry picked from commit 83a552b0bb9fc2a5e80a0ab3723c0a80ce1db9f2)

commit ceeba1d73c84f1a551677149ce3b3ed3372fb3ec
Author: Rajalakshmi Srinivasaraghavan <raji@linux.vnet.ibm.com>
Date:   Tue Aug 28 12:42:19 2018 +0530

    Speedup first memmem match
    
    As done in commit 284f42bc778e487dfd5dff5c01959f93b9e0c4f5, memcmp
    can be used after memchr to avoid the initialization overhead of the
    two-way algorithm for the first match.  This has shown improvement
    >40% for first match.
    
    (cherry picked from commit c8dd67e7c958de04c3783cbea7c384431707b5f8)

commit c60bf879b21aefedaf632f585b9c39af8532bc71
Author: Wilco Dijkstra <wdijkstr@arm.com>
Date:   Fri Aug 3 17:24:12 2018 +0100

    Simplify and speedup strstr/strcasestr first match
    
    Looking at the benchtests, both strstr and strcasestr spend a lot of time
    in a slow initialization loop handling one character per iteration.
    This can be simplified and use the much faster strlen/strnlen/strchr/memcmp.
    Read ahead a few cachelines to reduce the number of strnlen calls, which
    improves performance by ~3-4%.  This patch improves the time taken for the
    full strstr benchtest by >40%.
    
        * string/strcasestr.c (STRCASESTR): Simplify and speedup first match.
        * string/strstr.c (AVAILABLE): Likewise.
    
    (cherry picked from commit 284f42bc778e487dfd5dff5c01959f93b9e0c4f5)

commit 55a280689e61cb8a7879ebbe0586d031559f1ba4
Author: Wilco Dijkstra <wdijkstr@arm.com>
Date:   Mon Jul 16 17:50:09 2018 +0100

    Improve strstr performance
    
    Improve strstr performance.  Strstr tends to be slow because it uses
    many calls to memchr and a slow byte loop to scan for the next match.
    Performance is significantly improved by using strnlen on larger blocks
    and using strchr to search for the next matching character.  strcasestr
    can also use strnlen to scan ahead, and memmem can use memchr to check
    for the next match.
    
    On the GLIBC bench tests the performance gains on Cortex-A72 are:
    strstr: +25%
    strcasestr: +4.3%
    memmem: +18%
    
    On a 256KB dataset strstr performance improves by 67%, strcasestr by 47%.
    
        Reviewd-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
    
    (cherry picked from commit 3ae725dfb6d7f61447d27d00ed83e573bd5454f4)

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: strstr4.patch --]
[-- Type: text/x-patch; name="strstr4.patch", Size: 23896 bytes --]

diff --git a/ChangeLog b/ChangeLog
index 2a9b6ed..5f3df32 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,4 +1,47 @@
-2019-01-09  Wilco Dijkstra  <wdijkstr@arm.com>
+2019-09-13  Wilco Dijkstra  <wdijkstr@arm.com>
+
+	* string/memmem.c (__memmem): Rewrite to improve performance.
+
+2019-06-12  Wilco Dijkstra  <wdijkstr@arm.com>
+
+	* string/str-two-way.h (two_way_short_needle): Add inline to avoid
+	warning.
+	(two_way_long_needle): Block inlining.
+	* string/strstr.c (strstr2): Add new function.
+	(strstr3): Likewise.
+	(STRSTR): Completely rewrite strstr to improve performance.
+
+2019-09-13  Wilco Dijkstra  <wdijkstr@arm.com>
+
+	[BZ #23637]
+	* string/test-strstr.c (pr23637): New function.
+	(test_main): Add tests with longer needles.
+	* string/strcasestr.c (AVAILABLE): Fix readahead distance.
+	* string/strstr.c (AVAILABLE): Likewise.
+
+2019-09-13  Rajalakshmi Srinivasaraghavan  <raji@linux.vnet.ibm.com>
+
+	* string/memmem.c: Use memcmp for first match.
+
+2019-09-13  Wilco Dijkstra  <wdijkstr@arm.com>
+
+	* string/strcasestr.c (STRCASESTR): Simplify and speedup first match.
+	* string/strstr.c (AVAILABLE): Likewise.
+
+2019-09-13  Wilco Dijkstra  <wdijkstr@arm.com>
+
+	* benchtests/bench-strcasestr.c: Rename __strnlen to strnlen.
+	* benchtests/bench-strstr.c: Likewise.
+	* string/memmem.c (FASTSEARCH): Define.
+	* string/str-two-way.h (two_way_short_needle): Minor cleanups.
+	Add support for FASTSEARCH.
+	* string/strcasestr.c (AVAILABLE): Use read-ahead __strnlen.
+	* string/strstr.c (AVAILABLE): Use read-ahead __strnlen.
+	(FASTSEARCH): Define.
+	* string/test-strcasestr.c: Rename __strnlen to strnlen.
+	* string/test-strstr.c: Likewise.
+
+2019-09-06  Wilco Dijkstra  <wdijkstr@arm.com>
 
 	* manual/tunables.texi (glibc.cpu.name): Add ares tunable.
 	* sysdeps/aarch64/multiarch/memcpy.c (__libc_memcpy): Use
diff --git a/benchtests/bench-strcasestr.c b/benchtests/bench-strcasestr.c
index 4e6f480..9a031b3 100644
--- a/benchtests/bench-strcasestr.c
+++ b/benchtests/bench-strcasestr.c
@@ -24,6 +24,7 @@
 #define STRCASESTR simple_strcasestr
 #define NO_ALIAS
 #define __strncasecmp strncasecmp
+#define __strnlen strnlen
 #include "../string/strcasestr.c"
 
 
diff --git a/benchtests/bench-strstr.c b/benchtests/bench-strstr.c
index e63659f..2fa6411 100644
--- a/benchtests/bench-strstr.c
+++ b/benchtests/bench-strstr.c
@@ -22,6 +22,9 @@
 
 
 #define STRSTR simple_strstr
+#undef libc_hidden_builtin_def
+#define libc_hidden_builtin_def(X)
+#define __strnlen strnlen
 #include "../string/strstr.c"
 
 
diff --git a/string/memmem.c b/string/memmem.c
index 54fca49..fba7fe3 100644
--- a/string/memmem.c
+++ b/string/memmem.c
@@ -15,67 +15,115 @@
    License along with the GNU C Library; if not, see
    <http://www.gnu.org/licenses/>.  */
 
-/* This particular implementation was written by Eric Blake, 2008.  */
-
 #ifndef _LIBC
 # include <config.h>
 #endif
 
-/* Specification of memmem.  */
 #include <string.h>
 
 #ifndef _LIBC
-# define __builtin_expect(expr, val)   (expr)
 # define __memmem	memmem
 #endif
 
 #define RETURN_TYPE void *
 #define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l))
+#define FASTSEARCH(S,C,N) (void*) memchr ((void *)(S), (C), (N))
 #include "str-two-way.h"
 
 #undef memmem
 
-/* Return the first occurrence of NEEDLE in HAYSTACK.  Return HAYSTACK
-   if NEEDLE_LEN is 0, otherwise NULL if NEEDLE is not found in
-   HAYSTACK.  */
+/* Hash character pairs so a small shift table can be used.  All bits of
+   p[0] are included, but not all bits from p[-1].  So if two equal hashes
+   match on p[-1], p[0] matches too.  Hash collisions are harmless and result
+   in smaller shifts.  */
+#define hash2(p) (((size_t)(p)[0] - ((size_t)(p)[-1] << 3)) % sizeof (shift))
+
+/* Fast memmem algorithm with guaranteed linear-time performance.
+   Small needles up to size 2 use a dedicated linear search.  Longer needles
+   up to size 256 use a novel modified Horspool algorithm.  It hashes pairs
+   of characters to quickly skip past mismatches.  The main search loop only
+   exits if the last 2 characters match, avoiding unnecessary calls to memcmp
+   and allowing for a larger skip if there is no match.  A self-adapting
+   filtering check is used to quickly detect mismatches in long needles.
+   By limiting the needle length to 256, the shift table can be reduced to 8
+   bits per entry, lowering preprocessing overhead and minimizing cache effects.
+   The limit also implies worst-case performance is linear.
+   Needles larger than 256 characters use the linear-time Two-Way algorithm.  */
 void *
-__memmem (const void *haystack_start, size_t haystack_len,
-	  const void *needle_start, size_t needle_len)
+__memmem (const void *haystack, size_t hs_len,
+	  const void *needle, size_t ne_len)
 {
-  /* Abstract memory is considered to be an array of 'unsigned char' values,
-     not an array of 'char' values.  See ISO C 99 section 6.2.6.1.  */
-  const unsigned char *haystack = (const unsigned char *) haystack_start;
-  const unsigned char *needle = (const unsigned char *) needle_start;
-
-  if (needle_len == 0)
-    /* The first occurrence of the empty string is deemed to occur at
-       the beginning of the string.  */
-    return (void *) haystack;
-
-  /* Sanity check, otherwise the loop might search through the whole
-     memory.  */
-  if (__glibc_unlikely (haystack_len < needle_len))
+  const unsigned char *hs = (const unsigned char *) haystack;
+  const unsigned char *ne = (const unsigned char *) needle;
+
+  if (ne_len == 0)
+    return (void *) hs;
+  if (ne_len == 1)
+    return (void *) memchr (hs, ne[0], hs_len);
+
+  /* Ensure haystack length is >= needle length.  */
+  if (hs_len < ne_len)
     return NULL;
 
-  /* Use optimizations in memchr when possible, to reduce the search
-     size of haystack using a linear algorithm with a smaller
-     coefficient.  However, avoid memchr for long needles, since we
-     can often achieve sublinear performance.  */
-  if (needle_len < LONG_NEEDLE_THRESHOLD)
+  const unsigned char *end = hs + hs_len - ne_len;
+
+  if (ne_len == 2)
+    {
+      uint32_t nw = ne[0] << 16 | ne[1], hw = hs[0] << 16 | hs[1];
+      for (hs++; hs <= end && hw != nw; )
+	hw = hw << 16 | *++hs;
+      return hw == nw ? (void *)hs - 1 : NULL;
+    }
+
+  /* Use Two-Way algorithm for very long needles.  */
+  if (__builtin_expect (ne_len > 256, 0))
+    return two_way_long_needle (hs, hs_len, ne, ne_len);
+
+  uint8_t shift[256];
+  size_t tmp, shift1;
+  size_t m1 = ne_len - 1;
+  size_t offset = 0;
+
+  memset (shift, 0, sizeof (shift));
+  for (int i = 1; i < m1; i++)
+    shift[hash2 (ne + i)] = i;
+  /* Shift1 is the amount we can skip after matching the hash of the
+     needle end but not the full needle.  */
+  shift1 = m1 - shift[hash2 (ne + m1)];
+  shift[hash2 (ne + m1)] = m1;
+
+  for ( ; hs <= end; )
     {
-      haystack = memchr (haystack, *needle, haystack_len);
-      if (!haystack || __builtin_expect (needle_len == 1, 0))
-	return (void *) haystack;
-      haystack_len -= haystack - (const unsigned char *) haystack_start;
-      if (haystack_len < needle_len)
-	return NULL;
-      return two_way_short_needle (haystack, haystack_len, needle, needle_len);
+      /* Skip past character pairs not in the needle.  */
+      do
+	{
+	  hs += m1;
+	  tmp = shift[hash2 (hs)];
+	}
+      while (tmp == 0 && hs <= end);
+
+      /* If the match is not at the end of the needle, shift to the end
+	 and continue until we match the hash of the needle end.  */
+      hs -= tmp;
+      if (tmp < m1)
+	continue;
+
+      /* Hash of the last 2 characters matches.  If the needle is long,
+	 try to quickly filter out mismatches.  */
+      if (m1 < 15 || memcmp (hs + offset, ne + offset, 8) == 0)
+	{
+	  if (memcmp (hs, ne, m1) == 0)
+	    return (void *) hs;
+
+	  /* Adjust filter offset when it doesn't find the mismatch.  */
+	  offset = (offset >= 8 ? offset : m1) - 8;
+	}
+
+      /* Skip based on matching the hash of the needle end.  */
+      hs += shift1;
     }
-  else
-    return two_way_long_needle (haystack, haystack_len, needle, needle_len);
+  return NULL;
 }
 libc_hidden_def (__memmem)
 weak_alias (__memmem, memmem)
 libc_hidden_weak (memmem)
-
-#undef LONG_NEEDLE_THRESHOLD
diff --git a/string/str-two-way.h b/string/str-two-way.h
index 599c867..30aca30 100644
--- a/string/str-two-way.h
+++ b/string/str-two-way.h
@@ -221,7 +221,7 @@ critical_factorization (const unsigned char *needle, size_t needle_len,
    most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.
    If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
    HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.  */
-static RETURN_TYPE
+static inline RETURN_TYPE
 two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
 		      const unsigned char *needle, size_t needle_len)
 {
@@ -281,50 +281,50 @@ two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
     }
   else
     {
-      const unsigned char *phaystack = &haystack[suffix];
+      const unsigned char *phaystack;
       /* The comparison always starts from needle[suffix], so cache it
 	 and use an optimized first-character loop.  */
       unsigned char needle_suffix = CANON_ELEMENT (needle[suffix]);
 
-#if CHECK_EOL
-      /* We start matching from the SUFFIX'th element, so make sure we
-	 don't hit '\0' before that.  */
-      if (haystack_len < suffix + 1
-	  && !AVAILABLE (haystack, haystack_len, 0, suffix + 1))
-	return NULL;
-#endif
-
       /* The two halves of needle are distinct; no extra memory is
 	 required, and any mismatch results in a maximal shift.  */
       period = MAX (suffix, needle_len - suffix) + 1;
       j = 0;
-      while (1
-#if !CHECK_EOL
-	     && AVAILABLE (haystack, haystack_len, j, needle_len)
-#endif
-	     )
+      while (AVAILABLE (haystack, haystack_len, j, needle_len))
 	{
 	  unsigned char haystack_char;
 	  const unsigned char *pneedle;
 
-	  /* TODO: The first-character loop can be sped up by adapting
-	     longword-at-a-time implementation of memchr/strchr.  */
-	  if (needle_suffix
+	  phaystack = &haystack[suffix + j];
+
+#ifdef FASTSEARCH
+	  if (*phaystack++ != needle_suffix)
+	    {
+	      phaystack = FASTSEARCH (phaystack, needle_suffix,
+				      haystack_len - needle_len - j);
+	      if (phaystack == NULL)
+		goto ret0;
+	      j = phaystack - &haystack[suffix];
+	      phaystack++;
+	    }
+#else
+	  while (needle_suffix
 	      != (haystack_char = CANON_ELEMENT (*phaystack++)))
 	    {
 	      RET0_IF_0 (haystack_char);
-#if !CHECK_EOL
+# if !CHECK_EOL
 	      ++j;
-#endif
-	      continue;
+	      if (!AVAILABLE (haystack, haystack_len, j, needle_len))
+		goto ret0;
+# endif
 	    }
 
-#if CHECK_EOL
+# if CHECK_EOL
 	  /* Calculate J if it wasn't kept up-to-date in the first-character
 	     loop.  */
 	  j = phaystack - &haystack[suffix] - 1;
+# endif
 #endif
-
 	  /* Scan for matches in right half.  */
 	  i = suffix + 1;
 	  pneedle = &needle[i];
@@ -338,6 +338,11 @@ two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
 		}
 	      ++i;
 	    }
+#if CHECK_EOL
+	  /* Update minimal length of haystack.  */
+	  if (phaystack > haystack + haystack_len)
+	    haystack_len = phaystack - haystack;
+#endif
 	  if (needle_len <= i)
 	    {
 	      /* Scan for matches in left half.  */
@@ -360,13 +365,6 @@ two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
 	    }
 	  else
 	    j += i - suffix + 1;
-
-#if CHECK_EOL
-	  if (!AVAILABLE (haystack, haystack_len, j, needle_len))
-	    break;
-#endif
-
-	  phaystack = &haystack[suffix + j];
 	}
     }
  ret0: __attribute__ ((unused))
@@ -384,8 +382,11 @@ two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
    and sublinear performance O(HAYSTACK_LEN / NEEDLE_LEN) is possible.
    If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
    HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching, and
-   sublinear performance is not possible.  */
-static RETURN_TYPE
+   sublinear performance is not possible.
+
+   Since this function is large and complex, block inlining to avoid
+   slowing down the common case of small needles.  */
+__attribute__((noinline)) static RETURN_TYPE
 two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
 		     const unsigned char *needle, size_t needle_len)
 {
diff --git a/string/strcasestr.c b/string/strcasestr.c
index 2acf003..19ea1d4 100644
--- a/string/strcasestr.c
+++ b/string/strcasestr.c
@@ -37,8 +37,9 @@
 /* Two-Way algorithm.  */
 #define RETURN_TYPE char *
 #define AVAILABLE(h, h_l, j, n_l)			\
-  (!memchr ((h) + (h_l), '\0', (j) + (n_l) - (h_l))	\
-   && ((h_l) = (j) + (n_l)))
+  (((j) + (n_l) <= (h_l)) \
+   || ((h_l) += __strnlen ((void*)((h) + (h_l)), (n_l) + 512), \
+       (j) + (n_l) <= (h_l)))
 #define CHECK_EOL (1)
 #define RET0_IF_0(a) if (!a) goto ret0
 #define CANON_ELEMENT(c) TOLOWER (c)
@@ -58,31 +59,22 @@
    case-insensitive comparison.  This function gives unspecified
    results in multibyte locales.  */
 char *
-STRCASESTR (const char *haystack_start, const char *needle_start)
+STRCASESTR (const char *haystack, const char *needle)
 {
-  const char *haystack = haystack_start;
-  const char *needle = needle_start;
   size_t needle_len; /* Length of NEEDLE.  */
   size_t haystack_len; /* Known minimum length of HAYSTACK.  */
-  bool ok = true; /* True if NEEDLE is prefix of HAYSTACK.  */
-
-  /* Determine length of NEEDLE, and in the process, make sure
-     HAYSTACK is at least as long (no point processing all of a long
-     NEEDLE if HAYSTACK is too short).  */
-  while (*haystack && *needle)
-    {
-      ok &= (TOLOWER ((unsigned char) *haystack)
-	     == TOLOWER ((unsigned char) *needle));
-      haystack++;
-      needle++;
-    }
-  if (*needle)
+
+  /* Handle empty NEEDLE special case.  */
+  if (needle[0] == '\0')
+    return (char *) haystack;
+
+  /* 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.  */
+  needle_len = strlen (needle);
+  haystack_len = __strnlen (haystack, needle_len + 256);
+  if (haystack_len < needle_len)
     return NULL;
-  if (ok)
-    return (char *) haystack_start;
-  needle_len = needle - needle_start;
-  haystack = haystack_start + 1;
-  haystack_len = needle_len - 1;
 
   /* Perform the search.  Abstract memory is considered to be an array
      of 'unsigned char' values, not an array of 'char' values.  See
@@ -90,10 +82,10 @@ STRCASESTR (const char *haystack_start, const char *needle_start)
   if (needle_len < LONG_NEEDLE_THRESHOLD)
     return two_way_short_needle ((const unsigned char *) haystack,
 				 haystack_len,
-				 (const unsigned char *) needle_start,
+				 (const unsigned char *) needle,
 				 needle_len);
   return two_way_long_needle ((const unsigned char *) haystack, haystack_len,
-			      (const unsigned char *) needle_start,
+			      (const unsigned char *) needle,
 			      needle_len);
 }
 
diff --git a/string/strstr.c b/string/strstr.c
index 88f1d5d..4d72ffb 100644
--- a/string/strstr.c
+++ b/string/strstr.c
@@ -16,27 +16,17 @@
    License along with the GNU C Library; if not, see
    <http://www.gnu.org/licenses/>.  */
 
-/* This particular implementation was written by Eric Blake, 2008.  */
-
 #ifndef _LIBC
 # include <config.h>
 #endif
 
-/* Specification of strstr.  */
 #include <string.h>
 
-#include <stdbool.h>
-
-#ifndef _LIBC
-# define __builtin_expect(expr, val)   (expr)
-#endif
-
 #define RETURN_TYPE char *
 #define AVAILABLE(h, h_l, j, n_l)			\
-  (!memchr ((h) + (h_l), '\0', (j) + (n_l) - (h_l))	\
-   && ((h_l) = (j) + (n_l)))
-#define CHECK_EOL (1)
-#define RET0_IF_0(a) if (!a) goto ret0
+  (((j) + (n_l) <= (h_l)) \
+   || ((h_l) += __strnlen ((void*)((h) + (h_l)), (n_l) + 512), \
+       (j) + (n_l) <= (h_l)))
 #include "str-two-way.h"
 
 #undef strstr
@@ -45,48 +35,128 @@
 #define STRSTR strstr
 #endif
 
-/* Return the first occurrence of NEEDLE in HAYSTACK.  Return HAYSTACK
-   if NEEDLE is empty, otherwise NULL if NEEDLE is not found in
-   HAYSTACK.  */
+static inline char *
+strstr2 (const unsigned char *hs, const unsigned char *ne)
+{
+  uint32_t h1 = (ne[0] << 16) | ne[1];
+  uint32_t h2 = 0;
+  for (int c = hs[0]; h1 != h2 && c != 0; c = *++hs)
+      h2 = (h2 << 16) | c;
+  return h1 == h2 ? (char *)hs - 2 : NULL;
+}
+
+static inline char *
+strstr3 (const unsigned char *hs, const unsigned char *ne)
+{
+  uint32_t h1 = ((uint32_t)ne[0] << 24) | (ne[1] << 16) | (ne[2] << 8);
+  uint32_t h2 = 0;
+  for (int c = hs[0]; h1 != h2 && c != 0; c = *++hs)
+      h2 = (h2 | c) << 8;
+  return h1 == h2 ? (char *)hs - 3 : NULL;
+}
+
+/* Hash character pairs so a small shift table can be used.  All bits of
+   p[0] are included, but not all bits from p[-1].  So if two equal hashes
+   match on p[-1], p[0] matches too.  Hash collisions are harmless and result
+   in smaller shifts.  */
+#define hash2(p) (((size_t)(p)[0] - ((size_t)(p)[-1] << 3)) % sizeof (shift))
+
+/* Fast strstr algorithm with guaranteed linear-time performance.
+   Small needles up to size 3 use a dedicated linear search.  Longer needles
+   up to size 256 use a novel modified Horspool algorithm.  It hashes pairs
+   of characters to quickly skip past mismatches.  The main search loop only
+   exits if the last 2 characters match, avoiding unnecessary calls to memcmp
+   and allowing for a larger skip if there is no match.  A self-adapting
+   filtering check is used to quickly detect mismatches in long needles.
+   By limiting the needle length to 256, the shift table can be reduced to 8
+   bits per entry, lowering preprocessing overhead and minimizing cache effects.
+   The limit also implies worst-case performance is linear.
+   Needles larger than 256 characters use the linear-time Two-Way algorithm.  */
 char *
-STRSTR (const char *haystack_start, const char *needle_start)
+STRSTR (const char *haystack, const char *needle)
 {
-  const char *haystack = haystack_start;
-  const char *needle = needle_start;
-  size_t needle_len; /* Length of NEEDLE.  */
-  size_t haystack_len; /* Known minimum length of HAYSTACK.  */
-  bool ok = true; /* True if NEEDLE is prefix of HAYSTACK.  */
-
-  /* Determine length of NEEDLE, and in the process, make sure
-     HAYSTACK is at least as long (no point processing all of a long
-     NEEDLE if HAYSTACK is too short).  */
-  while (*haystack && *needle)
-    ok &= *haystack++ == *needle++;
-  if (*needle)
+  const unsigned char *hs = (const unsigned char *) haystack;
+  const unsigned char *ne = (const unsigned char *) needle;
+
+  /* Handle short needle special cases first.  */
+  if (ne[0] == '\0')
+    return (char *)hs;
+  hs = (const unsigned char *)strchr ((const char*)hs, ne[0]);
+  if (hs == NULL || ne[1] == '\0')
+    return (char*)hs;
+  if (ne[2] == '\0')
+    return strstr2 (hs, ne);
+  if (ne[3] == '\0')
+    return strstr3 (hs, ne);
+
+  /* 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.  */
+  size_t ne_len = strlen ((const char*)ne);
+  size_t hs_len = __strnlen ((const char*)hs, ne_len | 512);
+  if (hs_len < ne_len)
     return NULL;
-  if (ok)
-    return (char *) haystack_start;
-
-  /* Reduce the size of haystack using strchr, since it has a smaller
-     linear coefficient than the Two-Way algorithm.  */
-  needle_len = needle - needle_start;
-  haystack = strchr (haystack_start + 1, *needle_start);
-  if (!haystack || __builtin_expect (needle_len == 1, 0))
-    return (char *) haystack;
-  needle -= needle_len;
-  haystack_len = (haystack > haystack_start + needle_len ? 1
-		  : needle_len + haystack_start - haystack);
-
-  /* Perform the search.  Abstract memory is considered to be an array
-     of 'unsigned char' values, not an array of 'char' values.  See
-     ISO C 99 section 6.2.6.1.  */
-  if (needle_len < LONG_NEEDLE_THRESHOLD)
-    return two_way_short_needle ((const unsigned char *) haystack,
-				 haystack_len,
-				 (const unsigned char *) needle, needle_len);
-  return two_way_long_needle ((const unsigned char *) haystack, haystack_len,
-			      (const unsigned char *) needle, needle_len);
+
+  /* Check whether we have a match.  This improves performance since we
+     avoid initialization overheads.  */
+  if (memcmp (hs, ne, ne_len) == 0)
+    return (char *) hs;
+
+  /* Use Two-Way algorithm for very long needles.  */
+  if (__glibc_unlikely (ne_len > 256))
+    return two_way_long_needle (hs, hs_len, ne, ne_len);
+
+  const unsigned char *end = hs + hs_len - ne_len;
+  uint8_t shift[256];
+  size_t tmp, shift1;
+  size_t m1 = ne_len - 1;
+  size_t offset = 0;
+
+  /* Initialize bad character shift hash table.  */
+  memset (shift, 0, sizeof (shift));
+  for (int i = 1; i < m1; i++)
+    shift[hash2 (ne + i)] = i;
+  /* Shift1 is the amount we can skip after matching the hash of the
+     needle end but not the full needle.  */
+  shift1 = m1 - shift[hash2 (ne + m1)];
+  shift[hash2 (ne + m1)] = m1;
+
+  while (1)
+    {
+      if (__glibc_unlikely (hs > end))
+	{
+	  end += __strnlen ((const char*)end + m1 + 1, 2048);
+	  if (hs > end)
+	    return NULL;
+	}
+
+      /* Skip past character pairs not in the needle.  */
+      do
+	{
+	  hs += m1;
+	  tmp = shift[hash2 (hs)];
+	}
+      while (tmp == 0 && hs <= end);
+
+      /* If the match is not at the end of the needle, shift to the end
+	 and continue until we match the hash of the needle end.  */
+      hs -= tmp;
+      if (tmp < m1)
+	continue;
+
+      /* Hash of the last 2 characters matches.  If the needle is long,
+	 try to quickly filter out mismatches.  */
+      if (m1 < 15 || memcmp (hs + offset, ne + offset, 8) == 0)
+	{
+	  if (memcmp (hs, ne, m1) == 0)
+	    return (void *) hs;
+
+	  /* Adjust filter offset when it doesn't find the mismatch.  */
+	  offset = (offset >= 8 ? offset : m1) - 8;
+	}
+
+      /* Skip based on matching the hash of the needle end.  */
+      hs += shift1;
+    }
 }
 libc_hidden_builtin_def (strstr)
-
-#undef LONG_NEEDLE_THRESHOLD
diff --git a/string/test-strcasestr.c b/string/test-strcasestr.c
index abb3916..78e03da 100644
--- a/string/test-strcasestr.c
+++ b/string/test-strcasestr.c
@@ -25,6 +25,7 @@
 #define STRCASESTR simple_strcasestr
 #define NO_ALIAS
 #define __strncasecmp strncasecmp
+#define __strnlen strnlen
 #include "strcasestr.c"
 
 
diff --git a/string/test-strstr.c b/string/test-strstr.c
index 33f2211..5bce73b 100644
--- a/string/test-strstr.c
+++ b/string/test-strstr.c
@@ -24,6 +24,7 @@
 
 #define STRSTR simple_strstr
 #define libc_hidden_builtin_def(arg) /* nothing */
+#define __strnlen strnlen
 #include "strstr.c"
 
 
@@ -150,6 +151,32 @@ check2 (void)
     }
 }
 
+#define N 1024
+
+static void
+pr23637 (void)
+{
+  char *h = (char*) buf1;
+  char *n = (char*) buf2;
+
+  for (int i = 0; i < N; i++)
+    {
+      n[i] = 'x';
+      h[i] = ' ';
+      h[i + N] = 'x';
+    }
+
+  n[N] = '\0';
+  h[N * 2] = '\0';
+
+  /* Ensure we don't match at the first 'x'.  */
+  h[0] = 'x';
+
+  char *exp_result = stupid_strstr (h, n);
+  FOR_EACH_IMPL (impl, 0)
+    check_result (impl, h, n, exp_result);
+}
+
 static int
 test_main (void)
 {
@@ -157,6 +184,7 @@ test_main (void)
 
   check1 ();
   check2 ();
+  pr23637 ();
 
   printf ("%23s", "");
   FOR_EACH_IMPL (impl, 0)
@@ -201,6 +229,9 @@ test_main (void)
 	do_test (15, 9, hlen, klen, 1);
 	do_test (15, 15, hlen, klen, 0);
 	do_test (15, 15, hlen, klen, 1);
+
+	do_test (15, 15, hlen + klen * 4, klen * 4, 0);
+	do_test (15, 15, hlen + klen * 4, klen * 4, 1);
       }
 
   do_test (0, 0, page_size - 1, 16, 0);

^ permalink raw reply	[flat|nested] only message in thread

only message in thread, other threads:[~2019-09-13 16:29 UTC | newest]

Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-01-01  0:00 [2.26 COMMITTED] Backport strstr/memmem performance improvements Wilco Dijkstra

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).