Why so many calls to constructor using std::views::filter

Question

Why so many calls to constructor using std::views::filter

M3 116

I have the following example code showing std::ranges::filter repeatedly calls constructor on the lambda I passed in. Why is this happening? How can I get by with fewer?
This is on VS 2022 preview 7 with /std:c++latest, but I've seen similar on gcc (godbolt).

#include <ranges>
#include <vector>
#include <utility>

using namespace std;
using std::ranges::views::filter;

struct S {
    S() {
        ++count;
        cout << "\ns(" << count << ")";
    }
    S(const S &s) {
        count = s.count;
        ++count;
        cout << "\ncopy s(" << count << ")";
    }
    static int count;
};

int S::count = 0;

template <typename T>
auto my_test(T &&s) {
    return [p = std::forward<T>(s)](int i) { return true; };
}

int main() {
    std::vector<int> ints{1, 2, 3, 4, 5};
    auto f = my_test(S{});  // 2 total ctors (I expected 1)

    auto it = ints | filter(f)  // 6 total ctors  (I expected 0)
              | filter(f)       // 12 total ctors   (I expected 0)
              | filter(f);      // 20 total ctors (I expected 0)
    return 0;
}

Output:
s(1)
copy s(2)
copy s(3)
copy s(4)
copy s(5)
copy s(6)
copy s(7)
copy s(8)
copy s(9)
copy s(10)
copy s(11)
copy s(12)
copy s(13)
copy s(14)
copy s(15)
copy s(16)
copy s(17)
copy s(18)
copy s(19)
copy s(20)

Viorel 122.6K Reputation points

2021-10-31T20:21:02.49+00:00
If you write:

S s; auto f = my_test( &s );

you will see a smaller number.

By the way, since you are experimenting with "&&", you can define the 'S( S&& s)' constructor too.
M3 116 Reputation points

2021-10-31T22:09:10.563+00:00
Thanks, that is helpful. I can see it does eliminate the constructors for S, but probably doesn't avoid the 20 copies of a pointer to S along with any copies of the underlying iterators, right?
With ranges, I hoped I was getting a very slick composable way to do this kind of thing

for ( auto i: container ) if (pred_a(i)) if (pred_b(i)) // ... do_something(i);

and I guess I really am getting something slick looking, but it's not for free. Unless I'm still missing a key point (sadly, not unlikely)
Minxin Yu 13,501 Reputation points Microsoft External Staff

2021-11-01T08:17:33.523+00:00
I tested the code suggested but no copies：

S s; auto f = my_test( &s );
M3 116 Reputation points

2021-11-01T17:25:15.797+00:00

Thanks. I see that S no longer has extra copy constructors which is great. That means there is a single copy of S, but it doesn't say anything about pointers to S. What I think is happening is that each time a filter is constructed it copies needed iterators and pointers to S from ALL previous filters. So as you compose a chain of filters the complexity grows linearly with the number of filters. Probably a small cost, but a cost nonetheless. Let me know if you see something else.

Accepted answer

1 additional answer

Your answer

Viorel 122.6K Reputation points

2021-10-31T20:21:02.49+00:00

If you write:

S s; auto f = my_test( &s );

you will see a smaller number.

By the way, since you are experimenting with "&&", you can define the 'S( S&& s)' constructor too.
M3 116 Reputation points

2021-10-31T22:09:10.563+00:00

Thanks, that is helpful. I can see it does eliminate the constructors for S, but probably doesn't avoid the 20 copies of a pointer to S along with any copies of the underlying iterators, right?
With ranges, I hoped I was getting a very slick composable way to do this kind of thing

for ( auto i: container ) if (pred_a(i)) if (pred_b(i)) // ... do_something(i);

and I guess I really am getting something slick looking, but it's not for free. Unless I'm still missing a key point (sadly, not unlikely)
Minxin Yu 13,501 Reputation points Microsoft External Staff

2021-11-01T08:17:33.523+00:00

I tested the code suggested but no copies：

S s; auto f = my_test( &s );
M3 116 Reputation points

2021-11-01T17:25:15.797+00:00

Thanks. I see that S no longer has extra copy constructors which is great. That means there is a single copy of S, but it doesn't say anything about pointers to S. What I think is happening is that each time a filter is constructed it copies needed iterators and pointers to S from ALL previous filters. So as you compose a chain of filters the complexity grows linearly with the number of filters. Probably a small cost, but a cost nonetheless. Let me know if you see something else.

Answer 1

Here is the best way I've found. Improvements from original include

definition of the lambda generating function
a) Universal (aka forwarding) reference. Previously I had a const && which causes a silent copies.
b) a std::forward to a capture by value. Importantly this avoids dangling references when using lambda returned from this function
```
  template <typename T>
  auto my_test(T &&s) {
      return [p = std::forward<T>(s)](int i) { return true; };
  }
```

c) using std::move when constructing filters in main function. Or, one could construct filters with rvalues instead of std::moving lvalues in main()

2) better diagnostics in struct S, by RLWA32-6355
3) addition of move constructor suggested by RLWA32-6355.

here is the whole thing with some refactoring to more descriptive names

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

    using namespace std;
    using std::ranges::views::filter;

   // This definition is the same as struct S before. skip over if you like
    struct PredData {
        PredData() = delete;
        PredData(int i) : m_id(i) {
            cout << "\ns(" << m_id << ")";
            ctors++;
        }
        PredData(const PredData &s) {
            m_id = s.m_id;
            cout << "\ncopy s(" << m_id << ")";
            copy_ctors++;
        }
        // Comment/uncomment to see effect of the move constructor when lambda captures by value
        PredData(PredData &&rhs) {
            swap(m_id, rhs.m_id);
            cout << "\nmove s(" << m_id << ")";
            move_ctors++;
        }
        \~PredData() {
            cout << "\n\~s(" << m_id << ")";
            dtors++;
        }

        operator int() const {
            return m_id;
        }

        static int ctors, dtors, copy_ctors, move_ctors;

        int m_id{-1};
    };

    int PredData::ctors{0}, PredData::dtors{0}, PredData::copy_ctors{0}, PredData::move_ctors{0};

    // Change lambda to capture by reference [&s] to see effect on constructor use
    template <typename T>
    constexpr inline auto pred_generator(T &&temp_data) {
        return [pred_data = std::forward<T>(temp_data)](int i) {
            cout << "\nIn lambda: value is " << i << " id is " << (int)pred_data;
            return i <= (int)pred_data;
        };
    }

    int main() {
        int expt_id = 0;
        std::vector<int> ints{1, 2, 3, 4, 5}; 

        {  // Scope to invoke destructors before totals printed

            PredData s1{++expt_id}, s2{++expt_id};

            auto f1 = pred_generator(s1);                   // two ctor, one move
            auto f2 = pred_generator(std::move(s2));        // one ctor, one move
            auto f3 = pred_generator(PredData{++expt_id});  // one ctor, one move

            cout << "\nfilter";
            auto g0 = filter(f1);  // s(1)     1 copy, 1 move
                                   // s(-1)    1 dtor

            cout << "\nints | filter1";
            auto g1 = ints | filter(f1);  // s(1)  1 copy, 3 moves
                                          // s(-1) 3 dtor

            cout << "\nints | filter1 | filter2";
            auto g2 = ints | filter(f1) | filter(f2);
            // s(1) 1 copy, 5 moves
            // s(2) 1 copy, 3 moves
            // s(-1), 8 dtor

            cout << "\nints | filter1 | filter2 | filter3";
            auto g3 = ints | filter(f1) | filter(f2) | filter(f3);
            // s(1) 1 copy, 7 moves
            // s(2) 1 copy, 5 moves
            // s(3) 1 copy, 3 moves
            // s(-1), 15 dtor

        cout << "\nints | filter(move) ";
        auto g4 = ints | filter(std::move(f1)) ;
        // s(1), 4 moves
        // s(-1), 3 dtors

            cout << "\nBefore filtered for";
            for (auto &x : g3) {
                cout << "\nx is " << x;
            }
            cout << "\nAfter filtered for";
        }

        cout << "\nctors " << PredData::ctors
             << ", copy_ctors " << PredData::copy_ctors
             << ", move_ctors " << PredData::move_ctors
             << ", dtors " << PredData::dtors;

        return 0;
    }

Answer 2

You can really see the difference if your lambda captures by reference instead of by value. Try this example -

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

using namespace std;
using namespace ranges::views;

struct S {
    S(int i) : m_id(i){

        cout << "s(" << m_id << ")\n";
        ctors++;
    }

    S(const S& s) {
        m_id = s.m_id;
        cout << "copy s(" << m_id << ")\n";
        copy_ctors++;
    }

    ~S() {
        cout << "~s(" << m_id << ")\n";
        dtors++;
    }

    // Comment/uncomment to see effect of the move constructor when lambda captures by value
    //S(S&& rhs) {
    //    swap(m_id, rhs.m_id);
    //    cout << "move s(" << m_id << ")\n";
    //    move_ctors++;
    //}

    operator int() const {
        return m_id;
    }

    static int ctors, dtors, copy_ctors, move_ctors;

private:
    int m_id{ 0 };
};

int S::ctors{ 0 }, S::dtors{ 0 }, S::copy_ctors{ 0 }, S::move_ctors{ 0 };



// Change lambda to capture by reference [&s] to see effect on constructor use
template <typename T>
auto my_test(T&& s) {
    return [s](int i) {
        cout << "In lambda: value is " << i << " id is " << (int) s << endl;
        return i <= (int) s;
    };
}


int main()
{
    std::vector<int> ints{ 1, 2, 3, 4, 5 };

    {  // Scope to invoke destructors before totals printed

        S s4{ 4 }, s2{ 2 };

        auto f4 = my_test(s4);
        auto f2 = my_test(s2);

        cout << "Before filtered for\n";
        for (auto& x : ints | filter(f4) | filter(f2))
        {
            cout << "x is " << x << endl;
        }
        cout << "After filtered for\n";
    }

    cout << "ctors " << S::ctors
        << ", copy_ctors " << S::copy_ctors
        << ", move_ctors " << S::move_ctors
        << ", dtors " << S::dtors << endl;

    return 0;
}

M3 116 Reputation points

2021-11-02T18:46:13.343+00:00

I swear I had written a response, but then Edge (or the inter-webs) ate it.

Anyway. Those are very helpful diagnostics.

I still believe that each time a range is piped to another filter, that all information from all previous filters is copied. In the case of a lambda clause that has captured by reference it is cheaper because the lambda class has a pointer to the captured data, but it will still be copied.

There is another problem. If I call the filter with an rvalue: filter( my_test( S{3})), there will be a dangling reference when the filter is used. Let me know if that's wrong.
I can easily avoid it by writing another overloaded my_test functions that captures by value when it is passed a rvalue.
RLWA32 49,536 Reputation points

2021-11-02T20:35:55.597+00:00

There is another problem. If I call the filter with an rvalue: filter( my_test( S{3})), there will be a dangling reference when the filter is used.

I agree about the dangling reference in your example. But I don't believe that the S{3} object is an rvalue inside my_test.

Using the move constructor makes capture by value less expensive if dealing with non-trivial members.
M3 116 Reputation points

2021-11-03T15:59:38.367+00:00

Thanks again. I'll look carefully to see what data is copied with each filter and if I have more questions I'll ask in another thread.

Share via

Why so many calls to constructor using std::views::filter

1 additional answer

Your answer