From patchwork Fri Jul 20 11:15:38 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wilco Dijkstra X-Patchwork-Id: 28525 Received: (qmail 73615 invoked by alias); 20 Jul 2018 11:16:09 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 73477 invoked by uid 89); 20 Jul 2018 11:16:04 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-25.3 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_HELO_PASS, SPF_PASS autolearn=unavailable version=3.3.2 spammy=needle, AVAILABLE X-HELO: EUR01-VE1-obe.outbound.protection.outlook.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector1-arm-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=Ou6cF3VJ19EIKOHz39dz0brLEkAIa605fOFJ4910IYA=; b=HN9Ot+JMGWsl4xscjC43YPlDDvvc6E2ncG8Y02QZktnmNMYUL+sPW+9KY6iljzgHo8WzfSSAit35ZMlTSktOoLa2PA7ySSfQEuTFMSNPqRNJDo8fhdYwJZmQqRUwnwHDCpcb7a0nsAXsuevYpTf3/1OlK5XkqwdbNzvaYV/+sh0= From: Wilco Dijkstra To: "libc-alpha@sourceware.org" CC: nd Subject: [PATCH] Simplify and speedup strstr/strcasestr first match Date: Fri, 20 Jul 2018 11:15:38 +0000 Message-ID: authentication-results: spf=none (sender IP is ) smtp.mailfrom=Wilco.Dijkstra@arm.com; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) MIME-Version: 1.0 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. This patch improves the time taken for the full strstr benchtest by ~40%. Passes GLIBC regression tests. ChangeLog: 2018-07-20 Wilco Dijkstra * string/strcasestr.c (STRCASESTR): Simplify and speedup first match. * string/strstr.c (AVAILABLE): Likewise. diff --git a/string/strcasestr.c b/string/strcasestr.c index 5909fe3cdba88e476c7a989a020f3611bbfeb1de..305ab1dc947c89a9a1cd4a1e4b66782ad39b2748 100644 --- a/string/strcasestr.c +++ b/string/strcasestr.c @@ -58,31 +58,20 @@ 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) + + /* Determine length of NEEDLE and handle empty NEEDLE special case. */ + if (needle[0] == '\0') + return (char *) haystack; + needle_len = strlen (needle); + + /* Ensure HAYSTACK length is at least as long as NEEDLE length. */ + 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 +79,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 265e9f310ce507ce63740cc42d8ceea1d28dab01..8526e863e39cee668069ec265e00aa3d1417d16c 100644 --- a/string/strstr.c +++ b/string/strstr.c @@ -50,33 +50,30 @@ if NEEDLE is empty, otherwise NULL if NEEDLE is not found in HAYSTACK. */ 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) + + /* Determine length of NEEDLE and handle empty NEEDLE special case. */ + if (needle[0] == '\0') + return (char *) haystack; + needle_len = strlen (needle); + + /* Skip until we find first matching char from NEEDLE. */ + haystack = strchr (haystack, needle[0]); + if (haystack == NULL || needle_len == 1) + return (char *) haystack; + + /* Ensure HAYSTACK length is at least as long as NEEDLE length. */ + haystack_len = __strnlen (haystack, needle_len + 256); + if (haystack_len < needle_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)) + + /* 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; - 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