Re: [boost] [math] pow redux and observations

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.