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: =?utf-8?b?T25kxZllaiBCw61sa2E=?= X-Patchwork-Id: 471792 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4B512140664 for ; Wed, 13 May 2015 19:48:52 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=sourceware.org header.i=@sourceware.org header.b=cwMidBDb; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:date:from:to:subject:message-id:mime-version :content-type; q=dns; s=default; b=Qi/nYjs9XvWl8FnVMaW6DDj5uBczW eoohdZ9sthbKmYh7S4WD+m+vquKm5cKAb3EDTVIwQ2LHOQWDOihS09JL0v2qEzZY glA54wjQ4TsjrEzUhFeu1ZtBoLY0BVvrHIhVKiq+5atp187jA2LRCH/35uyDfqX3 juHAvK95vXFwPc= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:date:from:to:subject:message-id:mime-version :content-type; s=default; bh=kW2HtnD+dO89X1zd7dYgLRfiqs4=; b=cwM idBDbVknhU99B7hAmLOVJdgAP2D8NexOYxhmz9C1uW87tfnH/CKH7WkBclV/bl38 d19VAuYGHaEXq3Ly1zxirUqvDXdIxE+jSsSAIRnqbrpbLooBNmqUpwcjoPXYRlBP xhnadlvpmxyDMYRuzLWxHRDc7nP3ralpftmkmHA4= 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