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 2005			VS 2012
Algorithm	Debug	/Od (disable)	/O2 (speed)	Debug	/Od (disable)	/O2 (speed)
Reference builtin (strstr)	7,332	7,254	8,128	843	718	873
Brute Force	40,310	37,658	11,919	40,638	36,691	12,496
Scan compare	16,271	11,528	9,094	11,154	7,114	4,976
Knuth-Morris-Pratt	53,555	52,900	14,555	53,258	52,915	15,085
Boyer-Moore	4,430	4,415	1,592	4,623	4,488	1,808
Boyer-Moore-Horspool	3,510	4,414	1,576	3,494	3,556	1,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 [0]