From 80b2bfb5350442ef1a781b0ee9dd44d61bd88f8a Mon Sep 17 00:00:00 2001 From: Wilco Dijkstra Date: Tue, 11 Jun 2019 15:52:21 +0100 Subject: Benchmark strstr hard needles 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. Reviewed-by: Adhemerval Zanella * benchtests/bench-strstr.c (test_hard_needle): New function. --- ChangeLog | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'ChangeLog') diff --git a/ChangeLog b/ChangeLog index e3f60702ea..2c9836d4e6 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,7 @@ +2019-06-11 Wilco Dijkstra + + * benchtests/bench-strstr.c (test_hard_needle): New function. + 2019-06-10 Joseph Myers * malloc/tst-calloc.c: Include . -- cgit v1.2.3