Abstract:
A method for optimizing search functions.

Created by Peter Kankowski
Last changed
Contributors: Centaur
Filed under Low-level code optimization

Share on social sitesReddit Digg Delicious Buzz Facebook Twitter

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:

Time in clock cycles
for short stringsfor long string
CRT12801560
naive15002670
sentinel14302130
sentinel unrolled13701430
sentinel vectorized13801180
sentinel vectorized asm15501160

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)

Peter Kankowski
Peter Kankowski

About the author

Peter is the developer of Aba Search and Replace, a tool for replacing text in multiple files. He likes to program in C with a bit of C++, also in x86 assembly language, Python, and PHP. He can be reached at kankowski@gmail.com.

Created by Peter Kankowski
Last changed
Contributors: Centaur

5 comments

Centaur,

You forgot to mention one strong counter-indication for this technique: multithreading. If two threads try to search one string for different characters more or less simultaneously, they will fight for the sentinel post. The last one to put the sentinel wins. The loser walks off the string end, all the way into undefined behavior.

Peter Kankowski,

Centaur, thank you for the idea. I agree that this optimization should not be used if several threads access the string.

Nils,

I just tried to submit a comment and it didn't made it through the network. Don't worry, it wasn't that important.

But I wonder: Am I the only one who has problems posting comments? It takes ages (and lots of timeouts) to see my post once I pressed the "Submit Comment"-Button.

Peter Kankowski,

I experienced timeouts myself :(. Weblogs.us is a hobbyist project, so they often have problems with their servers, but they usually solve them within several hours. The main reason to use their hosting was much higher level of customization than with any commercial service (for example, I added C/C++ code highlight, installed several Wordpress plugins, etc.)

I will think about switching to another hosting if the performance problems will continue. Thank you for reporting them.

Rolland,

This is plain wrong.

The string passed in argument is const char, so should not be modified.If the string happens to be placed in some read-only memory, this is going to basically crash (or in the best case, not work as expected).

Also, you did mention that this will work on a NULL-terminated string ; if len happens to be the size of a buffer but the string is actually much smaller than len, this is going to be less efficient than the naive implementation. And of course, this new memchr_sentinel will not work on substrings...

Your name:


Comment:


Please ignore this field: