Is TMP really faster if the recusion depth is very deep?

user_6543053 0
Viewed 116

I made a simple sqrt struct using TMP. It goes like :

template <int N, int i>
struct sqrt {
    static const int val = (i*i <= N && (i + 1)*(i + 1) > N) ? i : sqrt<N, i - 1 >::val;
};

but is causes error since it does not have the exit condition, so I added this :

template <int N>
struct sqrtM<N, 0> {
    static const int val = 0;
};

So as I understand it, in case we use TMP, the compiler goes into recursion loop until they meet the exit condition (in terms of sqrt, usally when i = 0 or i = 1)

But if we make a recursive sqrt function, compiler doesn't have to dive until it meets i = 0, because at some point, recursive function ends at exact location where condition (i*i <= N && (i + 1)*(i + 1) > N) is met.

So let's assume we put very large value into our sqrt, then our TMP should do extra computation of sqrt<N, sqrt<N-1>::val> compared to the recursive version of sqrt function, and it seems waste to me.

Am I getting it wrong? Or TMP is really worth it even in this kind of cases?

template-meta-programming c++
2 Answers

The thing is that in TMP you can't go very deep by default. The depth is limited but the limit can be changed (see this). The other thing is that you write your TMP code with recursion but it can be compiled into a non-recursive code so it doesn't have the extra cost of saving the state and doing a function call as it goes deeper. So it is a tradeoff between compile time, executable size and runtime performance. If your N is not known at compile time, then you can't use TMP.

user_59228540

There is a difference between evaluation and instantiation.

in

template <int N, int i>
struct sqrt {
    static const int val = (i*i <= N && (i + 1)*(i + 1) > N) ? i : sqrt<N, i - 1 >::val;
};

it should instantiate sqrt<N, i - 1 > to retrieve associated val, even if that value won't be taken at the end.

You can write code differently to delay instantiation of sqrt<N, i - 1 >

template <int N> struct val_identity { static const int val = N; };

template <int N, int i>
struct sqrt {
    static const int val =
        std::conditional_t<i * i <= N && N < (i + 1) * (i + 1),
                           val_identity<i>,
                           sqrt<N, i - 1 >
                          >::val;
};

Demo

user_26845390
Related