Patchwork Benchmark strstr hard needles

login
register
mail settings
Submitter Wilco Dijkstra
Date April 24, 2019, 2:04 p.m.
Message ID <VI1PR0801MB21272E38054E27C5E48B6ED1833C0@VI1PR0801MB2127.eurprd08.prod.outlook.com>
Download mbox | patch
Permalink /patch/32402/
State New
Headers show

Comments

Wilco Dijkstra - April 24, 2019, 2:04 p.m.
Benchmark hard needles both for Two-way and the new strstr algorithm.
This shows how the worst cases are quite close and both much faster than
the quadratic basic_strstr.  Thanks to Szabolcs for providing various
hard needles.

ChangeLog:
2019-04-24  Wilco Dijkstra  <wdijkstr@arm.com>

        * benchtests/bench-strstr.c (test_hard_needle): New function.
--

Patch

diff --git a/benchtests/bench-strstr.c b/benchtests/bench-strstr.c
index 31309b24029a96de7381e1050fd89e5d26642e5f..5cb889aa8dbf4a08940159f8ddca717f59deb88d 100644
--- a/benchtests/bench-strstr.c
+++ b/benchtests/bench-strstr.c
@@ -203,6 +203,52 @@  do_test (size_t align1, size_t align2, size_t len1, size_t len2,
   putchar ('\n');
 }
 
+
+char * volatile null = NULL;
+
+static void
+test_hard_needle (size_t ne_len, size_t hs_len)
+{
+  char *ne = (char *) buf1;
+  char *hs = (char *) buf2;
+
+  /* Hard needle for strstr algorithm using skip table.  */
+  memset (ne, 'a', ne_len);
+  ne[ne_len] = '\0';
+  ne[ne_len - 6] = 'b';
+
+  memset (hs, 'a', hs_len);
+  for (size_t i = ne_len; i < hs_len; i += ne_len)
+    {
+       hs[i-5] = 'b';
+       hs[i-6] = 'b';
+    }
+
+  printf ("Length %4zd/%3zd, complex needle 1:", hs_len, ne_len);
+
+  FOR_EACH_IMPL (impl, 0)
+    do_one_test (impl, hs, ne, null);
+  putchar ('\n');
+
+  /* Hard needle for Two-way algorithm.  */
+  for (int i = 0; i < hs_len; i++)
+    hs[i] = (rand () & 255) > 155 ? 'a' : 'b';
+  hs[hs_len] = 0;
+
+  memset (ne, 'a', ne_len);
+  ne[ne_len-2] = 'b';
+  ne[0] = 'b';
+  ne[ne_len] = 0;
+
+  printf ("Length %4zd/%3zd, complex needle 2:", hs_len, ne_len);
+
+  {
+    FOR_EACH_IMPL (impl, 0)
+      do_one_test (impl, hs, ne, null);
+    putchar ('\n');
+  }
+}
+
 static int
 test_main (void)
 {
@@ -227,6 +273,10 @@  test_main (void)
 	do_test (14, 5, hlen, klen, 1);
       }
 
+  test_hard_needle (64, 65536);
+  test_hard_needle (255, 65536);
+  test_hard_needle (1024, 65536);
+
   return ret;
 }