# Range-v3 view composition and views calculation parallelization

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)?

• no, it's not easy to parallelize range algorithms. Forget about the implementation, how do you choose the thread distribution on a range that can be composed of operations like filter, take_first_n, reverse, etc. in any order? – bolov Apr 19 at 21:05
• I guess a naive fork-join on `take_first_n | reverse` would do the work? Plus, there are more productive examples that if parallelized would give performance gains (like the one I am referring to, at my question) – gonidelis Apr 19 at 21:14
• well, range-v3 is open source You can go and try to parallelize it if you feel it is trivial or you can do it with a naive approach. – bolov Apr 19 at 21:46
• There's a lot in this question. Are you just asking basically how `views::remove_if` and `views::transform` are implemented? – Barry Apr 22 at 0:32
• @Barry I am asking how they are materialized as a reference example. The main question is how ranges derived from pipelined views are getting materialized in general. – gonidelis Apr 22 at 12:31

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.)

• My question was open on purpose but you gave a great answer nevertheless! Thanks for both the explanation and the references! – gonidelis Apr 24 at 15:10
{"ft_lang_label":"__label__en","ft_lang_prob":0.8912242,"math_prob":0.878741,"size":2106,"snap":"2021-31-2021-39","text_gpt3_token_len":505,"char_repetition_ratio":0.1132255,"word_repetition_ratio":0.0,"special_character_ratio":0.23789173,"punctuation_ratio":0.15085158,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9758204,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-07-28T01:03:42Z\",\"WARC-Record-ID\":\"<urn:uuid:699b3212-4ce5-4a9f-81ab-bde23aabac60>\",\"Content-Length\":\"180505\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:37049ca5-f294-4f9c-9c6c-cbfb079edc5a>\",\"WARC-Concurrent-To\":\"<urn:uuid:e75ec024-12c1-4280-bc22-344c7addb420>\",\"WARC-IP-Address\":\"151.101.65.69\",\"WARC-Target-URI\":\"https://stackoverflow.com/questions/67167472/range-v3-view-composition-and-views-calculation-parallelization\",\"WARC-Payload-Digest\":\"sha1:4WXFDR36BWO2R425LNMARSMXN427VGTW\",\"WARC-Block-Digest\":\"sha1:U52FUQRJBMUUVAZPO2TI4LAZGCIIDMM6\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-31/CC-MAIN-2021-31_segments_1627046153515.0_warc_CC-MAIN-20210727233849-20210728023849-00716.warc.gz\"}"}