Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Variadic templates and switch statement?

Tags:

I have the following function which can take N arguments of different types, and forwards them to N functions templated on each individual type, in this manner (example with two arguments):

template <typename T1, typename T2> bool func(int& counter, T1 x1, T2 x2) {     switch (counter) {         case 0:             if (func2<T1>(x1)) {                 counter++;                 return true;             } else {                 return false;             }         case 1:             if (func2<T2>(x2)) {                 counter++;                 return true;             } else {                 return false;             }         default:             return true;     } } 

I want to write this function with variadic templates so that it can handle any number of arguments in a type-safe way. I can see a solution using recursive functions, passing along the counter and the variadic index and comparing them for equality, but this would seem to yield far less efficient code than the switch statement above (a sequence of if-checks compared to a jump table).

Can this be done efficiently using template metaprogramming or do I need to provide overloads for each arity?

like image 578
Thomas Avatar asked Sep 18 '17 12:09

Thomas


People also ask

What is Variadic template in C++?

Variadic templates are class or function templates, that can take any variable(zero or more) number of arguments. In C++, templates can have a fixed number of parameters only that have to be specified at the time of declaration. However, variadic templates help to overcome this issue.

How do you expand a parameter pack?

Parameter packs can only be expanded in a strictly-defined list of contexts, and operator , is not one of them. In other words, it's not possible to use pack expansion to generate an expression consisting of a series of subexpressions delimited by operator , .

What is a parameter pack?

Parameter packs (C++11) A parameter pack can be a type of parameter for templates. Unlike previous parameters, which can only bind to a single argument, a parameter pack can pack multiple parameters into a single parameter by placing an ellipsis to the left of the parameter name.


2 Answers

Here's a solution similar to max's, but it: a) clearly separates out the generic parts from the parts specific to the solution, and b) I show that clang fully optimizes it. The basic idea is to build a switch case at compile time, from a contiguous integer sequence. We do that like this:

template <class T, T ... Is, class F> auto compile_switch(T i, std::integer_sequence<T, Is...>, F f) {   using return_type = std::common_type_t<decltype(f(std::integral_constant<T, Is>{}))...>;   return_type ret;   std::initializer_list<int> ({(i == Is ? (ret = f(std::integral_constant<T, Is>{})),0 : 0)...});   return ret; } 

The idea is that integer gets passed into the lambda as an integral constant type, so its usable in compile time contexts. To use this with the current problem, all we have to do is forward the variadic pack a tuple, and apply the usual tricks with index sequence:

template <class T, std::size_t ... Is> bool func_impl(std::size_t& counter, T&& t, std::index_sequence<Is...> is) {   auto b = compile_switch(counter, is, [&] (auto i) -> bool {     return func2(std::get<i>(std::move(t)));   });   if (b) ++counter;   return b; }  template <class ... Ts> bool func(std::size_t & counter, Ts&& ... ts) {   return func_impl(counter,       std::forward_as_tuple(std::forward<Ts>(ts)...),       std::index_sequence_for<Ts...>{}); } 

We'll use this definition of func2 to look at some assembly:

template <class T> bool func2(const T& t) { std::cerr << t; return std::is_trivial<T>::value; } 

Looking here: https://godbolt.org/g/6idVPS we notice the following instructions:

auto compile_switch<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul, bool func_impl<std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>(unsigned long&, std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>&&, std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>)::{lambda(auto:1)#1}>(unsigned long, std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>, bool func_impl<std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>(unsigned long&, std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>&&, std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>)::{lambda(auto:1)#1}): # @auto compile_switch<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul, bool func_impl<std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>(unsigned long&, std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>&&, std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>)::{lambda(auto:1)#1}>(unsigned long, std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>, bool func_impl<std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>(unsigned long&, std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>&&, std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>)::{lambda(auto:1)#1})         push    r14         push    rbx         push    rax         mov     bl, 1         cmp     rdi, 5         ja      .LBB2_11         jmp     qword ptr [8*rdi + .LJTI2_0] 

Looking down for that label, we find:

.LJTI2_0:         .quad   .LBB2_2         .quad   .LBB2_4         .quad   .LBB2_5         .quad   .LBB2_6         .quad   .LBB2_7         .quad   .LBB2_10 

In other words, clang has both turned this into a jump table, and inlined all the calls to func2. This is not possible using a table of function pointers as some have suggested (at least I've never seen a compiler do it), in fact the only way to get assembly this good is via switch case, or with this technique + clang. Sadly gcc will not generate assembly quite as good, but still decent.

like image 61
Nir Friedman Avatar answered Oct 07 '22 17:10

Nir Friedman


Just for fun, I propose the following way

template <typename ... Ts> bool func (int & cnt, Ts ... xs)  {    using unused = int[];     int  i   { -1 };    bool ret { true };     (void)unused { 0, ((++i == cnt ? (ret = func<Ts>(xs)) : true), 0)... };     if ( ret && (cnt <= i) )       ++cnt;     return ret;  } 

but I don't think is a efficient way as the switch way.

like image 28
max66 Avatar answered Oct 07 '22 17:10

max66