From patchwork Thu Mar 21 16:19:36 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wilco Dijkstra X-Patchwork-Id: 1060264 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-100785-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="fowD/ybX"; dkim=pass (1024-bit key; unprotected) header.d=armh.onmicrosoft.com header.i=@armh.onmicrosoft.com header.b="qctMP3WC"; 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 44QBnv6zX0z9sRX for ; Fri, 22 Mar 2019 03:19:47 +1100 (AEDT) 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=fXkAKD39IfOwOQULI3oUCJAtnA7CM/CtgCjvFLx0Rw8X3YlYfNk7Z H6GN+gVEK1JjITFnkwDEepy/PP0953N1LAmgLrnhHaTqiKbvnOP8TC35/TI4ZHhT VZ1Chj6+hZe6cwIid7MIDnvjATfw/KsHpHKtJJt+mJ/sWL/HcC2bVI= 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=UQ/e603iNn6IE+sppm1G7sbdOfs=; b=fowD/ybXnPrOqg7N1n2kcjUx2/76 NrVPhP6l0SOWkokpDHdmUaZSiQrIgOUvli7X8fwfyFHPuvkZs8VJdI+MR6E+SF4a l00oxH4J1mc3t2SMu8UWtd7ngA05SIy3iTcOMyOKnDd0oKaTlfhKat0ubV1NVCKE 3JGyKqs9BOJE17A= Received: (qmail 52612 invoked by alias); 21 Mar 2019 16:19:41 -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 51279 invoked by uid 89); 21 Mar 2019 16:19:41 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-15.8 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 autolearn=ham version=3.3.1 spammy=two-way, twoway X-HELO: EUR02-AM5-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=8EGHQAAQlwpXgnvu/H10EYSKmz7wmAmjFiPfqEfLxCQ=; b=qctMP3WC+NJGi8NYbupYJWBWRBBxGj6esgYz9GZ8m5BudNhNVXFdrBzG3PZ1JwWhNQU2t4K3BqAq8i6FjCXGux+2CBVrOwd3geHvyUrvsykm7Bd0Zcy8lT2ikDbw2jmrlL1C47SlfsA9YSIwyMMwUekoAeUcAWEDgBh/7fG1Z/k= From: Wilco Dijkstra To: "libc-alpha@sourceware.org" CC: nd Subject: [PATCH] Improve bench-memmem Date: Thu, 21 Mar 2019 16:19:36 +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) x-ms-exchange-senderadcheck: 1 MIME-Version: 1.0 X-MS-Exchange-CrossTenant-mailboxtype: HOSTED Improve bench-memmem by replacing simple_memmem with a more efficient implementation. Add the Two-way implementation to enable direct comparison with the optimized memmem. Also change the number of iterations to reduce the amount of output. ChangeLog: 2019-03-21 Wilco Dijkstra * benchtests/bench-memmem.c (simple_memmem): Remove function. (basic_memmem): Add function. (twoway_memmem): Add function. diff --git a/benchtests/bench-memmem.c b/benchtests/bench-memmem.c index 4936b236a33b5e22ca6c25b4729be5fee2cd6a04..b6b97f3d1f5f94a71c177cc516cba81c869d3865 100644 --- a/benchtests/bench-memmem.c +++ b/benchtests/bench-memmem.c @@ -19,22 +19,51 @@ #define TEST_MAIN #define TEST_NAME "memmem" #define BUF1PAGES 20 -#define ITERATIONS 500 +#define ITERATIONS 100 #include "bench-string.h" typedef char *(*proto_t) (const void *, size_t, const void *, size_t); -void *simple_memmem (const void *, size_t, const void *, size_t); -IMPL (simple_memmem, 0) -IMPL (memmem, 1) +void * +basic_memmem (const void *haystack, size_t hs_len, const void *needle, + size_t ne_len) +{ + const char *hs = haystack; + const char *ne = needle; + + if (ne_len == 0) + return (void *)hs; + int i; + int c = ne[0]; + const char *end = hs + hs_len - ne_len; + + for ( ; hs <= end; hs++) + { + if (hs[0] != c) + continue; + for (i = ne_len - 1; i != 0; i--) + if (hs[i] != ne[i]) + break; + if (i == 0) + return (void *)hs; + } + + return NULL; +} + +#define RETURN_TYPE void * +#define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l)) +#define FASTSEARCH(S,C,N) (void*) memchr ((void *)(S), (C), (N)) +#include "../string/str-two-way.h" void * -simple_memmem (const void *haystack, size_t haystack_len, const void *needle, - size_t needle_len) +twoway_memmem (const void *haystack_start, size_t haystack_len, + const void *needle_start, size_t needle_len) { - const char *begin; - const char *const last_possible - = (const char *) haystack + haystack_len - needle_len; + /* Abstract memory is considered to be an array of 'unsigned char' values, + 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; if (needle_len == 0) /* The first occurrence of the empty string is deemed to occur at @@ -46,16 +75,32 @@ simple_memmem (const void *haystack, size_t haystack_len, const void *needle, if (__glibc_unlikely (haystack_len < needle_len)) return NULL; - for (begin = (const char *) haystack; begin <= last_possible; ++begin) - if (begin[0] == ((const char *) needle)[0] - && !memcmp ((const void *) &begin[1], - (const void *) ((const char *) needle + 1), - needle_len - 1)) - return (void *) begin; - - return NULL; + /* 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 + can often achieve sublinear performance. */ + if (needle_len < LONG_NEEDLE_THRESHOLD) + { + haystack = memchr (haystack, *needle, haystack_len); + if (!haystack || __builtin_expect (needle_len == 1, 0)) + return (void *) haystack; + haystack_len -= haystack - (const unsigned char *) haystack_start; + if (haystack_len < needle_len) + return NULL; + /* 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 (void *) haystack; + return two_way_short_needle (haystack, haystack_len, needle, needle_len); + } + else + return two_way_long_needle (haystack, haystack_len, needle, needle_len); } +IMPL (memmem, 1) +IMPL (twoway_memmem, 0) +IMPL (basic_memmem, 0) + static void do_one_test (impl_t *impl, const void *haystack, size_t haystack_len, const void *needle, size_t needle_len, const void *expected)