Using sentinel for string manipulation

Suppose you have a null-terminating string, and its length is stored in a variable (so called fucked string). The function is looking for a character in the string.

Naive implementation

const char* memchr_naive(const char* s, int ch, size_t len) {
   const char* end = s + len;
   for(; s < end; s++)
      if(*s == ch)
         return s;
   return NULL;
}

Sentinel implementation

There is a better way to do it: temporarily replace the terminating null with the searched character. It will be a "sentinel". Now the program can do one comparison on each iteration instead of two. After the loop, we should check if we found the sentinel or a character in the string:

char* memchr_sentinel(char* s, int ch, size_t len) {
   char* sentinel = (char*)(s + len);
   *sentinel = (char)ch;
   while(*s != ch)
      s++;
   *sentinel = '\0';
   return (s < sentinel) ? s : NULL;
}

This method is 5-30% faster. With loop unrolling and vectorizing tricks by Agner Fog, it shows even better results for long strings:

Conclusion

You can use the sentinel method not only for memchr, but also for string search and array search functions. The main limitation is that there should be enough space for the sentinel after the end of the string. The string should be located in a writeable section of exe file (it cannot be "const"!).

Dowload the code (30 KB)