rule suggestion T.12x Avoid recursion in variadic templates

[cubbimew]

Practical C++ Metaprogramming by @edouarda and @jfalcou highlighted a point that I think makes a good core guideline: avoid recursion in variadic templates.

This both dramatically improves compilation times and avoids recursive instantiation depth limits. The book talks about using pack expansions and std::index_sequence where possible, but perhaps there could be a note that even when those can't be used, it is sometimes possible to rewrite recursion to log(n) depth.

[MikeGitb]

I agree. And I believe c++17's fold expressions make avoiding those recursions even easier.

[MikeGitb]

To be effective, I believe such a rule would need some good examples of how to avoid them however.

[cubbimew]

This has been idle for a while.. I'd like to throw some simple example ideas:

// Bad: recursion
template<class T>
void pbv(std::vector<T>& v) {}

template<class T, class H, class... Ts>
void pbv(std::vector<T>& v, H&& h, Ts&&... ts) {
    v.push_back(h);
    pbv(v, ts...);
}

// Better: pack expansion
template<class T, class... Ts>
void pbv(std::vector<T>& v, Ts&&... ts) {
    int _[] = {0, (v.push_back(ts), 0)...};
    (void)_;
}

// Best: fold expression
template<class T, class... Ts>
void pbv(std::vector<T>& v, Ts&&... ts) {
    (v.push_back(ts), ...);
}

and perhaps

// Bad: recursion, use of TMP to calculate a value
template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};

// Good:
constexpr int factorial(int n)
{
    int f = 1;
    while(n > 0) f *= n--;
    return f;
}

something with index_sequence would be nice too, but probably too much?

[MikeGitb]

Looks good to me. Does the Better: pack expansion example need additional explanation? Wasn't too obvious to me when I first encountered this pattern.

[cubbimew]

er, my second example is not really applicable - it's not about variadic templates and duplicates the one in T.123: Use constexpr functions to compute values at compile time

[jwakely]

Thanks for the examples, they're a good start.

The examples use forwarding references so should do v.push_back(std::forward<Ts>(ts)) not v.push_back(ts) (or just not bother with forwarding references, and use const Ts&... ts to keep the example simpler).

I'm concerned that "Better" example is a hack that's too clever for its own good (we've all written it, but only because we didn't have fold expressions yet). It might need so much additional explanation that it sidetracks the guideline (e.g. that the first 0 is there to handle the empty pack case, that (void)_ is there to avoid warnings, that initialization lists guarantee order of evaluation, and probably even the use of the comma operator in (v.push_back(ts), 0)).

Here's a possible example using index_sequence with a tuple, but also relies on a similar hack that needs explanation:

// Bad recursive version:
template<std::size_t I, typename Tuple, bool = (I < std::tuple_size<Tuple>::value)>
  struct Tuple_printer
  {
    static void print(std::ostream& out, const Tuple& t)
    {
      if (I == 0)
        out << '(';
      else
        out << ',';
      out << std::get<I>(t);
      Tuple_printer<I + 1, Tuple>::print(out, t);
    }
  };

template<std::size_t I, typename Tuple>
  struct Tuple_printer<I, Tuple, false>
  {
    static void print(std::ostream& out, const Tuple&) { out << ')'; }
  };

template<typename... T>
  void print_tuple(std::ostream& out, const std::tuple<T...>& t)
  {
    Tuple_printer<0, std::tuple<T...>>::print(out, t);
  }

// Better:
template<typename Tuple, std::size_t... I>
  int print_tuple_impl(std::ostream& out, const Tuple& t, std::index_sequence<I...>)
  {
    int dummy[] = { 0,
      // create and call a lambda function for each element of the pack:
      [&]{ if (I > 0) out << ','; out << std::get<I>(t); return 0; }()...
    };
    return dummy[0]; // prevent unused variable warnings
  }

template<typename... T>
  void print_tuple(std::ostream& out, const std::tuple<T...>& t)
  {
    out << '(';
    print_tuple_impl(out, t, std::index_sequence_for<T...>());
    out << ')';
  }

[MikeGitb]

@jwakely: I agree it is a hack, but it's all we have at the moment and for those of us that can't use new compilers on a regular basis, fold expressions might be lacking for quite some time. The way to document something like this is usually to provide a link to SO or some other source that explains the general pattern - the coreguidelines might just be that source in the future.

[compmaniak]

I discovered this proposal from Sergey's talk on C++ Russia 2017. That was the good talk. Proposed examples are quite clear. But they seem to be in conflict with the rule T.103 "Don’t use variadic templates for homogeneous argument lists" Here we have a vector of T. Is it better to use an example with writing to std::cout?

[cubbimew]

Thanks, @compmaniak, your talk about beating boost::lexical_cast at its own game was interesting too. If you are referring to

template<class T, class... Ts>
void pbv(std::vector<T>& v, Ts&&... ts)

the arguments are not homogeneous: they could be pbv<vector<double>, int, short, float> (as long as they are all convertible to T)

But sure, writing to std::cout is another simple demo for handling a heterogeneous type list. @jwakely 's example is doing just that and it's a fair option. In fact std::index_sequence is probably important to mention anyhow when talking about eliminating recursion in variadic templates (and it works with fold expressions too:

((out << (I == 0? "" : ", ") << std::get<I>(t)), ...);

[jwakely]

N.B. #625 just added a recursive example. We could either improve it, or give it a reference to this new guidelines (once added).