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!