From f262fce61671c38d436d2d0cd68dab5642ac9ef0 Mon Sep 17 00:00:00 2001 From: Wilco Dijkstra Date: Wed, 24 Apr 2024 18:24:45 +0100 Subject: 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 --- 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 -- cgit 1.4.1