Range-v3 view composition and views calculation parallelization

user_8242494 0
Viewed 461

Taken from range-v3 docs, the following example demonstrates a simple composition of views pipelined to produce a range:

std::vector<int> const vi{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
using namespace ranges;
auto rng = vi | views::remove_if([](int i){return i % 2 == 1;})
              | views::transform([](int i){return std::to_string(i);});

I know that views::foo is equivalent to something like foo_view() and therefore the example above ends up like:

transform_view(remove_if_view(vi, <lambda>), <lambda>)

Now the question is:

How is the sequence of the remove_if and transform operations taking place? (I know that they are lazy and they are not actually calculated at this step, rather than later on when rng is materialized, but that's not the point).

I can see two options here:

  1. The operations are fused by range-v3 and when a given element of rng is accessed through some iterator, the two operations are applied to the element consequently.

  2. When a given element is requested, the whole remove_if operation is applied throughout vi and then the output-vector of that operation is fed into transform. Thus, we end up with a whole "trasformed + removed_if" vector that gives us access to the desired element.

I am pretty sure that option (1) is what's actually going on. If that's the case, how does range-v3 accomplish that? Does it have some kind of generic composition code in order to combine unlimited number of composed-by-views operations?

Side question: What kind of iterator do range-v3 views expose? I think that whatever below a random-access iterator would render the parallelization impossible.

Meta-question: If option (1) is the truth, then isn't it extremely trivial to parallelize range-algorithms given that they take as input a simple range (composed by multiple views, calculated on-demand with operation fusion)?

range-v3 std-ranges c++20 std c++
1 Answers

If I had to guess then I would say that | operators build a compile time AST (abstract syntax tree) of operations. If you store this AST into a variable called range and then you call auto it = std::begin(range) you materialize an iterator the type of which will be non trivial ( unless type erasure is used). When you call *it it evaluates all the transform operations starting from dereferencing the current state of the original iterator. When you call ++it it is a bit more complicated. It needs to do several things. It needs to advance the base iterator but it also needs to evaluate all the in-between transforms so that the predicate in remove_if can be evaluated. If the predicate returns true then the base iterator needs to be advanced again as we are skipping an item.

This can result in inefficiencies in the pipeline if you place a transform before a remove_if. The transform will be evaluated twice for every item. Once for advancing the iterator and second for reading the current value. If the transform is non trivial then you get a slowdown. If the transform has side effects then bad things might happen. See

Why C++ ranges "transform -> filter" calls transform twice for values that match the filter's predicate?

for more details

With regards to making the operations parallel it would probably be done similar to the std library implementation by adding a tag parameter to each AST node saying whether you want to do it parallel or not. See https://www.modernescpp.com/index.php/parallel-algorithm-of-the-standard-template-library for some details

for example

vector<int> v = ...

// standard sequential sort
std::sort(v.begin(), v.end());

// sequential execution
std::sort(std::parallel::seq, v.begin(), v.end());

// permitting parallel execution
std::sort(std::parallel::par, v.begin(), v.end());

// permitting parallel and vectorized execution
std::sort(std::parallel::par_unseq, v.begin(), v.end());

This pattern could be extended to range-v3 but essentially the overloads would be new implementations and non trivial to implement.

There is an open question in the rangev3 github page on this topic with some further links that may be of interest to you.

https://github.com/ericniebler/range-v3/issues/921

(I am not a contributor to range-v3 but I have implemented my own range like library that has an overlap in functionality with range-v3.)

user_1582850
Related