One of the most interesting things introduced in C++11 for me was constexpr. I can’t say that I use it a lot but maybe I should. While it’s mostly known for its ability to perform compile-time computations, constexpr also forces its computations to be pure functions - sure the syntax is not exactly Haskell, but it makes a huge difference in terms of ability to reason about and maintain invariants.
Being a huge fan of programming competitions, I still remember the first time seeing a table embedded in the C++ source with precomputed answers. At that moment I thought it was cheating, but since functions are really just a table representing with mapping from inputs to outputs, as long as we are able to represent it without having to do actual computations, why not?
But after accepting that solution as legit, the fact that the answers were hard-coded in the source file, still bothered me. And that’s where we can leverage the power of constexpr!
Let’s tackle the most boring and beaten-up problem - computing fibonacci numbers. It has numerous solutions ranging from super inefficient recursive, to iterative dynamic programmng and matrix multiplication using fast exponentiation. But since our goal is to not have any runtime overhead, the actual solution doesn’t matter, so let’s use a naive one based on its definition - fib(n) = fib(n-2) + fib(n-1)
. We’ll store our table in the precomputed array and index into the table in the fib
function.
And what’s so special about this? Well, let’s take a look at the assembly:
Fascinating! fib function simply copies the precomputed value from the binary and returns it! This means that we avoid all runtime overhead associated with computation and as such the complexity of the function doesn’t matter, as long as we are willing to sacrifice compile time. So magically super inefficient recursive way of computing fibonacci numbers below
produces the exact same assembly as above.
Sure this approach makes sense only for computations with limited range of inputs, but that’s exactly what we usually have to deal with when faced with exponential algorithms, making constexpr an even better candidate for consideration.