[v2] Benchmark strstr hard needles
Commit Message
ping
v2: Add another hard needle case.
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-25 Wilco Dijkstra <wdijkstr@arm.com>
* benchtests/bench-strstr.c (test_hard_needle): New function.
--
@@ -203,6 +203,74 @@ 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 - 14] = 'b';
+
+Â Â Â memset (hs, 'a', hs_len);
+Â Â Â for (size_t i = ne_len; i <= hs_len; i += ne_len)
+Â Â Â Â Â {
+Â Â Â Â Â Â hs[i-5] = 'b';
+Â Â Â Â Â Â hs[i-62] = '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');
+Â }
+
+ /* 2nd 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 2:", 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 3:", 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 +295,10 @@ test_main (void)
        do_test (14, 5, hlen, klen, 1);
      }
Â
+Â test_hard_needle (64, 65536);
+Â test_hard_needle (256, 65536);
+Â test_hard_needle (1024, 65536);
+
  return ret;
 }
Â