Eliminating branches in C++ loops - Yagiz Nizipli's blog<br>Skip to main content
*]:col-main max-w-none [&_p:has(img.col-wide)]:col-wide prose prose-neutral prose-tight dark:prose-invert marker:text-black dark:marker:text-white text-base leading-7 prose-headings:font-extrabold prose-headings:mt-6 prose-h1:text-3xl prose-h2:text-2xl prose-h3:text-xl prose-h3:text-neutral-600 dark:prose-h3:text-neutral-300 prose-strong:font-bold"> Suppose you want to check whether a string is made entirely of ASCII<br>lowercase letters. It is a common check in parsers. In Ada we do<br>this kind of classification constantly for URL characters: is this a<br>hex digit, an unreserved character, a forbidden host code point?
A reasonable function might look as follows.
The obvious validating loopbool is_ascii_lowercase(std::string_view input) {<br>for (unsigned char c : input) {<br>if (c 'a' || c > 'z') {<br>return false;<br>return true;<br>If any byte falls outside a-z, we return false. If the loop<br>finishes, we return true. Importantly, this function exits as soon as<br>a bad character is found.
If we expect that almost every input is valid, that early return can<br>be expensive. The CPU guesses which side of the if will run. When it<br>guesses wrong, you pay a pipeline flush. || and && make it worse<br>because they short-circuit: the second compare is itself a branch.
Daniel Lemire has a post on a similar problem:<br>checking whether a JSON string needs escaping. The structure is the<br>same. A loop, a branch, return true at the end. The rest of this<br>post follows the same ladder he uses there: scan the whole string,<br>replace the compare with a table, then do eight or sixteen bytes at<br>once.
Always cast the byte to unsigned char (or uint8_t) before you<br>classify it. A plain char may be signed, and a signed value above<br>127 can become a negative index or break the range check.
Scan the whole string
If we expect that no bad character will be found, we can always scan<br>the whole input. That lets the compiler try other optimizations. In<br>particular, it is more likely to autovectorize the loop: to compile it<br>using SIMD instructions on its own. Daniel calls this version<br>branchless, because it does not branch out of the loop.
Branchless accumulationbool is_ascii_lowercase(std::string_view input) {<br>bool ok = true;<br>for (unsigned char c : input) {<br>ok &= (c >= 'a') & (c 'z');<br>return ok;<br>& is not &&. Bitwise AND always evaluates both sides, so there is<br>no short-circuit branch. The loop body is load, compare, compare, and,<br>store. After the last byte we return the flag.
I prefer the dual form when I am looking for problems rather than<br>confirming that everything is valid. Accumulate errors with OR:
Branchless accumulation with ORbool is_ascii_lowercase(std::string_view input) {<br>unsigned errors = 0;<br>for (unsigned char c : input) {<br>errors |= static_cast(c 'a');<br>errors |= static_cast(c > 'z');<br>return errors == 0;<br>On x86 those compares compile to setcc. That is a flag write, not a<br>jump. The loop always runs to completion. That is what you want when<br>the happy path is that the whole string is fine, and it is what the<br>vectorizer wants to see.
We still have two comparisons per byte. We can do better.
One compare: the wraparound test
A byte is an ASCII lowercase letter if and only if it sits in<br>['a', 'z']. Subtract 'a' and that statement becomes “the result<br>fits in 0 to 25”.
Range check that wraps into a single unsigned comparestatic inline bool is_lower(unsigned char c) {<br>return static_cast char>(c - 'a') 25;<br>Let’s walk through a few values:
'a' - 'a' is 0, and 0 .
'z' - 'a' is 25, still in range.
'`' - 'a' wraps to 255, and 255 is false.
'{' - 'a' is 26, just outside.
'A' - 'a' wraps well above 25, so uppercase is rejected.
Bytes below 'a' underflow modulo 256 and land in the high end of the<br>unsigned char range, where they fail the same test as bytes<br>above 'z'. Two comparisons become one.
Validating a string with a wraparound predicatebool is_ascii_lowercase(std::string_view input) {<br>unsigned errors = 0;<br>for (unsigned char c : input) {<br>errors |= static_cast(<br>static_cast char>(c - 'a') > 25);<br>return errors == 0;<br>The body is now subtract, compare, or. There is no if, no return in<br>the middle, and no ||. For a single closed interval like a-z, this<br>is usually as far as scalar code needs to go.
The wraparound test only works for one interval. Hex digits, unreserved<br>URL characters, and forbidden host code points are unions of ranges<br>and punctuation. Bitwise arithmetic gets ugly there. A table does not.
A 256-byte lookup table
A simple way to classify a byte is to generate a 256-element array and<br>look the value up. Daniel calls this memoization (and not<br>memorization). You will sometimes hear “a table of size 255”. The last<br>valid index of an 8-bit value is 255, but the length of the array is<br>256 . Byte values run from 0x00 through 0xFF inclusive. A table<br>of 255 entries leaves 0xFF unmapped.
Using C++17, you can have the compiler build the array at compile time<br>from a lambda:
Build a...