From patchwork Wed Sep 5 13:38:22 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wilco Dijkstra X-Patchwork-Id: 966396 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=sourceware.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=libc-alpha-return-95682-incoming=patchwork.ozlabs.org@sourceware.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=arm.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.b="BFUq/YKH"; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=armh.onmicrosoft.com header.i=@armh.onmicrosoft.com header.b="R3b64Psf"; dkim-atps=neutral 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 4254Xq1qw9z9sCf for ; Wed, 5 Sep 2018 23:38:35 +1000 (AEST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:cc:subject:date:message-id :content-type:content-transfer-encoding:mime-version; q=dns; s= default; b=cND8VbdMUTcuNdyJAq1l8yIeOHXyeIIWdPsNNg7zJNkyFLYct2q+f MwYSzHxhghKEOuP1X6jEuXhO/pLyEwxgwu14eE+CL7yMBaR8DC4o1suL8qO3XuAj TQw4zzAex834AHfsjdKTP2akL6EUdr/M0pJAOrGJCcXn9qp9z/XtW4= 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:from:to:cc:subject:date:message-id :content-type:content-transfer-encoding:mime-version; s=default; bh=symeDnpe5MmOEL67WrKLFyvNe/I=; b=BFUq/YKHYCnRNkm31VuKqJ1m/tnM 5sX94YVgZLs1w1LoqmL3HY22buJUHhyz8mZzihxAnjnCenDsFtcDu2PWZbYmHtq9 a9jw/SEzsY5mtUsCjSEfCGgwG76WQ2K5gxiAXW3EZ6utP3X7mqVL+oHUtNGPgcTv Jt4F229YMCHJms8= Received: (qmail 78107 invoked by alias); 5 Sep 2018 13:38:28 -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 78080 invoked by uid 89); 5 Sep 2018 13:38:27 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_HELO_PASS, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: EUR04-VI1-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=BAGMxDXNgiOAvbtPXNyeb5k7ySMIa9xqLUwLaVTtD18=; b=R3b64PsfnEr7dFHOk7ae0jJX4H3XQwvS1xSx+YbY9i45JKhkS9GGfURpaQZnoNmp5Tt33XoPW4UzXTODzFqOy+7kjDksGAmeMinCnP08uEcJIaTD6iSqJdRh2w093huvJIwbcGY5kDfUYRbh/tIoc4rmn6ZjgZ+kcAhuP12igIA= From: Wilco Dijkstra To: "libc-alpha@sourceware.org" CC: nd Subject: [PATCH] Improve strstr performance of short needles Date: Wed, 5 Sep 2018 13:38:22 +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 Improve strstr performance for the common case of short needles. For 2-4 characters a small loop is typically fastest. On large strings the speedup with a needle size of 4 is about 65%. Passes GLIBC regression tests. OK for commit? ChangeLog: 2018-09-05 Wilco Dijkstra * string/strstr.c (strstr2): Add new function. (strstr3): Likewise. (strstr3): Likewise. (STRSTR): Add special cases for short needles. Reviewed-by: Gabriel F. T. Gomes diff --git a/string/strstr.c b/string/strstr.c index 33acdc5442d3e9031298a56e4f52a19e2ffa7d84..dd8663494ef391f34f7ed0a961d6c0e399bfdda9 100644 --- a/string/strstr.c +++ b/string/strstr.c @@ -46,6 +46,50 @@ #define STRSTR strstr #endif + +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; +} + + /* Return the first occurrence of NEEDLE in HAYSTACK. Return HAYSTACK if NEEDLE is empty, otherwise NULL if NEEDLE is not found in HAYSTACK. */ @@ -64,6 +108,13 @@ STRSTR (const char *haystack, const char *needle) if (haystack == NULL || needle[1] == '\0') return (char *) haystack; + if (needle[2] == '\0') + return strstr2 (haystack, needle); + if (needle[3] == '\0') + return strstr3 (haystack, needle); + if (needle[4] == '\0') + return strstr4 (haystack, needle); + /* Ensure HAYSTACK length is at least as long as NEEDLE length. Since a match may occur early on in a huge HAYSTACK, use strnlen and read ahead a few cachelines for improved performance. */