Re:Sentinels Can Be Faster
by klodolph on Wednesday September 09, 2020 @08:24PM
(#24427584)
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.
/// 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.
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...
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.