* [2.29 COMMITTED] Backport strstr/memmem performance improvements
[not found] <VI1PR0801MB2127CA167B297CD5876CD59F83B30@VI1PR0801MB2127.eurprd08.prod.outlook.com>
@ 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: 2954 bytes --]
commit 91372f000197deb148fbd6d6b5a8d93327119c3e
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 1ad15e008cca9a7189c26d756d20d07acf4855df
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)
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: strstr1.patch --]
[-- Type: text/x-patch; name="strstr1.patch", Size: 14812 bytes --]
diff --git a/ChangeLog b/ChangeLog
index 84acb52..8ba3545 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,16 @@
+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-03 Aurelien Jarno <aurelien@aurel32.net>
* sysdeps/alpha/fpu/libm-test-ulps: Regenerated using GCC 9.2.
diff --git a/string/memmem.c b/string/memmem.c
index 4bf733f..83ee75e 100644
--- a/string/memmem.c
+++ b/string/memmem.c
@@ -15,17 +15,13 @@
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
@@ -36,51 +32,98 @@
#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;
- /* Check whether we have a match. This improves performance since we
- avoid the initialization overhead of the two-way algorithm. */
- if (memcmp (haystack, needle, needle_len) == 0)
- return (void *) haystack;
- 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 b5011ba..f43c613 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)
{
@@ -382,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/strstr.c b/string/strstr.c
index 64e478b..408cce8 100644
--- a/string/strstr.c
+++ b/string/strstr.c
@@ -16,29 +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) \
(((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 FASTSEARCH(S,C,N) (void*) strchr ((void*)(S), (C))
#include "str-two-way.h"
#undef strstr
@@ -47,47 +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. */
-char *
-STRSTR (const char *haystack, const char *needle)
+static inline char *
+strstr2 (const unsigned char *hs, const unsigned char *ne)
{
- size_t needle_len; /* Length of NEEDLE. */
- size_t haystack_len; /* Known minimum length of HAYSTACK. */
-
- /* Handle empty NEEDLE special case. */
- if (needle[0] == '\0')
- return (char *) haystack;
+ 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;
+}
- /* Skip until we find the first matching char from NEEDLE. */
- haystack = strchr (haystack, needle[0]);
- if (haystack == NULL || needle[1] == '\0')
- return (char *) haystack;
+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;
+}
- /* Ensure HAYSTACK length is at least as long as NEEDLE length.
- Since a match may occur early on in a huge HAYSTACK, use strnlen
+/* 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, const char *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. */
- needle_len = strlen (needle);
- haystack_len = __strnlen (haystack, needle_len + 256);
- if (haystack_len < needle_len)
+ 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;
- /* Check whether we have a match. This improves performance since we avoid
- the initialization overhead of the two-way algorithm. */
- if (memcmp (haystack, needle, needle_len) == 0)
- return (char *) 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
^ permalink raw reply [flat|nested] only message in thread