17.3 A Second Example: Computing the Square Root

Ru-Brd

Lets look at a slightly more complicated example: a metaprogram that computes the square root of a given value N . The metaprogram looks as follows (explanation of the technique follows ):

  // meta/sqrt1.hpp  #ifndef SQRT_HPP  #define SQRT_HPP  // primary template to compute  sqrt(N)  template <int N, int LO=1, int HI=N>  class Sqrt {    public:  // compute the midpoint, rounded up  enum { mid = (LO+HI+1)/2 };  // search a not too large value in a halved interval  enum { result = (N<mid*mid) ? Sqrt<N,LO,mid-1>::result                                  : Sqrt<N,mid,HI>::result };  };  // partial specialization for the case when  LO  equals  HI  template<int N, int M>  class Sqrt<N,M,M> {    public:      enum { result=M};  };  #endif  // SQRT_HPP  

The first template is the general recursive computation that is invoked with the template parameter N (the value for which to compute the square root) and two other optional parameters. The latter represent the minimum and maximum values the result can have. If the template is called with only one argument, we know that the square root is at least one and at most the value itself.

Our recursion then proceeds using a binary search technique (often called method of bisection in this context). Inside the template, we compute whether result is in the first or the second half of the range between LO and HI . This case differentiation is done using the conditional operator ? : . If mid ² is greater than N , we continue the search in the first half. If mid ² is less than or equal to N , we use the same template for the second half again.

The specialization that ends the recursive process is invoked when LO and HI have the same value M , which is our final result .

Again, let's look at the details of a simple program that uses this metaprogram:

  // meta/sqrt1.cpp  #include <iostream>  #include "sqrt1.hpp"  int main()  {      std::cout << "Sqrt<16>::result = " << Sqrt<16>::result                << '\n';      std::cout << "Sqrt<25>::result = " << Sqrt<25>::result                << '\n';      std::cout << "Sqrt<42>::result = " <<Sqrt<42>::result                << '\n';      std::cout << "Sqrt<1>::result =  " << Sqrt<1>::result                << '\n';  } 

The expression

 Sqrt<16>::result 

is expanded to

 Sqrt<16,1,16>::result 

Inside the template, the metaprogram computes Sqrt<16,1,16>::result as follows:

 mid = (1+16+1)/2      = 9  result = (16<9*9) ? Sqrt<16,1,8>::result                    : Sqrt<16,9,16>::result         = (16<81) ? Sqrt<16,1,8>::result                   : Sqrt<16,9,16>::result         = Sqrt<16,1,8>::result 

Thus, the result is computed as Sqrt<16,1,8>::result , which is expanded as follows:

 mid = (1+8+1)/2      = 5  result = (16<5*5) ? Sqrt<16,1,4>::result                    : Sqrt<16,5,8>::result         = (16<25) ? Sqrt<16,1,4>::result                   : Sqrt<16,5,8>::result         = Sqrt<16,1,4>::result 

And similarly Sqrt<16,1,4>::result is decomposed as follows:

 mid = (1+4+1)/2      = 3  result = (16<3*3) ? Sqrt<16,1,2>::result                    : Sqrt<16,3,4>::result         = (16<9) ? Sqrt<16,1,2>::result                  : Sqrt<16,3,4>::result         = Sqrt<16,3,4>::result 

Finally, Sqrt<16,3,4>::result results in the following:

 mid = (3+4+1)/2      = 4  result = (16<4*4) ? Sqrt<16,3,3>::result                    : Sqrt<16,4,4>::result         = (16<16) ? Sqrt<16,3,3>::result                   : Sqrt<16,4,4>::result         = Sqrt<16,4,4>::result 

and Sqrt<16,4,4>::result ends the recursive process because it matches the explicit specialization that catches equal high and low bounds. The final result is therefore as follows:

 result = 4 

Tracking All Instantiations

In the preceding example, we followed the significant instantiations that compute the square root of 16. However, when a compiler evaluates the expression

 (16<=8*8) ? Sqrt<16,1,8>::result            : Sqrt<16,9,16>::result 

it not only instantiates the templates in the positive branch, but also those in the negative branch ( Sqrt<16,9,16> ). Furthermore, because the code attempts to access a member of the resulting class type using the :: operator, all the members inside that class type are also instantiated . This means that the full instantiation of Sqrt<16,9,16> results in the full instantiation of Sqrt<16,9,12> and Sqrt<16,13,16> . When the whole process is examined in detail, we find that dozens of instantiations end up being generated. The total number is almost twice the value of N .

This is unfortunate because template instantiation is a fairly expensive process for most compilers, particularly with respect to memory consumption. Fortunately, there are techniques to reduce this explosion in the number of instantiations. We use specializations to select the result of computation instead of using the condition operator ?: . To illustrate this, we rewrite our Sqrt metaprogram as follows:

  // meta/sqrt2.hpp  #include "ifthenelse.hpp"  // primary template for main recursive step  template<int N, int LO=1, int HI=N>  class Sqrt {    public:  // compute the midpoint, rounded up  enum { mid = (LO+HI+1)/2 };  // search a not too large value in a halved interval  typedef typename IfThenElse<(N<mid*mid),                                  Sqrt<N,LO,mid-1>,                                  Sqrt<N,mid,HI> >::ResultT              SubT;      enum { result = SubT::result };  };  // partial specialization for end of recursion criterion  template<int N, int S>  class Sqrt<N, S, S> {    public:      enum { result = S };  }; 

The key change here is the use of the IfThenElse template, which was introduced in Section 15.2.4 on page 272:

  // meta/ifthenelse.hpp  #ifndef IFTHENELSE_HPP  #define IFTHENELSE_HPP  // primary template: yield second or third argument depending on first argument  template<bool C, typename Ta, typename Tb>  class IfThenElse;  // partial specialization:  true  yields second argument  template<typename Ta, typename Tb>  class IfThenElse<true, Ta, Tb> { 

 public:      typedef Ta ResultT;  };  // partial specialization:  false  yields third argument  template<typename Ta, typename Tb>  class IfThenElse<false, Ta, Tb> {    public:      typedef Tb ResultT;  };  #endif  // IFTHENELSE_HPP  

Remember, the IfThenElse template is a device that selects between two types based on a given Boolean constant. If the constant is true, the first type is typedef ed to ResultT ; otherwise , ResultT stands for the second type. At this point it is important to remember that defining a typedef for a class template instance does not cause a C++ compiler to instantiate the body of that instance. Therefore, when we write

 typedef typename IfThenElse<(N<mid*mid),                              Sqrt<N,LO,mid-1>,                              Sqrt<N,mid,HI> >::ResultT          SubT; 

neither Sqrt<N,LO,mid-1> nor Sqrt<N,mid,HI> is fully instantiated. Whichever of these two types ends up being a synonym for SubT is fully instantiated when looking up SubT::result . In contrast to our first approach, this strategy leads to a number of instantiations that is proportional to log ₂ ( N ): a very significant reduction in the cost of metaprogramming when N gets moderately large.

Ru-Brd