Faster meta-programs using gcc 4.5 and C++0x

One of the practical issues with C++ meta-programming is its speed. C++ programs that use heavy meta-programming can be notoriously slow to compile on contemporary compilers. Things are changing, however. Check the following comparison of gcc 4.5 against gcc 4.4.3.
The first graph is obtained from a program that creates a binary tree of template instantiations. The x-axis shows the number of instantiations when value of N goes from 8 to 17. I could not build up patience for gcc 4.4.3 beyond 16363 instantiations (N=13). On the other hand, gcc 4.5 does pretty good and its increase in compilation time is indeed linear as mentioned here. Here is the program that creates a binary tree of template instantiations.

template <int Depth, int A, typename B>
struct Binary 
{
  enum { value = 1 +
         Binary<depth-1, 0, Binary>::value +
         Binary<depth-1, 1, Binary>::value };
};

template<int a, typename B>
struct Binary<0, A, B> 
{
  enum { value = 1 };
};

int main(void) 
{
  static const int N = 10;
  const int instantiations = Binary<N,0,int>::value;
}

The second graph is obtained from a program that finds an intersection of two MPL vectors. Again gcc 4.5 shows linear increase in compilation time as opposed to gcc 4.4.3. Here is the intersection program.

template <class V1, class V2>
struct Intersection 
{
  typedef typename
     boost::mpl::copy_if<V1,
     boost::mpl::contains<V2, boost::mpl::placeholders::_1> >::type type;
};

While all that is already exciting, it fades in comparison to the performance of variadic templates in C++0x. The green line in the second graph shows negligible effect on performance with the increasing number of template parameters. Here is my intersection metaprogram using variadic templates.

struct null_type {};
template <typename... Arg> struct vector {};

template <typename V> struct front;
template <typename V> struct pop_front;

template <typename Head, typename... Tail>
struct front <vector <Head, Tail...> > 
{
  typedef Head type;
};

template <>
struct front <vector <> > 
{
  typedef null_type type;
};

template <typename Head, typename... Tail>
struct pop_front <vector <Head, Tail...> > 
{
  typedef vector<Tail...> type;
};

template <>
struct pop_front <vector <> > 
{
  typedef vector<> type;
};

template <typename Vector, typename T> struct push_back;

template <typename T, typename... Args>
struct push_back < vector<Args...>, T> 
{
  typedef vector<Args..., T> type;
};

template <typename Vector> struct size;

template <typename... Args>
struct size <vector <Args...> > 
{
  typedef size type;
  enum { value = sizeof...(Args) };
};

template <typename Vector, typename What> struct contains;

template <typename What, typename Head, typename... Tail>
struct contains < vector<Head, Tail...>, What> : 
  std::conditional < std::is_same<Head, What>::value,
                     std::true_type,
                     contains < vector<Tail...>, What> >::type
{
  typedef contains type;
};

template <typename What>
struct contains <vector<>, What> 
{
  typedef contains type;
  enum { value = 0 };
};

template <class V1, class V2>
struct Intersection;

template <class V1, class V2, unsigned int N>
struct Intersection_impl
{
  typedef typename front<V2>::type Head;
  typedef typename pop_front<V2>::type Tail;
  typedef typename Intersection<V1, Tail>::type I;

  typedef typename 
    std::conditional<contains<V1, Head>::value,
                     typename push_back<I, Head>::type,
                     I >::type type;
};

template <class V1, class V2>
struct Intersection_impl <V1, V2, 0> 
{
  typedef vector<> type;
};

template <class V1, class V2>
struct Intersection 
{
  typedef typename Intersection_impl<V1, V2, 
          size<V1>::value * size<V2>::value>::type type;
};

So long story short, seems like better days are ahead for C++ meta-programming!