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?
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.
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 , .
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.
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With