Best practices + expectations for zip.filter.output_to(zip)

[robbiesri]

Thanks so much for creating this library. It's been fun for me to learn how to work with it, and compare it against raw for-loops + ranges.

I've been experimenting with some code where I'm iterating over a set of associated sequences, testing each bundle, and writing out the filtered sequence values. Speaking in adaptor + algorithmic terms, I want to zip the inputs, filter, and write to zipped outputs. I could also say zip + copy_if.

Codegen was tested against clang 20.10, with -O3 -std=c++23.
Here is a CompilerExplorer of my test setup: https://godbolt.org/z/9cnrG98T3

This is an anonymized version of my actual code, which doesn't actually use vectors. Using vector bloats the code a bit, but the outputs are basically the same, as far as size differences.

My raw indexed loop

// ~300 assembly instructions
    for (size_t i = 0; i < input_A.size(); i++)
    {
        auto test_elem = input_A[i];

        if (PassTest(test_elem))
        {
            output_A.push_back(test_elem);
            output_B.push_back(input_B[i]);
            output_C.push_back(input_C[i]);
        }
    }

Ranges version

// ~200 assembly instructions
    auto output = std::views::zip(output_A, output_B, output_C);

    auto result = std::ranges::copy_if(std::views::zip(input_A, input_B, input_C),
        output.begin(),
        [](const auto& bundle) {
            auto [a, b, c] = bundle;
            return PassTest(a);
        });
    
    const size_t copied_count = result.out - output.begin();
    output_A.resize(copied_count);
    output_B.resize(copied_count);
    output_C.resize(copied_count);

This is my flux version. I originally had output_to chained to .filter, but I couldn't figure out how to get the count of items that actually got thru filter. Not a huge deal, but I suppose a little less ideal to look at. I also don't know if this is the idiomatic way you expected. I actually had a fairly difficult time writing this code, because I wrote this before I wrote the ranges version. I think if I had written the ranges one first, I would have been able to write this one much quicker, because the structure is basically identical (which I'm sure you intended)

// ~400 assembly instructions
    auto out_zip = flux::zip(flux::mut_ref(output_A), flux::mut_ref(output_B), flux::mut_ref(output_C));
    
    auto filtered_seq = flux::zip(flux::ref(input_A), flux::ref(input_B), flux::ref(input_C))
    .filter([](auto bundle){ 
        auto [a, b, c] = bundle;
        return PassTest(a);
    });

    filtered_seq.output_to(out_zip.begin());

    const auto filtered_count = filtered_seq.count();

    output_A.resize(filtered_count);
    output_B.resize(filtered_count);
    output_C.resize(filtered_count);

Looking forward to hearing how I could have done this better!

[tcbrindle]

Hi @robbiesri, thanks for the question!

The first thing to say is that flux::output_to returns the updated iterator, so it's possible to capture this and use it to get the filtered_count as you do in the ranges version, without the second pass:

auto result = flux::zip(flux::ref(input_A), flux::ref(input_B), flux::ref(input_C))
    .filter([](auto bundle){ 
        auto [a, b, c] = bundle;
        return PassTest(a);
    })
    .output_to(out_zip.begin());

const size_t copied_count = result.out - output.begin();

That's an immediate improvement, but then I started thinking about how what other improvements we could make. I think what we'd really like to do is to push_back to each of the three vectors whenever we have an element that passes the filter -- expanding all the vectors only to resize them back down again later doesn't seem ideal. One way to do this would be to use for_each after the filter:

flux::zip(flux::ref(input_A), flux::ref(input_B), flux::ref(input_C)))
    .filter([](auto bundle) {
        auto [a, b, c] = bundle;
        return PassTest(a);
    })
    .for_each([](auto bundle) {
        auto [a, b, c] = bundle;
        output_A.push_back(a);
        output_B.push_back(b);
        output_C.push_back(c);
    });

If we wanted to, we could avoid having to manually use structured bindings by using flux::unpack, which makes the code look a little nicer:

flux::zip(flux::ref(input_A), flux::ref(input_B), flux::ref(input_C)))
    .filter(flux::unpack([](auto a, auto, auto) {
        return PassTest(a);
    }))
    .for_each(flux::unpack([](auto a, auto b, auto c) {
        output_A.push_back(a);
        output_B.push_back(b);
        output_C.push_back(c);
    }));

This is probably as close to idiomatic as we can make it in terms of building up a data pipeline.

If I were writing the code though, I would probably be tempted to go a little further, and "inline" the filter condition into the for_each function:

flux::zip(flux::ref(input_A), flux::ref(input_B), flux::ref(input_C)))
    .for_each(flux::unpack([](auto a, auto b, auto c) {
        if (PassTest(a)) {
            output_A.push_back(a);
            output_B.push_back(b);
            output_C.push_back(c);
       }
    }));

The reason for this is that I know that Flux has a special function for doing zip(x, y, z...).for_each(f), called zip_for_each(f, x, y, z...). Using this is potentially more efficient as we don't need to form a tuple that we immediately unpack. It's also a bit nicer syntax-wise, as it doesn't need to explicitly ref the input vectors:

flux::zip_for_each([](auto a, auto b, auto c) {
        if (PassTest(a)) {
            output_A.push_back(a);
            output_B.push_back(b);
            output_C.push_back(c);
       }, input_A, input_B, input_C);

I think this is about as nice as I can make it. I tried it on Compiler Explorer and it ended up generating more assembly. I'm pretty sure this is because it needs to generate the code to handle expanding each of the three vectors, even though that code will never be hit because you're reserve()-ing enough space up front. I'd expect the actual run-time performance of this code to be on a par with the raw loop version.

I hope this helps, and thanks for your interest in Flux! If you have any more questions please feel free to post them.

[robbiesri]

The first thing to say is that flux::output_to returns the updated iterator,

I knew that, because I did it with ranges, and it didn't even register that I could do the same with flux -_-. Again, I wrote the flux code first, which threw me off. Sigh, thank you!

The progression here is great, thank you @tcbrindle . I really like that zip_for_each version. In my head, I was kinda stuck to wanting to have clear in and out zips, but that compact form is so nice.

The resizing in my examples is slightly bogus. I just needed something to share that runs. In my actual code, I have stack allocators that are trivial to grow and shrink (compared to vector at least). So I alloc enough to fit max output, then just decrement the size at the end to fit the actual result. Compared to the vector impl, that code doesn't need the re-alloc checks inside the loop.