# Template metaprogramming: Iteration is better than recursion

Thanks to Jeff Trull for this example of metaprogramming. Our goal is to make a filter metafunction that takes a typelist and returns a new typelist with all non-matching elements filtered out. Here’s our unit test:

using Input = std::tuple<int, int&, char, char&>;
using Output = std::tuple<int&, char&>;
static_assert(std::is_same_v<
filter<std::is_reference, Input>::type,
Output
>);


And here’s our original metaprogram (courtesy of Jeff). Most C++11 metaprograms, in my experience, end up looking something like this. There’s a forward declaration of filter, and then a recursive case, and then a base case. Classic recursion.

//
// Filter types in a std::tuple by a template "predicate"
//

template<template<class> class Pred, class Sequence>
struct filter;

// recursive case
template<template<class> class Pred, class H, class... Ts>
struct filter<Pred, std::tuple<H, Ts...>> {
using type = std::conditional_t<
Pred<H>::value,
decltype(std::tuple_cat(
std::declval<std::tuple<H>>(),
std::declval<typename filter<Pred, std::tuple<Ts...>>::type>()
)),
typename filter<Pred, std::tuple<Ts...>>::type
>;
};

// base case
template<template<class> class Pred>
struct filter<Pred, std::tuple<>> {
using type = std::tuple<>;
};


I observe that calling conditional_t<B, T, F> always fully evaluates both T and F, even though it’s going to throw out half of that work. In particular, even when the Pred<H>::value is false, we are still instantiating tuple_cat — and function instantiation is basically the slowest thing you can ask a compiler to do. So it should be more efficient to implement our branching in terms of partial specializations rather than conditional_t:

template<template<class> class Pred, class Sequence>
struct filter;

template<bool>
struct helper {
template<template<class> class Pred, class H, class... Ts>
using type = decltype(std::tuple_cat(
std::declval<std::tuple<H>>(),
std::declval<typename filter<Pred, std::tuple<Ts...>>::type>()
));
};

template<>
struct helper<false> {
template<template<class> class Pred, class H, class... Ts>
using type = typename filter<Pred, std::tuple<Ts...>>::type;
};

// recursive case
template<template<class> class Pred, class H, class... Ts>
struct filter<Pred, std::tuple<H, Ts...>> {
using type = typename helper<Pred<H>::value>::template type<Pred, H, Ts...>;
};

// base case
template<template<class> class Pred>
struct filter<Pred, std::tuple<>> {
using type = std::tuple<>;
};


Now we instantiate tuple_cat only exactly as many times as Pred<H>::value is true. (Here I am also trying to demonstrate my newfound appreciation for SCARY metafunctions.)

But we can still do better!

A really good rule of thumb for variadic-template metaprogramming is that

Iteration is always cheaper than recursion

because recursion involves lots of “throwaway” intermediate entities, whereas iteration often goes straight to the point. We should look for a way to avoid instantiating all those intermediate specializations of filter and tuple_cat. And lo and behold, we find such a way!

template<template<class> class Pred, class Sequence>
struct filter;

template<bool>
struct zero_or_one {
template<class E> using type = std::tuple<E>;
};

template<>
struct zero_or_one<false> {
template<class E> using type = std::tuple<>;
};

// iterative case
template<template<class> class Pred, class... Es>
struct filter<Pred, std::tuple<Es...>> {
using type = decltype(std::tuple_cat(
std::declval<typename zero_or_one<Pred<Es>::value>::template type<Es>>()...
));
};


In case you’re wondering, no we did not just push the problem down another level: std::tuple_cat is generally also implemented with iteration, not recursion.

By the way, implementing an iterative tuple_cat is one of the 12 classroom exercises in my upcoming two-day class at CppCon 2018. So if you want to be able to say “I implemented tuple_cat in 20 minutes at CppCon 2018,” please consider signing up!

Posted 2018-07-23