C++11 constexpr function compiler error with terna

问题:

What is wrong with this piece of code?

#include <iostream>

template<unsigned int N, unsigned int P=0>
constexpr unsigned int Log2() {
    return (N <= 1) ? P : Log2<N/2,P+1>();
}

int main()
{
    std::cout << "Log2(8) = " << Log2<8>() << std::endl;
    return 0;
}

When compiling with gcc version 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5), I get the following error:

log2.cpp: In function ‘constexpr unsigned int Log2() [with unsigned int N = 0u, unsigned int P = 1023u]’:
log2.cpp:5:38: error: template instantiation depth exceeds maximum of 1024 (use -ftemplate-depth= to increase the maximum) instantiating ‘constexpr unsigned int Log2() [with unsigned int N = 0u, unsigned int P = 1024u]’
log2.cpp:5:38:   recursively instantiated from ‘constexpr unsigned int Log2() [with unsigned int N = 4u, unsigned int P = 1u]’
log2.cpp:5:38:   instantiated from ‘constexpr unsigned int Log2() [with unsigned int N = 8u, unsigned int P = 0u]’
log2.cpp:10:37:   instantiated from here

回答1:

Constexpr doesn't work that way.

Simply put, constexpr functions must be available as runtime functions too. Imagine you took the constexpr off the function. Then think about why it cannot possibly work.

The reason is that the compiler has to instantiate the body of the function completely; it cannot decide based on the condition in the ?: not to instantiate one side. So it always has to instantiate the recursive call, leading to infinite recursion.

In any case, you're using constexpr wrong. You're using the old template metaprogramming calculation technique (passing stuff as template parameters) when constexpr was intended to replace this. Just use normal parameters.

constexpr unsigned Log2(unsigned n, unsigned p = 0) {
    return (n <= 1) ? p : Log2(n / 2, p + 1);
}

std::cout << "Log2(8) = " << Log2(8) << std::endl;

Edit: I'll try to elaborate on how this works.

When the compiler encounters your code, it parses the template function and stores it in template form. (How this works differs between compilers.) So far, all is fine.

Next, in main, the compiler sees the call Log2<8>(). It sees that it has to instantiate the template, so it goes ahead and does exactly that: it instantiates Log2<8, 0>. The body of the function template is this:

return (N <= 1) ? P : Log2<N/2,P+1>();

OK, the compiler sees this, but it doesn't try to evaluate it. Why would it? It's currently instantiating a template, not calculating a value. It just substitutes the values supplied:

return (8 <= 1) ? 0 : Log2<8/2,0+1>();

Huh, there's another template instantiation here. It doesn't matter that it's in a conditional expression, or that the left hand side could be known. Template instantiation must be complete. So it goes ahead and calculates the values for the new instantiation and then instantiates Log2<4, 1>:

return (4 <= 1) ? 1 : Log2<4/2,1+1>();

And the game begins again. There's a template instantiation in there, and it's Log2<2, 2>:

return (2 <= 1) ? 2 : Log2<2/2,2+1>();

And again, Log2<1,3>():

return (1 <= 1) ? 3 : Log2<1/2,3+1>();

Did I mention that the compiler doesn't care about the semantic meaning of this stuff? It's just yet another template to instantiate: Log2<0,4>:

return (0 <= 1) ? 4 : Log2<0/2,4+1>();

And then Log2<0,5>:

return (0 <= 1) ? 5 : Log2<0/2,5+1>();

And so on, and so on. At some point the compiler realizes that it never stops, and gives up. But at no point does it say, "Wait, the condition of that ternary operator is false, I don't need to instantiate the right-hand side." That's because the C++ standard doesn't allow it to. The function body must be instantiated completely.

Now look at my solution. There's no template. There's just a function. The compiler sees it and goes, "Hey, here's a function. Awesome, let me put in a call to that function here." And then at some point (it might be immediately, it might be a lot later, depending on the compiler), it might (but is not forced to, in this case) say, "Hey, wait, this function is constexpr and I know the parameter values, let me evaluate that." Now it goes ahead and evaluates Log2(8, 0). Remember the body:

return (n <= 1) ? p : Log2(n / 2, p + 1);

"OK", the compiler says, "I just want to know what this function returns. Let's see, 8 <= 1 is false, so look at the right side. Log2(4, 1), huh? Let me look at that. OK, 4 <= 1 is also false, so it must be Log2(2, 2). What's that, 2 <= 1? Also false, so it's Log2(1, 3). Hey, 1 <= 1 is true, so let me take that 3 and return it. All the way up the call stack."

So it comes up with the answer 3. It doesn't go into endless recursion because it's evaluating the function with full knowledge of values and semantics, not just stupidly building up ASTs.

I hope that helps.

回答2:

As others already said: The compiler won't evaluate a conditional expression such as if/else or a ternary operator ?:. However, there is still a way to make this conditional expression compile time:

#include <cstddef>     // size_t is shorter than unsigned int, it's a matter of taste in this case
#include <iostream>    // to show our results
#include <type_traits> // needed for the mighty std::enable_if

template<size_t N, size_t P = 0>
constexpr typename std::enable_if<(N <= 1), size_t>::type Log2()
{
   return P;
}

template<size_t N, size_t P = 0>
constexpr typename std::enable_if<!(N <= 1), size_t>::type Log2()
{
   return Log2<N / 2, P + 1>();
}

int main()
{
   std::cout << Log2<1>() << "\n";
   std::cout << Log2<2>() << "\n";
   std::cout << Log2<4>() << "\n";
   std::cout << Log2<8>() << "\n";
   std::cout << Log2<16>() << "\n";
}

What this does is rather obvious: If N <= 1, the first branch should be evaluated, thus Log2<0, P>() and Log2<1, P>() should evaluate to P. If N <= 1, the upper method is enabled as this function header is valid. For everything else, i.e. N >= 2 or !(N <= 1), we need to recurse, which is done by the second method.