public inbox for newlib-cvs@sourceware.org
help / color / mirror / Atom feed
* [newlib-cygwin] Improve strstr performance of short needles
@ 2018-09-05 8:31 Corinna Vinschen
0 siblings, 0 replies; only message in thread
From: Corinna Vinschen @ 2018-09-05 8:31 UTC (permalink / raw)
To: newlib-cvs
https://sourceware.org/git/gitweb.cgi?p=newlib-cygwin.git;h=6dbb20dfc7916b97e0a7067fd426669739372808
commit 6dbb20dfc7916b97e0a7067fd426669739372808
Author: Wilco Dijkstra <Wilco.Dijkstra@arm.com>
Date: Tue Sep 4 17:54:21 2018 +0000
Improve strstr performance of short needles
Improve strstr performance for the common case of short needles. For a single
character strchr is best, for 2-4 characters a small loop is fastest. For these
the speedup over the Two-Way algorithm is ~10 times on large strings.
Newlib builds, the new code passes GLIBC testsuite. OK for commit?
Diff:
---
newlib/libc/string/strstr.c | 75 +++++++++++++++++++++++++++++++++++++++------
1 file changed, 65 insertions(+), 10 deletions(-)
diff --git a/newlib/libc/string/strstr.c b/newlib/libc/string/strstr.c
index 580ad62..e72b4bd 100644
--- a/newlib/libc/string/strstr.c
+++ b/newlib/libc/string/strstr.c
@@ -30,20 +30,11 @@ QUICKREF
#include <string.h>
-#if !defined(PREFER_SIZE_OVER_SPEED) && !defined(__OPTIMIZE_SIZE__)
-# 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)))
-# include "str-two-way.h"
-#endif
-
+#if defined(PREFER_SIZE_OVER_SPEED) || defined(__OPTIMIZE_SIZE__)
char *
strstr (const char *searchee,
const char *lookfor)
{
-#if defined(PREFER_SIZE_OVER_SPEED) || defined(__OPTIMIZE_SIZE__)
-
/* Less code size, but quadratic performance in the worst case. */
if (*searchee == 0)
{
@@ -77,6 +68,58 @@ strstr (const char *searchee,
#else /* compilation for speed */
+# 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)))
+# include "str-two-way.h"
+
+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;
+}
+
+char *
+strstr (const char *searchee,
+ const char *lookfor)
+{
/* Larger code size, but guaranteed linear performance. */
const char *haystack = searchee;
const char *needle = lookfor;
@@ -84,6 +127,18 @@ strstr (const char *searchee,
size_t haystack_len; /* Known minimum length of HAYSTACK. */
int ok = 1; /* True if NEEDLE is prefix of HAYSTACK. */
+ /* Handle short needle special cases first. */
+ if (needle[0] == '\0')
+ return (char *) haystack;
+ if (needle[1] == '\0')
+ return strchr (haystack, needle[0]);
+ if (needle[2] == '\0')
+ return strstr2 (haystack, needle);
+ if (needle[3] == '\0')
+ return strstr3 (haystack, needle);
+ if (needle[4] == '\0')
+ return strstr4 (haystack, needle);
+
/* 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). */
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2018-09-05 8:31 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-09-05 8:31 [newlib-cygwin] Improve strstr performance of short needles Corinna Vinschen
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).