From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS31976 209.132.180.0/23 X-Spam-Status: No, score=-4.0 required=3.0 tests=AWL,BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_EF,HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED,SPF_HELO_PASS,SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 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 dcvr.yhbt.net (Postfix) with ESMTPS id 845DD1F462 for ; Mon, 20 May 2019 18:49:09 +0000 (UTC) DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:subject:to:cc:references:from:message-id:date :mime-version:in-reply-to:content-type :content-transfer-encoding; q=dns; s=default; b=kKAedwB389OsZ2J7 592CDZsOaXGnhxjVz8/MLgycqrLrpWYLAa2lFJBUp2PzpE+D5iae5q3Oi37pSpaU PNpwDZX+nhb/dyYCTSM0CArU93qujQa0jzs9v45pbvQGAeWSQOjV953JqBI/yf/P VzX5YdsW73VOweqU8fNvSRjX7Hc= 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:subject:to:cc:references:from:message-id:date :mime-version:in-reply-to:content-type :content-transfer-encoding; s=default; bh=O5DfItCPKg8p37z3n5/0gV WKVI0=; b=o2NOsbit0epXFdk2Sd0DO9+xnyV/CHPrFY292tcntoJJ95d2VmQuN1 QTFOUvHANj26JpZn9sDPVaUJJdpbxJ6WiR03qjIvrHaYuaF1iHEAGpdyN99lH99y LgByKK7B2QgE5bCUEoikeAIq5rVcoZMF8zbrkZuGhZqP0a6P5LpQ0= Received: (qmail 109942 invoked by alias); 20 May 2019 18:49:07 -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 Received: (qmail 109821 invoked by uid 89); 20 May 2019 18:49:07 -0000 Authentication-Results: sourceware.org; auth=none X-HELO: mail-ua1-f65.google.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=subject:to:cc:references:from:openpgp:autocrypt:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=Z7qtX+zvawgxvaFJpw1hBUlP87/lcocdqKjhJNvoE8E=; b=gL8kN5Fyuy0dLDvjFTa3BIMYGMAtcYRYOyptnq3KS7+e0itQGawR4dKIOsESBzTxdZ o88bRAApCPn5twXntBATE9iSqtG0C8Ep4HIixdeNlt88ItbfBf1qWu9V7Bq33gx++kL6 DJp6KKZvGIXhf4IXm1I7CYrYB5+DB5aUk6Rj2qLdsj2cZ3H26PiS7ClK+FkK5CLYCYH3 wp3TRgOmQCiyhqgYmLOuVgyS0RajxovSik5bw4P4Icjfiw7yNjlT6sju9Cd5A7ScJbMy 70U7SM2ZVgZjvDc7kZ8wQFzxtLdfFLAzusaQQLRhyOL9yyiQPdCHA441iGGlg4mdtR/Y Td3A== Subject: Re: [PATCH v2] Benchmark strstr hard needles To: Wilco Dijkstra , "libc-alpha@sourceware.org" Cc: nd References: From: Adhemerval Zanella Openpgp: preference=signencrypt Message-ID: <3cacddd7-308b-7579-e6f8-50f6c49778cc@linaro.org> Date: Mon, 20 May 2019 15:49:01 -0300 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.6.1 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit On 26/04/2019 08:57, Wilco Dijkstra wrote: > v2: Add another hard needle case. > > Benchmark hard needles both for Two-way and the new strstr algorithm. > This shows how the worst cases are quite close and both much faster than > the quadratic basic_strstr. Thanks to Szabolcs for providing various > hard needles. > > ChangeLog: > 2019-04-25 Wilco Dijkstra > > * benchtests/bench-strstr.c (test_hard_needle): New function. LGTM with some nits below, thanks. Reviewed-by: Adhemerval Zanella > > -- > > diff --git a/benchtests/bench-strstr.c b/benchtests/bench-strstr.c > index 31309b24029a96de7381e1050fd89e5d26642e5f..f604460c60002e745a76a30835976df95f753234 100644 > --- a/benchtests/bench-strstr.c > +++ b/benchtests/bench-strstr.c > @@ -203,6 +203,74 @@ do_test (size_t align1, size_t align2, size_t len1, size_t len2, > putchar ('\n'); > } > > + > +char * volatile null = NULL; > + I am not seeing why exactly it requires a global non static volatile variable to call do_one_test. > +static void > +test_hard_needle (size_t ne_len, size_t hs_len) > +{ Maybe add some context from where these tests came from, from the libc-alpha discussion? > + char *ne = (char *) buf1; > + char *hs = (char *) buf2; > + > + /* Hard needle for strstr algorithm using skip table. */ > + { > + memset (ne, 'a', ne_len); > + ne[ne_len] = '\0'; > + ne[ne_len - 14] = 'b'; > + > + memset (hs, 'a', hs_len); > + for (size_t i = ne_len; i <= hs_len; i += ne_len) > + { > + hs[i-5] = 'b'; > + hs[i-62] = 'b'; > + } > + > + printf ("Length %4zd/%3zd, complex needle 1:", hs_len, ne_len); > + > + FOR_EACH_IMPL (impl, 0) > + do_one_test (impl, hs, ne, null); > + putchar ('\n'); > + } > + > + /* 2nd hard needle for strstr algorithm using skip table. */ > + { > + memset (ne, 'a', ne_len); > + ne[ne_len] = '\0'; > + ne[ne_len - 6] = 'b'; > + > + memset (hs, 'a', hs_len); > + for (size_t i = ne_len; i <= hs_len; i += ne_len) > + { > + hs[i-5] = 'b'; > + hs[i-6] = 'b'; > + } > + > + printf ("Length %4zd/%3zd, complex needle 2:", hs_len, ne_len); > + > + FOR_EACH_IMPL (impl, 0) > + do_one_test (impl, hs, ne, null); > + putchar ('\n'); > + } > + > + /* Hard needle for Two-way algorithm. */ > + { > + for (int i = 0; i < hs_len; i++) > + hs[i] = (rand () & 255) > 155 ? 'a' : 'b'; > + hs[hs_len] = 0; > + > + memset (ne, 'a', ne_len); > + ne[ne_len-2] = 'b'; > + ne[0] = 'b'; > + ne[ne_len] = 0; > + > + printf ("Length %4zd/%3zd, complex needle 3:", hs_len, ne_len); > + > + FOR_EACH_IMPL (impl, 0) > + do_one_test (impl, hs, ne, null); > + putchar ('\n'); > + } > +} > + > static int > test_main (void) > { > @@ -227,6 +295,10 @@ test_main (void) > do_test (14, 5, hlen, klen, 1); > } > > + test_hard_needle (64, 65536); > + test_hard_needle (256, 65536); > + test_hard_needle (1024, 65536); > + > return ret; > } > >