Exponential compilation times with simple typelist implementation. Why?

user_791744 0
Viewed 145

I am trying my hand at C++ type lists. Below is a trivial implementation of a type list filter function. It seems to work except that compilation times in both gcc and clang are horrific beyond say 18 elements. I was wondering what improvements I could make to make this practical.

#include <type_traits>

// a type list
template <class... T> struct tl ;

// helper filter for type list 
template <class IN_TL, class OUT_TL, template <typename> class P>
struct filter_tl_impl;

// Base case
template <class... Ts, template <typename> class P>
// If the input list is empty we are done
struct filter_tl_impl<tl<>, tl<Ts...>, P> {
  using type = tl<Ts...>;
};

// Normal case
template <class Head, class... Tail, class... Ts2, template <typename> class P>
struct filter_tl_impl<tl<Head, Tail...>, tl<Ts2...>, P> {
  using type = typename std::conditional<
      // Does the predicate hold on the head of the input list?
      P<Head>::value,
      // The head of the input list matches our predictate, copy it
      typename filter_tl_impl<tl<Tail...>, tl<Ts2..., Head>, P>::type,
      // The head of the input list does not match our predicate, skip
      // it
      typename filter_tl_impl<tl<Tail...>, tl<Ts2...>, P>::type>::type;
};

template <class TL, template <typename> class P> struct filter_tl {
  using type = typename filter_tl_impl<TL, tl<>, P>::type;
};

// Test code
using MyTypes = tl<
   char*, bool, char, int, long, void,
   char*, bool, char, int, long, void,
   char*, bool, char, int, long, void
   >;


using MyNumericTypes = filter_tl<MyTypes, std::is_arithmetic>::type;

static_assert(std::is_same < MyNumericTypes,
              tl<
              bool,char,int,long,
              bool,char,int,long,
              bool,char,int,long
              >> :: value);

int main(int, char **) {}
variadic-templates template-meta-programming c++
4 Answers
using type = typename std::conditional<
      // Does the predicate hold on the head of the input list?
      P<Head>::value,
      // The head of the input list matches our predictate, copy it
      typename filter_tl_impl<tl<Tail...>, tl<Ts2..., Head>, P>::type,
      // The head of the input list does not match our predicate, skip
      // it
      typename filter_tl_impl<tl<Tail...>, tl<Ts2...>, P>::type>::type;

instantiates both sides because of ::type.

You might delay intermediate instantiation by after the std::conditional:

using type = typename std::conditional<
      // Does the predicate hold on the head of the input list?
      P<Head>::value,
      // The head of the input list matches our predicate, copy it
      filter_tl_impl<tl<Tail...>, tl<Ts2..., Head>, P>,
      // The head of the input list does not match our predicate, skip
      // it
      filter_tl_impl<tl<Tail...>, tl<Ts2...>, P>>::type::type;

Which leads to linear number of instantiations instead of exponential.

user_26845390

If you want lists, the first thing you do is define the cons function. The rest becomes natural and straightforward.

// first, define `cons`      
  template <class Head, class T> struct cons_impl;
  template <class Head, class ... Tail>
  struct cons_impl <Head, tl<Tail...>> {
     using type = tl<Head, Tail...>;
  };
  template <class Head, class T>
  using cons = typename cons_impl<Head, T>::type;

// next, define `filter`
  template <template <typename> class P, class T>
  struct filter_tl_impl;
  template <template <typename> class P, class T>
  using filter_tl = typename filter_tl_impl<P, T>::type;

// empty list case      
  template <template <typename> class P>
  struct filter_tl_impl<P, tl<>> {
    using type = tl<>;
  };
  
// non-empty lust case
  template <template <typename> class P, class Head, class ... Tail>
  struct filter_tl_impl<P, tl<Head, Tail...>> {
    using tailRes = filter_tl<P, tl<Tail...>>;
    using type = std::conditional_t<P<Head>::value,
                                    cons<Head, tailRes>,
                                    tailRes>;
  };

Note tailRes is defined for readability only, you can write directly

    using type = std::conditional_t<P<Head>::value,
                                    cons<Head, filter_tl<P, tl<Tail...>>>,
                                    filter_tl<P, tl<Tail...>>>;

and compilation time remains negligible.

user_7758060

A possible alternative could be insert the std::conditional inside the filter_tl_impl.

I mean

// Normal case
template <typename Head, typename... Tail, typename... Ts2,
          template <typename> class P>
struct filter_tl_impl<tl<Head, Tail...>, tl<Ts2...>, P>
 {
   using type = typename filter_tl_impl<tl<Tail...>,
                                        std::conditional_t<
                                           P<Head>::value,
                                           tl<Ts2..., Head>,
                                           tl<Ts2...>>,
                                        P>::type;
};
user_60226560

And now, for something completely different...

I propose to split your "normal case" (the recursive case) in two different cases: the case "true" and the case "false".

Unfortunately, this require an additional custom type traits check_first

template <typename, template <typename> class>
struct check_first : public std::false_type
 { };

template <typename H, typename ... T, template <typename> class P>
struct check_first<tl<H, T...>, P>
   : public std::integral_constant<bool, P<H>::value>
 { };

Now you can write filter_tl_impl as follows

// declaration and ground case
template <typename I, typename O, template <typename> class P,
          bool = check_first<I, P>::value>
struct filter_tl_impl
 { using type = O; };

// recursive-positive case
template <typename H, typename... T, typename... Ts,
          template <typename> class P>
struct filter_tl_impl<tl<H, T...>, tl<Ts...>, P, true>
   : public filter_tl_impl<tl<T...>, tl<Ts..., H>, P>
 { };

// recursive-negative case
template <typename H, typename... T, typename... Ts,
          template <typename> class P>
struct filter_tl_impl<tl<H, T...>, tl<Ts...>, P, false>
   : public filter_tl_impl<tl<T...>, tl<Ts...>, P>
 { };

I've also rewritten filter_tl as a simpler using

template <typename TL, template <typename> class P>
using filter_tl = typename filter_tl_impl<TL, tl<>, P>::type;

so your original code become

#include <type_traits>

// a type list
template <typename...>
struct tl;

template <typename, template <typename> class>
struct check_first : public std::false_type
 { };

template <typename H, typename ... T, template <typename> class P>
struct check_first<tl<H, T...>, P>
   : public std::integral_constant<bool, P<H>::value>
 { };   

// declaration and ground case
template <typename I, typename O, template <typename> class P,
          bool = check_first<I, P>::value>
struct filter_tl_impl
 { using type = O; };

// recursive-positive case
template <typename H, typename... T, typename... Ts,
          template <typename> class P>
struct filter_tl_impl<tl<H, T...>, tl<Ts...>, P, true>
   : public filter_tl_impl<tl<T...>, tl<Ts..., H>, P>
 { };

// recursive-negative case
template <typename H, typename... T, typename... Ts,
          template <typename> class P>
struct filter_tl_impl<tl<H, T...>, tl<Ts...>, P, false>
   : public filter_tl_impl<tl<T...>, tl<Ts...>, P>
 { };

template <typename TL, template <typename> class P>
using filter_tl = typename filter_tl_impl<TL, tl<>, P>::type;

// Test code
using MyTypes = tl<char*, bool, char, int, long, void,
                   char*, bool, char, int, long, void,
                   char*, bool, char, int, long, void>;

using MyNumericTypes = filter_tl<MyTypes, std::is_arithmetic>;

static_assert(std::is_same_v<MyNumericTypes,
                             tl<bool, char, int, long,
                                bool, char, int, long,
                                bool, char, int, long>>);

int main ()
 { }
user_60226560
Related