CODEWITHSUNDEEP
c++
mercury0114
mercury0114

Reputation: 1449

c++ support for last call optimization in template metaprogramming

I am reading about C++ templates and would like to contrast two different implementations of a function which computes sum from 0 to N.

Unfortunately, I have problems and would like to address a few questions through examples:

Code for naive sum:

#include <stdio.h>

template<int N>
struct Sum {
    // Copied the implementation idea from Scott Meyers book
    // "Effective C++". Is there a better way?
    enum { value = N + Sum<N - 1>::value };
};

template<>
struct Sum<0> {
    enum { value = 0 };
};

int main() {
    // Works well in this case, but gives compilation error, if
    // it's called with a larger value, such as 10000
    // (error: template instantiation depth exceeds maximum of 900").
    // How to improve the program properly, that it would
    // not give compile time error?
    printf("%d\n", Sum<100>::value);
}

Now my idea for an improvement is to use an accumulator:

template<int Acc, int N>
struct Sum {
    enum { value = Sum<Acc + N, N - 1>::value };
};

// Is that an appropriate way of writing the base case?
template<int Acc> 
struct Sum<Acc, 0> {
    enum { value = Acc };
};

However, when compiled with simple g++ on Ubuntu OS:

int main() {
    // Still gives the "depth exceeded" error.
    printf("%d\n", Sum<0, 1000>::value);
}

Hence, my main concern is:

Does any modern c++ compiler support last call optimisation for template metaprogramming? If yes, what is an appropriate way to write code for such optimisation?

Upvotes: 5

Views: 234

Answers (3)

mercury0114
mercury0114

Reputation: 1449

Short answer: incorporating LCO is not worth the trouble.

Longer explanation:

C++ template meta programming is Turing Complete. In theory it would be possible to compute any computable function at compile time using only templates (if enough resources were given). LCO would make such computation more efficient.

That does not mean templates should be used for sophisticated computations. Run time is for that. C++ templates merely aid to avoid writing identical code.

In fact, doing complicated computation through templates is discouraged, because one has little compiler support. The preprocessor will only expand templated code into more code and that's it. No type checking, etc. is happening when processing templates.

So I think the designers of c++ have more interesting things to add in the language rather than optimise template meta programming. Maybe after 20 years we will have LCO support. Currently there is no.

Upvotes: 0

Tony Delroy
Tony Delroy

Reputation: 106076

Does any modern c++ compiler support last call optimisation for template metaprogramming? If yes, what is an appropriate way to write code for such optimisation?

No, and it wouldn't make sense. Template instantiations are not function calls... last/tail call optimisation has no relevance here. Unlike function calls, template instantiations are not transient with automatic variables to reclaim; rather, each template instantiation becomes a new type in the compiler's state.

Upvotes: 1

Lightness Races in Orbit
Lightness Races in Orbit

Reputation: 385108

The whole point of template metaprogramming is that all of these "calls" will be optimised out of your program; they are "executed" during the build.

That doesn't change the fact that there is an implementation-defined limit to the amount of recursion you can use during this process. This is the limit you've hit.

So, no, there's no "optimisation" to work around it.

Upvotes: 0

Related Questions