Optimized version of strstr (search has constant length)

Answer 1

Your code may access cs beyond the bounds of its allocation if cs is shorter than 4 characters.

A common optimisation for string search is to use the Boyer-Moore algorithm where you start looking in cs from the end of what would be ct. See the linked page for a full description of the algorithm.

Answer 2

There are several fast string search algorithms. Try looking at Boyer-Moore (as already suggested by Greg Hewgill), Rabin-Karp and KMP algorithms.

If you need to search for many small patterns in the same large body of text, you can also try implementing a suffix tree or a suffix array. But these are IMHO somewhat harder to understand and implement correctly.

But beware, these techniques are very fast, but only give you an appreciable speedup if the strings involved are very large. You might not see an appreciable speedup for strings less than say a 1000 characters long.

EDIT:

If you are searching on the same text over and over again (i.e. the value of cs is always/often the same across calls), you will get a big speedup by using a suffix trie (Basically a trie of suffixes). Since your text is as small as 100 or 200 characters, you can use the simpler O(n^2) method to build the trie and then do multiple fast searches on it. Each search would require only 5 comparisons instead of the usual 5*200.

Edit 2:

As mentioned by caf's comment, C's strstr algorithm is implementations dependent. glibc uses a linear time algorithm which should be more or less as fast in practice as any of the methods I've mentioned. While the OP's method is asymptotically slower (O(N*m) instead of O(n) ), it is faster probably due to the fact that both n and m (the lengths of the pattern and the text) are very small and it does not have to do any of the long preprocessing in the glibc version.

Answer 3

Reducing the number of comparisons will increase the speed of the search. Keep a running int of the string and compare it to a fixed int for the search term. If it matches compare the last character.

uint32_t term = ct[0] << 24 | ct[1] << 16 | ct[2] << 8 | ct[3];
uint32_t walk = cs[0] << 24 | cs[1] << 16 | cs[2] << 8 | cs[3];
int i = 0;

do {
  if ( term == walk && ct[4] == cs[4] ) { return i; } // or return cs or 1
  walk = ( walk << 8 ) | cs[4];
  cs += 1;
  i += 1;
} while ( cs[4] ); // assumes original cs was longer than ct
// return failure

Add checks for a short cs.

Edit:

Added fixes from comments. Thanks.

This could easily be adopted to use 64 bit values. You could store cs[4] and ct[4] in local variables instead of assuming the compiler will do that for you. You could add 4 to cs and ct before the loop and use cs[0] and ct[0] in the loop.