I came across a really cool use of C++ templates that I hadn't seen before - optimizing out branch instructions.

I discovered it while watching a recorded tech talk from Drew Paroski, who apparently is a rather well-known Facebook engineer. Drew only briefly mentions the design pattern, and shows a single slide on it.

Drew starts talking about templates at 18:14. The very next slide is the one we care about, which is at 19:03. What he shows is an example of how to use C++ templates to optimize out branch instructions.

Here is the example he gives:

Let's start with a basic function, as you might normally write it, that contains a conditional:

void foo(bool b) {  
    if (b) {
        bar();
    }
    /* Other stuff */
}

When this gets compiled down to machine code, it will turn into something that looks like this (psuedo code):

test condition b  
if result is false, jump to label L1  
call function bar  
label L:  
...

Pretty straight-forward. But, check it out. If you templatize the function:

template <bool b> void foo() {  
    if (b) {
        bar();
    }
}

Then the compiled code is either nothing, or just call function bar. How does this work?

Remember that C++ templates are really just a form of meta-programming. So when you write templated code, you aren't writing 'normal C++ code', persay, but rather you are telling the compiler how to write C++ code for you.

So, when the compiler comes across that bit of templated code above, if b is true, then the compiler will 'write' this code for you:

void foo() {  
    bar()
    /* Other stuff */
}

Remember, when it evaluates the template, it knows if b is true or false, so it will know to either always call bar(), or to never call it. If b is false, then the compiler just optimizes the call to bar() away entirely, and you are simply left with the rest of the function.

Pretty slick!

Recommended Reading

If you enjoy learning stuff like this, I highly recommend the C++ books by Scott Meyers. A great one to start with is Effective C++: 55 Specific Ways to Improve Your Programs and Designs.