[glibc] benchtests: Add difficult strstr needle for bruteforce algorithms

[glibc] benchtests: Add difficult strstr needle for bruteforce algorithms

[Wilco Dijkstra]

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