Home for HMNL Enterprise Computing

Calibrating String Searches

Ian Tree  08 October 2013 15:03:45

Calibrating some String Search Algorithms


Last weekend I had the need to calibrate a new test environment in preparation for doing some performance benchmarking. I cast around for an old benchmark application that would not take much set up time and I came across an application that performed comparative benchmarks on different string search algorithms. I compiled the application with both Visual Studio 2005 and Visual Studio 2012 and ran through the test series.

In the benchmark application each algorithm is exercised by performing 10,000 cycles of a series of 5 searches (4 hits and one miss), the application reports the elapsed time in milliseconds for each test. The results are shown below.

VS 2005VS 2012
AlgorithmDebug/Od (disable)/O2 (speed)Debug/Od (disable)/O2 (speed)
Reference builtin (strstr)7,3327,2548,128843718873
Brute Force40,31037,65811,91940,63836,69112,496
Scan compare16,27111,5289,09411,1547,1144,976
Knuth-Morris-Pratt53,55552,90014,55553,25852,91515,085
Boyer-Moore4,4304,4151,5924,6234,4881,808
Boyer-Moore-Horspool3,5104,4141,5763,4943,5561,685

Observations

The results of the Knuth-Morris-Pratt tests should probably be discounted, I don't remember it being that slow, I suspect that the test application has some experimental modifications in that algorithm.

What is interesting is the near 10 fold improvement in performance of the builtin strstr() function between the Visual Studio 2005 and the Visual Studio 2012 implementations. This improvement makes the builtin function the outright winner from this test set in the VS 2012 implementation.

Comments