diff mbox series

benchtests: Add difficult strstr needle for bruteforce algorithms

Message ID PAWPR08MB8982F63E1AF0745763EC682B830E2@PAWPR08MB8982.eurprd08.prod.outlook.com
State New
Headers show
Series benchtests: Add difficult strstr needle for bruteforce algorithms | expand

Commit Message

Wilco Dijkstra April 18, 2024, 1:03 p.m. UTC 
Add another difficult needle to strstr that clearly shows the quadratic
complexity of bruteforce algorithms.

OK for commit?

---

Comments

Adhemerval Zanella Netto April 23, 2024, 6:47 p.m. UTC | #1 
On 18/04/24 10:03, Wilco Dijkstra wrote:
> 
> Add another difficult needle to strstr that clearly shows the quadratic
> complexity of bruteforce algorithms.
> 
> OK for commit?

LGTM, thanks.

Reviewed-by: Adhemerval Zanella  <adhemerval.zanella@linaro.org>

> 
> ---
> 
> diff --git a/benchtests/bench-strstr.c b/benchtests/bench-strstr.c
> index 9288ad16e963d5397419aa11263520d259d2d6b9..4b07d39a50b0e5e1f29743a258b05466099c1959 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
>
diff mbox series

Patch

diff --git a/benchtests/bench-strstr.c b/benchtests/bench-strstr.c
index 9288ad16e963d5397419aa11263520d259d2d6b9..4b07d39a50b0e5e1f29743a258b05466099c1959 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