* [PATCH v2] Benchmark strstr hard needles
@ 2019-04-26 11:57 Wilco Dijkstra
2019-05-07 15:08 ` Wilco Dijkstra
2019-05-20 18:49 ` Adhemerval Zanella
0 siblings, 2 replies; 6+ messages in thread
From: Wilco Dijkstra @ 2019-04-26 11:57 UTC (permalink / raw)
To: libc-alpha@sourceware.org; +Cc: nd
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.
--
diff --git a/benchtests/bench-strstr.c b/benchtests/bench-strstr.c
index 31309b24029a96de7381e1050fd89e5d26642e5f..f604460c60002e745a76a30835976df95f753234 100644
--- a/benchtests/bench-strstr.c
+++ b/benchtests/bench-strstr.c
@@ -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;
}
^ permalink raw reply related [flat|nested] 6+ messages in thread* Re: [PATCH v2] Benchmark strstr hard needles
2019-04-26 11:57 [PATCH v2] Benchmark strstr hard needles Wilco Dijkstra
@ 2019-05-07 15:08 ` Wilco Dijkstra
2019-05-20 18:49 ` Adhemerval Zanella
1 sibling, 0 replies; 6+ messages in thread
From: Wilco Dijkstra @ 2019-05-07 15:08 UTC (permalink / raw)
To: libc-alpha@sourceware.org; +Cc: nd
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.
--
diff --git a/benchtests/bench-strstr.c b/benchtests/bench-strstr.c
index 31309b24029a96de7381e1050fd89e5d26642e5f..f604460c60002e745a76a30835976df95f753234 100644
--- a/benchtests/bench-strstr.c
+++ b/benchtests/bench-strstr.c
@@ -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;
}
^ permalink raw reply related [flat|nested] 6+ messages in thread* Re: [PATCH v2] Benchmark strstr hard needles
2019-04-26 11:57 [PATCH v2] Benchmark strstr hard needles Wilco Dijkstra
2019-05-07 15:08 ` Wilco Dijkstra
@ 2019-05-20 18:49 ` Adhemerval Zanella
2019-05-21 13:12 ` Wilco Dijkstra
1 sibling, 1 reply; 6+ messages in thread
From: Adhemerval Zanella @ 2019-05-20 18:49 UTC (permalink / raw)
To: Wilco Dijkstra, libc-alpha@sourceware.org; +Cc: nd
On 26/04/2019 08:57, Wilco Dijkstra wrote:
> 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.
LGTM with some nits below, thanks.
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
>
> --
>
> diff --git a/benchtests/bench-strstr.c b/benchtests/bench-strstr.c
> index 31309b24029a96de7381e1050fd89e5d26642e5f..f604460c60002e745a76a30835976df95f753234 100644
> --- a/benchtests/bench-strstr.c
> +++ b/benchtests/bench-strstr.c
> @@ -203,6 +203,74 @@ do_test (size_t align1, size_t align2, size_t len1, size_t len2,
> putchar ('\n');
> }
>
> +
> +char * volatile null = NULL;
> +
I am not seeing why exactly it requires a global non static volatile
variable to call do_one_test.
> +static void
> +test_hard_needle (size_t ne_len, size_t hs_len)
> +{
Maybe add some context from where these tests came from, from the
libc-alpha discussion?
> + 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;
> }
>
>
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [PATCH v2] Benchmark strstr hard needles
2019-05-20 18:49 ` Adhemerval Zanella
@ 2019-05-21 13:12 ` Wilco Dijkstra
2019-06-10 11:46 ` Wilco Dijkstra
0 siblings, 1 reply; 6+ messages in thread
From: Wilco Dijkstra @ 2019-05-21 13:12 UTC (permalink / raw)
To: Adhemerval Zanella, libc-alpha@sourceware.org; +Cc: nd
Hi Adhemerval,
> +char * volatile null = NULL;
> I am not seeing why exactly it requires a global non static volatile
> variable to call do_one_test.
You're right, this is not necessary in the current version (IIRC it was to avoid
a warning), so I have removed it.
> Maybe add some context from where these tests came from, from the
> libc-alpha discussion?
Sure, I've improved the comments and description to make it clearer what
the hard needle test is doing and why. New version below.
Wilco
[PATCH v3] Benchmark strstr hard needles
v3: Improve comments/description.
Benchmark needles which exhibit worst-case performance. This shows that
basic_strstr is quadratic and thus unsuitable for large needles.
On the other hand the Two-way and new strstr implementations are linear with
increasing needle sizes. The slowest cases of the two implementations are
within a factor of 2 on several different microarchitectures. Two-way is
slowest on inputs which cause a branch mispredict on almost every character.
The new strstr is slowest on inputs which almost match and result in many
calls to memcmp. Thanks to Szabolcs for providing various hard needles.
ChangeLog:
2019-05-21 Wilco Dijkstra <wdijkstr@arm.com>
* benchtests/bench-strstr.c (test_hard_needle): New function.
--
diff --git a/benchtests/bench-strstr.c b/benchtests/bench-strstr.c
index 31309b24029a96de7381e1050fd89e5d26642e5f..5ec6edcf1869dd198a3326cb85f2a4463ae3417c 100644
--- a/benchtests/bench-strstr.c
+++ b/benchtests/bench-strstr.c
@@ -203,6 +203,81 @@ do_test (size_t align1, size_t align2, size_t len1, size_t len2,
putchar ('\n');
}
+/* Test needles which exhibit worst-case performance. This shows that
+ basic_strstr is quadratic and thus unsuitable for large needles.
+ On the other hand Two-way and skip table implementations are linear with
+ increasing needle sizes. The slowest cases of the two implementations are
+ within a factor of 2 on several different microarchitectures. */
+
+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. This results in many
+ memcmp calls comparing most of the needle. */
+ {
+ 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. This results in
+ many memcmp calls comparing most of the needle. */
+ {
+ 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 - the random input causes a large number
+ of branch mispredictions which significantly reduces performance on modern
+ micro architectures. */
+ {
+ 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 +302,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;
}
^ permalink raw reply related [flat|nested] 6+ messages in thread* Re: [PATCH v2] Benchmark strstr hard needles
2019-05-21 13:12 ` Wilco Dijkstra
@ 2019-06-10 11:46 ` Wilco Dijkstra
2019-06-11 13:13 ` Adhemerval Zanella
0 siblings, 1 reply; 6+ messages in thread
From: Wilco Dijkstra @ 2019-06-10 11:46 UTC (permalink / raw)
To: Adhemerval Zanella, libc-alpha@sourceware.org; +Cc: nd
Hi Adhemerval,
> +char * volatile null = NULL;
> I am not seeing why exactly it requires a global non static volatile
> variable to call do_one_test.
You're right, this is not necessary in the current version (IIRC it was to avoid
a warning), so I have removed it.
> Maybe add some context from where these tests came from, from the
> libc-alpha discussion?
Sure, I've improved the comments and description to make it clearer what
the hard needle test is doing and why. New version below.
Wilco
[PATCH v3] Benchmark strstr hard needles
v3: Improve comments/description.
Benchmark needles which exhibit worst-case performance. This shows that
basic_strstr is quadratic and thus unsuitable for large needles.
On the other hand the Two-way and new strstr implementations are linear with
increasing needle sizes. The slowest cases of the two implementations are
within a factor of 2 on several different microarchitectures. Two-way is
slowest on inputs which cause a branch mispredict on almost every character.
The new strstr is slowest on inputs which almost match and result in many
calls to memcmp. Thanks to Szabolcs for providing various hard needles.
ChangeLog:
2019-05-21 Wilco Dijkstra <wdijkstr@arm.com>
* benchtests/bench-strstr.c (test_hard_needle): New function.
--
diff --git a/benchtests/bench-strstr.c b/benchtests/bench-strstr.c
index 31309b24029a96de7381e1050fd89e5d26642e5f..5ec6edcf1869dd198a3326cb85f2a4463ae3417c 100644
--- a/benchtests/bench-strstr.c
+++ b/benchtests/bench-strstr.c
@@ -203,6 +203,81 @@ do_test (size_t align1, size_t align2, size_t len1, size_t len2,
putchar ('\n');
}
+/* Test needles which exhibit worst-case performance. This shows that
+ basic_strstr is quadratic and thus unsuitable for large needles.
+ On the other hand Two-way and skip table implementations are linear with
+ increasing needle sizes. The slowest cases of the two implementations are
+ within a factor of 2 on several different microarchitectures. */
+
+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. This results in many
+ memcmp calls comparing most of the needle. */
+ {
+ 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. This results in
+ many memcmp calls comparing most of the needle. */
+ {
+ 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 - the random input causes a large number
+ of branch mispredictions which significantly reduces performance on modern
+ micro architectures. */
+ {
+ 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 +302,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;
}
^ permalink raw reply related [flat|nested] 6+ messages in thread* Re: [PATCH v2] Benchmark strstr hard needles
2019-06-10 11:46 ` Wilco Dijkstra
@ 2019-06-11 13:13 ` Adhemerval Zanella
0 siblings, 0 replies; 6+ messages in thread
From: Adhemerval Zanella @ 2019-06-11 13:13 UTC (permalink / raw)
To: Wilco Dijkstra, libc-alpha@sourceware.org; +Cc: nd
On 10/06/2019 08:46, Wilco Dijkstra wrote:
> Hi Adhemerval,
>
>> +char * volatile null = NULL;
>
>> I am not seeing why exactly it requires a global non static volatile
>> variable to call do_one_test.
>
> You're right, this is not necessary in the current version (IIRC it was to avoid
> a warning), so I have removed it.
>
>> Maybe add some context from where these tests came from, from the
>> libc-alpha discussion?
>
> Sure, I've improved the comments and description to make it clearer what
> the hard needle test is doing and why. New version below.
>
> Wilco
LGTM, thanks.
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
>
>
> [PATCH v3] Benchmark strstr hard needles
>
> v3: Improve comments/description.
>
> Benchmark needles which exhibit worst-case performance. This shows that
> basic_strstr is quadratic and thus unsuitable for large needles.
> On the other hand the Two-way and new strstr implementations are linear with
> increasing needle sizes. The slowest cases of the two implementations are
> within a factor of 2 on several different microarchitectures. Two-way is
> slowest on inputs which cause a branch mispredict on almost every character.
> The new strstr is slowest on inputs which almost match and result in many
> calls to memcmp. Thanks to Szabolcs for providing various hard needles.
>
>
> ChangeLog:
> 2019-05-21 Wilco Dijkstra <wdijkstr@arm.com>
>
> * benchtests/bench-strstr.c (test_hard_needle): New function.
>
> --
> diff --git a/benchtests/bench-strstr.c b/benchtests/bench-strstr.c
> index 31309b24029a96de7381e1050fd89e5d26642e5f..5ec6edcf1869dd198a3326cb85f2a4463ae3417c 100644
> --- a/benchtests/bench-strstr.c
> +++ b/benchtests/bench-strstr.c
> @@ -203,6 +203,81 @@ do_test (size_t align1, size_t align2, size_t len1, size_t len2,
> putchar ('\n');
> }
>
> +/* Test needles which exhibit worst-case performance. This shows that
> + basic_strstr is quadratic and thus unsuitable for large needles.
> + On the other hand Two-way and skip table implementations are linear with
> + increasing needle sizes. The slowest cases of the two implementations are
> + within a factor of 2 on several different microarchitectures. */
> +
> +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. This results in many
> + memcmp calls comparing most of the needle. */
> + {
> + 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. This results in
> + many memcmp calls comparing most of the needle. */
> + {
> + 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 - the random input causes a large number
> + of branch mispredictions which significantly reduces performance on modern
> + micro architectures. */
> + {
> + 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 +302,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;
> }
>
>
>
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2019-06-11 13:13 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-04-26 11:57 [PATCH v2] Benchmark strstr hard needles Wilco Dijkstra
2019-05-07 15:08 ` Wilco Dijkstra
2019-05-20 18:49 ` Adhemerval Zanella
2019-05-21 13:12 ` Wilco Dijkstra
2019-06-10 11:46 ` Wilco Dijkstra
2019-06-11 13:13 ` Adhemerval Zanella
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).