From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1895) id 325F4385840D; Wed, 24 Apr 2024 17:26:25 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 325F4385840D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1713979585; bh=CzEg3COoDQLzGe3lPxC+KV2O0phWuSXJXYhazy7Twdg=; h=From:To:Subject:Date:From; b=YnoyYfPS6r/ZDnzw5B0bQ7XwMBsGY9NIk57QFvYu8IBmX0ztEgQQDp9Hf/pfGL8KZ Y+REyOOgn8ZUYG9Up7kHrUhOw9h2Wmg92sPtmNrybEHtiCrgVo/gSpmGEJV+GbY3rs Ys2lMpVgL3jvSj/VBI07QBSjqyLoS21FAfWycZKQ= Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Wilco Dijkstra To: glibc-cvs@sourceware.org Subject: [glibc] benchtests: Add difficult strstr needle for bruteforce algorithms X-Act-Checkin: glibc X-Git-Author: Wilco Dijkstra X-Git-Refname: refs/heads/master X-Git-Oldrev: 46c999741340ea559784c20a45077955b50aca43 X-Git-Newrev: f262fce61671c38d436d2d0cd68dab5642ac9ef0 Message-Id: <20240424172625.325F4385840D@sourceware.org> Date: Wed, 24 Apr 2024 17:26:25 +0000 (GMT) List-Id: https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=f262fce61671c38d436d2d0cd68dab5642ac9ef0 commit f262fce61671c38d436d2d0cd68dab5642ac9ef0 Author: Wilco Dijkstra Date: Wed Apr 24 18:24:45 2024 +0100 benchtests: Add difficult strstr needle for bruteforce algorithms Add another difficult needle to strstr that clearly shows the quadratic complexity of bruteforce algorithms. Reviewed-by: Adhemerval Zanella Diff: --- benchtests/bench-strstr.c | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+) diff --git a/benchtests/bench-strstr.c b/benchtests/bench-strstr.c index 9288ad16e9..4b07d39a50 100644 --- a/benchtests/bench-strstr.c +++ b/benchtests/bench-strstr.c @@ -352,6 +352,33 @@ test_hard_needle (json_ctx_t *json_ctx, size_t ne_len, size_t hs_len) json_array_end (json_ctx); json_element_object_end (json_ctx); } + + /* Hard needle for bruteforce algorithms that match first few chars. */ + { + memset (hs, 'a', hs_len); + for (int i = ne_len-1; i < hs_len; i += ne_len) + hs[i] = 'b'; + hs[hs_len] = 0; + + memset (ne, 'a', ne_len); + ne[ne_len] = 0; + + json_element_object_begin (json_ctx); + json_attr_uint (json_ctx, "len_haystack", hs_len); + json_attr_uint (json_ctx, "len_needle", ne_len); + json_attr_uint (json_ctx, "align_haystack", 0); + json_attr_uint (json_ctx, "align_needle", 0); + json_attr_uint (json_ctx, "fail", 1); + json_attr_string (json_ctx, "desc", "Difficult bruteforce needle"); + + json_array_begin (json_ctx, "timings"); + + FOR_EACH_IMPL (impl, 0) + do_one_test (json_ctx, impl, hs, ne, NULL); + + json_array_end (json_ctx); + json_element_object_end (json_ctx); + } } static int