TMP Part 4 - Recursion Free Tuple Iteration
By on August 25, 2017
This post is a follow up to
iterating over tuples,
but this time we do not use runtime or compile time recursion, so the
resulting code is cleaner and faster. There are two different types of
iteration, one where you keep a “state” and one where you do not. By
state I mean, for example, the partial sum of all elements already
processed in a reduction, accumulation, or fold.
Parameter pack
expansion is the fastest and preferred method of iteration. However,
it has the drawback that it cannot keep state at compile time (or at least
I haven’t figured out how, yet). That means parameter pack expansion works well
in transforms at compile time but not folds. Interestingly enough, we can
use parameter pack expansion for runtime iteration with state. This is something
I have spent a fair amount of time thinking about and I now have a solution I’m
very happy with. Let’s dive in!
A Tuple Fold
We have a std::tuple and want to iterate over the elements of it by performing
either a fold or a transform. These are distinct because, for a transform, the
current index of the iteration must be passed as a template parameter. I will
come back to this important point in a bit. First, let’s implement a fold
and a counted fold. For this section I will use C++14 because it makes the
discussion and code more concise, but everything can readily be implemented
in C++11 by removing constexpr in some places and implementing an
integer_sequence. The code I show here is shared on
GitHub.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
namespace tuple_impl_detail {
template <bool ReverseIteration, typename... Elements, typename N_naryOp,
typename... Args, size_t... Is>
constexpr inline void tuple_fold_impl(
const std::tuple<Elements...>& tupull, N_naryOp&& op,
std::index_sequence<Is...> /*meta*/,
Args&... args) noexcept(
noexcept(static_cast<void>(std::initializer_list<char>{
(static_cast<void>(
op(std::get<(ReverseIteration ? sizeof...(Elements) - 1 - Is : Is)>(
tupull),
args...)),
'0')...}))) {
constexpr size_t tuple_size = sizeof...(Elements);
static_cast<void>(std::initializer_list<char>{
(static_cast<void>(
op(std::get<(ReverseIteration ? tuple_size - 1 - Is : Is)>(tupull),
args...)),
'0')...});
}
} // namespace tuple_impl_detail
template <bool ReverseIteration = false, typename... Elements,
typename N_naryOp, typename... Args>
constexpr inline void tuple_fold(
const std::tuple<Elements...>& tuple, N_naryOp&& op,
Args&&... args) noexcept(noexcept(tuple_impl_detail::
tuple_fold_impl<ReverseIteration>(
tuple, std::forward<N_naryOp>(op),
std::make_index_sequence<
sizeof...(Elements)>{},
args...))) {
tuple_impl_detail::tuple_fold_impl<ReverseIteration>(
tuple, std::forward<N_naryOp>(op),
std::make_index_sequence<sizeof...(Elements)>{}, args...);
}
There’s a lot happening here, so I’ll go over it piece by piece.
First, let’s look at the arguments passed to tuple_fold. We take a const
reference to a std::tuple since we aren’t modifying its state, then we
take an invokable (with some constraints that I’ll explain), and finally
a list of arguments by forwarding references. Because the call to ops
may have a different first argument for each iteration op must be a function
object with a call operator template, or a generic lambda in C++14. In the case
that all elements are of the same type you could also pass a function. Next,
taking args... by forwarding
reference is required so that an rvalue reference can be passed to tuple_fold.
Finally, the first template parameter of tuple_fold controls whether we iterate from
left to right (the default) or from right to left (ReverseIteration == true).
Let’s ignore the noexcept business until later.
Indexing and Evaluation Order
Okay, now that we know what the function receives as arguments and parameters,
let’s look at the body. The only thing there is a call to the implementation,
since in order to index the std::tuple we need a parameter pack of size_ts
ranging from 0 to sizeof...(Elements)-1. C++14 has the handy
std::index_sequence
and
std::make_index_sequence
to help us with generating such parameter packs.
std::make_index_sequence takes a single template parameter N and generates
a std::index_sequnece from 0 to N - 1. The helper function is then able
to match a parameter pack to the std::index_sequence, which is the parameter
pack we need to index the std::tuple. This parameter pack is named Is in
tuple_fold_impl. We can now call std::get<Is>(tupull)... to generate
std::get<0>(tupull), std::get<1>(tupull), etc. In other words, being able to
generate a comma separated list of the std::get calls
allows us to apply op to all elements in a tuple using
op(std::get<Is>(tupull), args...).... Hopefully this makes some sense.
Now we need to figure out how to guarantee the runtime order of evaluation
of the calls. Luckily std::initializer_list has the wonderful property of
guaranteeing left-to-right evaluation. However, we need to create the
initializer_list with a uniform type, so let’s just choose a char (it’s
only 1 byte in size). We can use the comma operator to discard the result of
the op(std::get<Is>(tupull), args...) calls. However, we need to make
sure that the result of the op call is void. Otherwise, if the user
overloaded the comma operator for char and the return type of op, we will
have unexpected code being executed as part of our tuple_fold implementation.
With all of this is mind we can almost
write line 14 of the above code block. The last static_cast<void> around the
initializer_list on line 14 is there to avoid unused
variable warnings, and (ReverseIteration ? tuple_size - 1 - Is : Is) controls
left-to-right and right-to-left evaluation order.
Exception Handling
Phew, that was a lot, but we are not done yet! What about the noexcept stuff?
Well, we want our tuple_fold function to be noexcept if all the calls
to op are noexcept. Unfortunately, noexcept doubles as a specifier
and as an operator to calculate whether a code block is noexcept.
This is why we have noexcept(noexcept(....)): the inner noexcept is a call
to the noexcept operator, while the outer is the noexcept specifier on a
function taking the returned boolean of the noexcept operator. I’ll note
briefly that for tuple_counted_fold you pass the Is as the second parameter
to the invokable op (I’ll go over why this isn’t a transform below).
So we’ve done quite a bit of work here, and the result is extremely dense code.
What is so awesome about tuple_fold? Well the thing to appreciate is that
we are iterating over the std::tuple without any recursion. This means we
can operate on arbitrary large tuples and never encounter compile time or
runtime recursion depth limits. Unfortunately, if you are using the std::tuple
implementation in stdlibc++ this won’t help you all that much because their
std::tuple implementation is recursive. However, with libcxx you can go wild
and iterate over tuples with thousands of elements. I’ve actually found a use
for this, but that’s for another time.
Now, I lied a little bit when I said the implementation is completely compile
time recursion free. The generation of the index_sequence requires recursion.
However, even compile time recursion can be improved with a technique called
fast tracking (more on this in a different post). In practice, creating an
index_sequence of two hundred thousand elements takes ~30 seconds with GCC
7.1.1 and libstdc++. With Clang 4.0.1 and libstdc++ the compile time is about
the same. However, with Clang and libcxx it compiles instantaneously. The reason
is that Clang has a compiler intrinsic that can generate index_sequences
extremely quickly and libcxx takes advantage of this. Using the compiler
builtin an index_sequence of 200,000 elements is generated in under a second.
If we intentionally fall back to the TMP method of generating the
index_sequence, libcxx is still a factor of roughly two and a half faster than
libstdc++.
Tuple Transform
Why did I call the above function a fold? The reason is because we are
unable to index a second tuple inside op, which is necessary for a transform.
All we are able to do is some sort of reduction operation, so tuple_fold is
a std::tuple implementation of std::accumulate (feel free to rename
the function to tuple_accumulate if you prefer). In order to perform a
transform we must pass the current Index as a template parameter to the
invokable. At first glance it looks like this means that tuple_transform’s
op must be a function object with a call operator template whose first
template parameter is a non-type template parameter of type size_t, the current
Index. With
this
proposal you will also be able to use lambdas, e.g.
[]<size_t Index>(const auto& element, ...) {...}. However, we are able to work
around this issue by having a generic lambda that takes the current element as
its first argument and a std::integral_constant<size_t, Index> index as its
second argument. We are then able to get the
Index at compile time using decltype(index)::value. I’ll show an example
below, but for now here is the implementation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
namespace tuple_impl_detail {
template <bool ReverseIteration, typename... Elements, typename N_naryOp,
typename... Args, size_t... Is>
constexpr inline void tuple_transform_impl(
const std::tuple<Elements...>& tupull, N_naryOp&& op,
std::index_sequence<Is...> /*meta*/,
Args&... args) noexcept(
noexcept(static_cast<void>(std::initializer_list<char>{
(static_cast<void>(op(
std::get<(ReverseIteration ? sizeof...(Elements) - 1 - Is : Is)>(
tupull),
std::integral_constant<
size_t, (ReverseIteration ? sizeof...(Elements) - 1 - Is : Is)>{},
args...)),
'0')...}))) {
constexpr size_t tuple_size = sizeof...(Elements);
static_cast<void>(std::initializer_list<char>{(
static_cast<void>(op(
std::get<(ReverseIteration ? tuple_size - 1 - Is : Is)>(tupull),
std::integral_constant<size_t, (ReverseIteration ? tuple_size - 1 - Is
: Is)>{},
args...)),
'0')...});
}
} // namespace tuple_impl_detail
template <bool ReverseIteration = false, typename... Elements,
typename N_naryOp, typename... Args>
constexpr void tuple_transform(
const std::tuple<Elements...>& tuple, N_naryOp&& op,
Args&&... args) noexcept(noexcept(tuple_impl_detail::
tuple_transform_impl<
ReverseIteration>(
tuple, std::forward<N_naryOp>(op),
std::make_index_sequence<
sizeof...(Elements)>{},
args...))) {
tuple_impl_detail::tuple_transform_impl<ReverseIteration>(
tuple, std::forward<N_naryOp>(op),
std::make_index_sequence<sizeof...(Elements)>{}, args...);
}
As you can see, the code is nearly identical to tuple_fold except that now
op is called using
op(std::get<Is>(tupull), std::integral_constant<size_t, Is>{}, ...) so
that the second argument can be used for indexing a std::tuple inside a
generic lambda. In the C++11 case you are restricted to function objects
since generic lambdas are a C++14 feature, but other than that the code
is the same.
Example Use Cases
Now let’s look at some toy examples of how to use the above functions. First,
let’s look at tuple_fold
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const auto my_tupull = std::make_tuple(2, 7, -3.8, 20.9);
double sum_value = 0.0;
tuple_fold(my_tupull,
[](const auto& element, double& state) { state += element; },
sum_value);
std::cout << "Expected: 26.1 Computed: " << sum_value << "\n";
sum_value = 0.0;
tuple_counted_fold(my_tupull,
[](const auto& element, size_t index, double& state) {
if (index != 1) {
state += element;
}
},
sum_value);
std::cout << "Expected: 19.1 Computed: " << sum_value << "\n";
Of course, in this example you could have just used a std::vector<double>
as the container instead of a tuple.
However, if you need to iterate over different classes and call a member
function on each, the solution is less obvious. One method is to have all
classes derive from an abstract base class, and then have a vector of
pointers to abstract base classes. This works, but does limit what you can do
at compile time. I’ve found that avoiding the use of abstract base classes leads
to clearer and safer code. The objects of different types are stored in a
tuple, over which one can then iterate using either tuple_fold or
tuple_transform. An example of this approach is in the CoordinateMap
class in SpECTRE.
Now for an example of tuple_transform,
1
2
3
4
5
6
7
8
9
10
const auto my_tupull = std::make_tuple(2, 7, -3.8, 20.9);
std::decay_t<decltype(my_tupull)> out_tupull;
tuple_transform(my_tupull,
[](const auto& element, auto index, auto& out_tuple) {
constexpr size_t index_v = decltype(index)::value;
std::get<index_v>(out_tuple) = -element;
},
out_tupull);
std::cout << "Expected: (-2, -7, 3.8, -20.9) Computed: " << out_tupull
<< "\n";
In order to use the index at compile time for indexing the out_tuple
we must get its type (std::integral_constant), and then assign the
member variable value to a constexpr variable. Other than that,
tuple_transform and tuple_fold behave very similarly and there is not much
to say.
Summary
We used parameter pack expansion and std::initializer_list to implement
a non-recursive tuple_fold and tuple_transform for both C++11 and C++14.
The main takeaway is
that using parameter pack expansion is the preferred way to do iteration
whenever possible because this trivially avoids recursion depth problems
and is faster than function template and class template instantiation.
As we saw in the previous post, recursive iteration over a tuple requires
using SFINAE, which is
extremely slow. See 9:20 of
Odin Holmes’s talk for some
insight on performance of different TMP techniques. Finally, I have shared
the fully implemented version on
GitHub
under the Boost License, so please, feel free to use the code.