Sentinels Can Be Faster (lemire.me)

This is a rather weird article. Of course sentinels can be faster in some very particular algorithms. That's not the core contention. The core contention is that sentinels in general cause more speed losses than speed gains over the entirety of the application. Importantly, many useful algorithms such as string copying, string comparison, and string concatenation can be much more efficient using a size field.

This is really less “sentinels can be faster” and more “assuming invariants can be faster because you’re reducing comparisons”.

Any string representation is faster for some hand-picked task. But still, I think it's reasonable to assert that certain ones are better than others for general use.

I think most modern languages shifted towards slices due to security issues with sentinels. C++ span, rust, zig, go. It's very sad we need to use libc interfaces and deal with null terminated byte sequences.

Another classical example of sentinels is improving a linear search by inserting the key as the last element.

I put the benchmark into quick-bench but could not replicate the 40% result. The sentinel version was faster but only slightly.

https://quick-bench.com/q/314Z81FskTlcDqMCUHFVhWmDz8Q

Update 1: After moving some constants around, I get the 40% result:

https://quick-bench.com/q/lPrpQTAyDQuOoKS9MBWCTBXk1TE

No idea why it made such a big difference to the benchmark.

Update 2: If the test order is reversed, the result goes back to being only slightly faster for the sentinel version:

https://quick-bench.com/q/Ds7aqe5-6md_tTPndOK54ltYZmE

I never thought of null-termination as a "sentinel". I thought sentinel means strategically putting somewhere a value to avoid having to check for termination condition. Null-termination is not a sentinel, IMO. It is the opposite - terminator, which has to be explicitly checked for. Am I wrong here?

BTW. If you really want speed, SIMD will obliterate any non-SIMD solution, and my bet would be that most of the time SIMD will be easier to implement with length prefix because it will not have to handle a special case of null-termination. Someone correct me if I'm wrong.

Trailing zero is a a typical case of a short-signed hack. More naive, simpler, natural solution (length prefix) actually works better, especially long term, where other things change (hardware architecture, performance and resource constraint, use cases).

EDIT: Never mind, I mis-read the code in the blog...

    const char * skip_leading_spaces(const char * start) {
      while(is_space(*start)) {
        start++;
      }
      return start;
    }

This is not weird or theoretical.

Sometimes you find that in some complicated system, there's a big chunk of overhead which you spend just parsing things. So, carefully, thinking about the consequences, you can decide to use a sentinel for end of input rather than length.

A larger, practical example: a C++ compiler spends a shocking amount of time just doing lexical analysis on its inputs. One thing that Clang does to speed it up is to get rid of the length check, just like suggested in the article.

https://github.com/llvm-mirror/clang/blob/master/lib/Lex/Lex...

    /// LexTokenInternal - This implements a simple C family lexer.  It is an
    /// extremely performance critical piece of code.  This assumes that the buffer
    /// has a null character at the end of the file. [...]
    bool Lexer::LexTokenInternal(Token &Result, bool TokAtPhysicalStartOfLine) {
      [...]
      if ((*CurPtr == ' ') || (*CurPtr == '\t')) {
        ++CurPtr;
        while ((*CurPtr == ' ') || (*CurPtr == '\t'))
          ++CurPtr;
        [...]
      }
      [...]
    }

There are a number of places in the world where you might find that text parsing is performance-critical. Note that in the rest of the code base, Clang uses really quite standard and boring std::string to represent strings. You don't have to use sentinels everywhere, but it's a trick to keep up your sleeve for the cases where it makes a difference.

And of course, you keep the parts of your code with sentinels self-contained because it can be hard to figure out whether the code is correct without a close reading.

I really like Rust's approach of keeping string length in the pointer.

It allows making substrings without copying (and there's no costly substring gotcha you get in GC languages, because the borrow checker will loudly remind you when you try to keep the substring longer than the original string).

In string-processing algorithms the length usually stays in a register, so (unlike Pascal string approach) it doesn't contribute to on-heap cost of the string. Knowing length ahead of time allows having SIMD-optimized loops.