Lower cpu usage on searching a big char array
I'm searching for few bytes in a char array. The problem is that on slower machines the process gets up to 90%+ cpu usage. How to prevent that? My code is:
for(long i = 0; i < size - 5; ) {
if (buff[++i] == 'f' && buff[++i] == 'i' && buff[++i] == 'l' && buff[++i] == 'e') {
printf("found at: %d\n", i);
开发者_开发知识库 }
}
EDIT: The string "file" is not null-terminated.
This looks like an attempt at very naive string search, I'd suggest you use either the standard functions provided for this purpose (like strstr) and/or research string search algorithms like Boyer-Moore.
The linked Wikipedia article on Boyer-Moore shows quite well why moving along one character at a time on a mismatch (like you do) is not necessary - it's an interesting read.
EDIT: also look at this page, it has a nice animated presentation that shows how BM does its job.
EDIT2: regarding the string not being nullterminated: either you
buff[size] = 0;
terminate it yourself, and use strstr, or you have a look at the BM code from the page I linked, that works with lengths, ie it will work with strings without terminating 0.
There is nothing wrong with getting 90% utilisation, since the algorithm is CPU-bound. But...
Unless you expect the search term to be on a 32-bit word boundary, the code is broken. If the word 'file' begins on the second character of the buffer, you will simply skip over it. (EDIT: Short-circuit eval means the code is correct as it stands. My mistake.)
Don't roll your own code for this; use strstr
.
Try just storing a list of values where 'file' is found and print them out after the loop. It will prevent context switches and will enable the CPU to use the cache better. Also put i in a register.
精彩评论