C ++ support for optimizing the last call in template metaprogramming

Question

I am reading about C ++ templates and would like to compare two different implementations of a function that calculates the sum from 0 to N.

Unfortunately, I have problems and would like to consider a few questions with examples:

Naive amount code:

#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 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 improvement is to use a battery:

 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 compiling with simple g ++ on an Ubuntu OS:

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

Hence my main problem:

Does any modern C ++ compiler support the latest call optimization for the metaprogramming pattern? If so, what is the way to write code for such an optimization?

Answer 1

Does any modern C ++ compiler support the latest call optimization for metaprogramming templates? If so, what is the way to write code for such an optimization?

No, and that doesn't make sense. Template instances are not functional calls ... Last / tail call optimization is not relevant here. Unlike function calls, template instances are not transitory with automatic variables for recovery; rather, each instance of the template becomes a new type in compiler state.

Answer 2

The whole point of metaprogramming templates is that all these “calls” will be optimized from your program; they are "executed" during assembly.

This does not change the fact that there is a certain implementation limit for the amount of recursion that you can use during this process. This is the limit that you have inflicted.

So no, there is no “optimization” to get around it.

Answer 3

Short answer: enabling LCO is not worth the trouble .

More detailed explanation:

C ++ template meta programming is Turing Complete. It is theoretically possible to compute any computable function at compile time using templates only (if enough resources have been provided). LCO will make such calculations more efficient.

This does not mean that templates should be used for complex calculations. For this, the start time is used. C ++ templates simply help to avoid writing identical code.

In fact, performing complex calculations using templates is not recommended because they have little compiler support. The preprocessor will only expand the boilerplate code to more code and it. When processing templates, type checking does not occur, etc.

So, I think that C ++ developers have more interesting things to add a language, rather than optimize template meta-programming. Perhaps in 20 years we will support the LCO. Not at present.