From patchwork Wed May 13 00:03:29 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ondrej Bilka X-Patchwork-Id: 6691 Received: (qmail 26894 invoked by alias); 13 May 2015 09:48:33 -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 26860 invoked by uid 89); 13 May 2015 09:48:32 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=1.4 required=5.0 tests=AWL, BAYES_50, DATE_IN_PAST_06_12, FREEMAIL_FROM, SPF_NEUTRAL autolearn=no version=3.3.2 X-HELO: popelka.ms.mff.cuni.cz Date: Wed, 13 May 2015 02:03:29 +0200 From: =?utf-8?B?T25kxZllaiBCw61sa2E=?= To: libc-alpha@sourceware.org Subject: [PATCH] Improve memmem. Message-ID: <20150513000329.GA23595@domone> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.20 (2009-06-14) Hi. This is same optimization for memmem as for strstr. On x64 memmem performance sucks as its order of magnitude slower than strstr. This equalizes performance somewhat and improves it in general case. OK to commit this? diff --git a/string/memmem.c b/string/memmem.c index 8a81f65..ed21ee4 100644 --- a/string/memmem.c +++ b/string/memmem.c @@ -46,6 +46,10 @@ __memmem (const void *haystack_start, size_t haystack_len, 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; + const unsigned char *haystack_end = (const unsigned char *) + haystack_start + haystack_len + - needle_len + 1; + if (needle_len == 0) /* The first occurrence of the empty string is deemed to occur at @@ -57,6 +61,29 @@ __memmem (const void *haystack_start, size_t haystack_len, if (__glibc_unlikely (haystack_len < needle_len)) return NULL; + if (needle_len == 1) + return memchr (haystack, needle[0], haystack_end - haystack); + + while ((haystack = memchr (haystack, needle[0], haystack_end - haystack))) + { + if (haystack[1] == needle[1] + && (needle_len == 2 || haystack[2] == needle[2])) + { + if (needle_len == 2) + return haystack; + + if (!memcmp (haystack + 2, needle + 2, needle_len - 2)) + return haystack; + else + goto slow_path; + } + haystack++; + } + + return NULL; + + slow_path:; + /* 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