This is the mail archive of the
glibc-cvs@sourceware.org
mailing list for the glibc project.
GNU C Library master sources branch master updated. glibc-2.27.9000-574-g3ae725d
- From: wilco at sourceware dot org
- To: glibc-cvs at sourceware dot org
- Date: 16 Jul 2018 16:55:45 -0000
- Subject: GNU C Library master sources branch master updated. glibc-2.27.9000-574-g3ae725d
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU C Library master sources".
The branch, master has been updated
via 3ae725dfb6d7f61447d27d00ed83e573bd5454f4 (commit)
from 31e422ca9680bbe412aa56b23f058c10eaee7be8 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
http://sourceware.org/git/gitweb.cgi?p=glibc.git;a=commitdiff;h=3ae725dfb6d7f61447d27d00ed83e573bd5454f4
commit 3ae725dfb6d7f61447d27d00ed83e573bd5454f4
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>
diff --git a/ChangeLog b/ChangeLog
index 89052e6..b921f90 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,16 @@
+2018-07-15 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.
+
2018-07-15 H.J. Lu <hongjiu.lu@intel.com>
* sysdeps/unix/sysv/linux/x86_64/____longjmp_chk.S: Undef
diff --git a/benchtests/bench-strcasestr.c b/benchtests/bench-strcasestr.c
index e6659ea..4337e0c 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 c30cd10..a31294e 100644
--- a/benchtests/bench-strstr.c
+++ b/benchtests/bench-strstr.c
@@ -23,6 +23,7 @@
#define STRSTR simple_strstr
#define libc_hidden_builtin_def(X)
+#define __strnlen strnlen
#include "../string/strstr.c"
diff --git a/string/memmem.c b/string/memmem.c
index c17e1cf..43efaa3 100644
--- a/string/memmem.c
+++ b/string/memmem.c
@@ -31,6 +31,7 @@
#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
diff --git a/string/str-two-way.h b/string/str-two-way.h
index cd26058..523d946 100644
--- a/string/str-two-way.h
+++ b/string/str-two-way.h
@@ -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))
diff --git a/string/strcasestr.c b/string/strcasestr.c
index 90ba189..5909fe3 100644
--- a/string/strcasestr.c
+++ b/string/strcasestr.c
@@ -37,8 +37,8 @@
/* 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)), 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)
diff --git a/string/strstr.c b/string/strstr.c
index b3b5deb..265e9f3 100644
--- a/string/strstr.c
+++ b/string/strstr.c
@@ -33,10 +33,11 @@
#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)), 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
diff --git a/string/test-strcasestr.c b/string/test-strcasestr.c
index 2b0a38e..9b1088d 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 acf6ff8..8d99716 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"
-----------------------------------------------------------------------
Summary of changes:
ChangeLog | 13 +++++++++
benchtests/bench-strcasestr.c | 1 +
benchtests/bench-strstr.c | 1 +
string/memmem.c | 1 +
string/str-two-way.h | 56 +++++++++++++++++++---------------------
string/strcasestr.c | 4 +-
string/strstr.c | 5 ++-
string/test-strcasestr.c | 1 +
string/test-strstr.c | 1 +
9 files changed, 50 insertions(+), 33 deletions(-)
hooks/post-receive
--
GNU C Library master sources