From patchwork Tue May 7 15:08:37 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Wilco Dijkstra X-Patchwork-Id: 32592 Received: (qmail 105664 invoked by alias); 7 May 2019 15:08:44 -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 105639 invoked by uid 89); 7 May 2019 15:08:43 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-16.7 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=needle, HX-Languages-Length:2371, Hard X-HELO: EUR03-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=gJjvrm4jDbDYK0bvfr7Rq7ubApBX3NbPnalEKqlgJ+A=; b=rTKAZo61Q05+fSGBnvI7UTbN3gmmBbiTu1uw6zH481IJO7Q1zc3DU13WG9jaBdudxUiuS4PkAlZQWwC7wcnhqWuMNhfAx/6/YATHH15CqItltn5w+8LV3kHpg5XwtR4+VX84OsdJWnSqOdnqwrBjfooHvpNbU3Mwgsa6PhnLmIE= From: Wilco Dijkstra To: "libc-alpha@sourceware.org" CC: nd Subject: Re: [PATCH v2] Benchmark strstr hard needles Date: Tue, 7 May 2019 15:08:37 +0000 Message-ID: References: In-Reply-To: authentication-results: spf=none (sender IP is ) smtp.mailfrom=Wilco.Dijkstra@arm.com; x-ms-oob-tlc-oobclassifiers: OLM:1388; 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 ping 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. 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; + +static void +test_hard_needle (size_t ne_len, size_t hs_len) +{ +  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;  } Â