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: 31935 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)