Is there an efficient way to use views::filter after transform? (range adaptors)

user_8658157 0
Viewed 1213

A common example of strange behaviour with views::filter:

#include <iostream>
#include <ranges>
#include <vector>

int main ()
{
    using namespace std;

    auto ml = [](char c) // ml = make lambda (always accepts / transforms to 1)
    {
        return [c](int) {cout << c; return 1;};
    };

    vector<int> vec = {1};
    
    auto view = vec
        | views::transform  (ml('T'))
        | views::filter     (ml('F'));
    
    // use view somehow:
    return *view.begin();
}

Which outputs TFT (note the extra T). demo

We must know that:

auto view = vec
    | views::transform  (ml('A'))
    | views::filter     (ml('B'));

...is just syntax sugar for:

auto view = views::filter(views::transform(vec, ml('A')), ml('B'));

Problem explained:

Having implemented a few mock versions of views::filter, it seems the issue is:

  • Unlike other iterators, filter::iterator does its work during operator ++ (searching for an accepted value)
  • operator * is designed to extract the value, but with filter::iterator the work has already been done and lost (we don't need redo the search for an accepted value, but we do need to re-calculate it)
  • We can't store the result because of the constant-time copy constraint for views (the value could be an array)

To explain this in a picture we'll represent the process of iterating over:

view = container | Transform | Filter1 | Filter2 | Filter3

(apologies for the ugly diagram) circles represent the work being done Pr(F3) for Print F3 (the work done in the mock example):

enter image description here

We can see that if we combine only filters or only transforms then we don't repeat the work - the issue is having filters above the transforms (above in the diagram).

In worst-case we get [where n(x) number of x]:
n(iterations) = n(filters) * n(transforms)
when we'd expect n(filters) + n(transforms)

We can see this parabolic vs linear growth with this example.

Question

Sometimes the transforms need to be done before we can determine what to filter, so how to avoid the extra work-load? This seems important as views are designed to iterate over containers, which is bottle-neck territory.

Is there a way to use std::views for situations like this without the huge slow-down described above?

std-ranges c++20 g++ gcc c++
1 Answers

I think a good way to think of this is that a filter needs to get the value of its input in order to decide whether to perform the filtering. Then when you evaluate the output of the filter, we must evaluate again, unless the filter has cached the input (see below).

From alternating filters and views, it appears that each filter builds a list of all transforms below it, and then uses this list of transforms to evaluate the result. So modifying your example

#include <iostream>
#include <ranges>
#include <vector>

int main()
{

    auto ml = [](char c) // ml = make lambda (always accepts / transforms to 1)
    {
        return [c](int) {std::cout << c; return 1; };
    };

    std::vector<int> vec = { 1,1,1 };
    auto view = vec
        | std::views::transform(ml('T'))
        | std::views::filter(ml('F'))
        | std::views::transform(ml('U'))
        | std::views::filter(ml('G'));

    for( auto v : view)
        std::cout << v << ",";

    return 0;
}

gives output

TFTUGTU1,TFTUGTU1,TFTUGTU1,

we want to take our input, then do transform T, filter F, transform U, filter G. So we may have expected output TFUG1. However, here is what seems to happen

Filter G needs to know if the value got filtered already, and needs to know the element value to know if it should do any filtering itself. So it passes this back up the chain to the next filter - F.

Filter F needs to know if it needs to filter so it evaluates transform T, it then does the filtering and finds it can pass the value, so it adds T to it's list of transforms.

G now can decide if it needs to filter. It evaluates the input using F's list of transforms (which only includes T) and any transforms between F and G. So we call transforms T and U.

G now does its filtering and finds it can pass the value. So it adds all the transforms below to it's list of transforms, This list is now T and U.

Finally we want the value, so G evaluates everything by calling its list of transforms T and U. We now have our result.

Note that this is a conceptual model from observations. I haven't trawled the standard or the code to check this, it's just how it appears from the example.

You can view this as a tree

G
|\
U U
|  \
F   \
|\   \
T T   T

Every filter causes a branch with filters and transforms on the left and just transforms on the right. We evaluate the left of each filter node then the filter node itself, then the right branch of each filter node.

The complexity is as you say, O((n_filters+1)*n_transforms).

My suspicion is that if you had provided a constexpr as the transform, then the compiler could optimise this into a simple linear evaluation of TFUG, because it would see that the return value would be the same for each evaluation. However, the act of adding the std::cout in the transform means that this is not a constexpr and so these optimisations cannot happen.

I therefore suspect that what has happened here is that by trying to show the structure of the C++ code, you have stopped optimisations occurring in the binary code.

You can of course test this by creating a constexpr transform and checking what happens to the runtime as you increase the layers of views with optimisation turned on.

Edit

I initially said that I thought the filters were caching a list of transforms and if they were doing this then if the transforms were constexpr then they might cache the results of these transfers instead. On reflection and with more reading, I think the filters are not caching a list of transforms at all. They are evaluating the left side of each branch on incrementing the iterator and the right side on dereferencing.

However, I would still imagine that with constexpr transforms, the compiler could effectively optimise this. And without checking the code, maybe filters can do caching - I'm sure someone on here knows. So I think it would still be useful to test a constexpr optimised example.

user_10518050
Related