From: John Maddock (john_at_[hidden])
Date: 2008-05-20 13:28:57
John Moeller wrote:
> Can it be proportionally difficult for a compiler to inline a series
> of nested function calls the deeper the calls go?
Probably yes.
> If the answer to this question is "yes," it may be advantageous to
> alter the base template of positive power from this:
>
> template <int N, bool odd>
> struct positive_power
> {
> template <typename T>
> static typename tools::promote_args<T>::type result(T base)
> {
> return base*positive_power<N-1, (N-1)%2>::result(base);
> }
> };
>
> to this:
>
> template <int N, bool odd>
> struct positive_power
> {
> template <typename T>
> static typename tools::promote_args<T>::type result(T base)
> {
> return base*positive_power<2, false>::result(
> positive_power<N/2, (N/2)%2>::result(base));
> }
> };
>
> The reason is that for pow<31>, the first generates calls that go 8
> deep with 3 2/F calls:
>
> 31/T, 30/F, 15/T, 14/F, 7/T, 6/F, 3/F, 2/F
>
> while the second generates calls that go 5 deep with 4 2/F calls:
>
> 31/T, 15/T, 7/T, 3/T, 1/T
>
> The second generates one more 2/F call than the first, but the 2/F
> calls don't add to the depth of the call; they're sibling calls to
> the recursive calls. This may only be a minor problem for builtin
> types, but I could see this being a problem for a
> "mod-multiplication" type, for example, that can raise numbers to
> high powers.
Right, and it also reduces the number of template instantiations needed?
Looks like an excellent idea to me,
Regards, John.