about summary refs log tree commit diff
path: root/benchtests
diff options
context:
space:
mode:
authorWilco Dijkstra <wilco.dijkstra@arm.com>2024-04-24 18:24:45 +0100
committerWilco Dijkstra <wilco.dijkstra@arm.com>2024-04-24 18:25:46 +0100
commitf262fce61671c38d436d2d0cd68dab5642ac9ef0 (patch)
tree4ada45bdf29e4d4384b98f237a6de2277ff35d39 /benchtests
parent46c999741340ea559784c20a45077955b50aca43 (diff)
downloadglibc-f262fce61671c38d436d2d0cd68dab5642ac9ef0.tar.gz
glibc-f262fce61671c38d436d2d0cd68dab5642ac9ef0.tar.xz
glibc-f262fce61671c38d436d2d0cd68dab5642ac9ef0.zip
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>
Diffstat (limited to 'benchtests')
-rw-r--r--benchtests/bench-strstr.c27
1 files changed, 27 insertions, 0 deletions
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