From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 878 invoked by alias); 5 Sep 2018 08:31:38 -0000 Mailing-List: contact newlib-cvs-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: newlib-cvs-owner@sourceware.org Received: (qmail 57129 invoked by uid 9078); 5 Sep 2018 08:25:51 -0000 Date: Wed, 05 Sep 2018 08:31:00 -0000 Message-ID: <20180905082551.57126.qmail@sourceware.org> Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Corinna Vinschen To: newlib-cvs@sourceware.org Subject: [newlib-cygwin] Improve strstr performance of short needles X-Act-Checkin: newlib-cygwin X-Git-Author: Wilco Dijkstra X-Git-Refname: refs/heads/master X-Git-Oldrev: 86c31ae47b1a17e8d79968af2874b2a89b4326c5 X-Git-Newrev: 6dbb20dfc7916b97e0a7067fd426669739372808 X-SW-Source: 2018-q3/txt/msg00113.txt.bz2 https://sourceware.org/git/gitweb.cgi?p=newlib-cygwin.git;h=6dbb20dfc7916b97e0a7067fd426669739372808 commit 6dbb20dfc7916b97e0a7067fd426669739372808 Author: Wilco Dijkstra 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 -#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). */