I have a file that's 21056 bytes.
I've written a program in C that reads the entire file into a buffer, and then uses multiple search algorithms to search the file for a token that's 82 chars.
I've used all the implementations of the algorithms from the “Exact String Matching Algorithms” page. I've used: KMP, BM, TBM, and Horspool. And then I used strstr
and benchmarked each one.
What I'm wondering is, each time the strstr
outperforms all the other algorithms. The only one that is faster sometimes is BM.
Shouldn't strstr
be the slowest?
Here's my benchmark code with an example of benchmarking BM:
double get_time()
{
LARGE_INTEGER t, f;
QueryPerformanceCounter(&t);
QueryPerformanceFrequency(&f);
return (double)t.QuadPart/(double)f.QuadPart;
}
before = get_time();
BM(token, strlen(token), buffer, len);
after = get_time();
printf("Time: %f\n\n", after - before);
Could someone explain to me why strstr
is outperforming the other search algorithms? I'll post more code on request if needed.
Why do you think strstr
should be slower than all the others? Do you know what algorithm strstr
uses? I think it's quite likely that strstr
uses a fine-tuned, processor-specific, assembly-coded algorithm of the KMP
type or better. In which case you don't stand a chance of out-performing it in C
for such small benchmarks.
(The reason I think this is likely is that programmers love to implement such things.)