public inbox for glibc-cvs@sourceware.org help / color / mirror / Atom feed
From: Wilco Dijkstra <wilco@sourceware.org> To: glibc-cvs@sourceware.org Subject: [glibc] benchtests: Add difficult strstr needle for bruteforce algorithms Date: Wed, 24 Apr 2024 17:26:25 +0000 (GMT) [thread overview] Message-ID: <20240424172625.325F4385840D@sourceware.org> (raw) https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=f262fce61671c38d436d2d0cd68dab5642ac9ef0 commit f262fce61671c38d436d2d0cd68dab5642ac9ef0 Author: Wilco Dijkstra <wilco.dijkstra@arm.com> 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 <adhemerval.zanella@linaro.org> 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
reply other threads:[~2024-04-24 17:26 UTC|newest] Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20240424172625.325F4385840D@sourceware.org \ --to=wilco@sourceware.org \ --cc=glibc-cvs@sourceware.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).