Are filtered iterator loops (with boost) faster than classical for loop with an if condition inside

bobinthebox 0
Viewed 35

I'm a C++ newbie, and I'm trying to understand some boost capabilities. Looking at the top answer to this question, I've seen this snippet:

#include <boost/range/adaptor/filtered.hpp>
#include <iostream>
#include <vector>

struct is_even
{
    bool operator()( int x ) const { return x % 2 == 0; }
};

int main(int argc, const char* argv[])
{
    using namespace boost::adaptors;

    std::vector<int> myCollection{1,2,3,4,5,6,7,8,9};

    for( int i: myCollection | filtered( is_even() ) )
    {
        std::cout << i;
    }
}

Is there any advantage in terms of complexity w.r.t the classical approach, i.e. the for loop plus an if condition inside it? If so, how is that possible? I don't see the rationale behind it.

boost c++14 performance filter c++
1 Answers

Is there any advantage in terms of complexity w.r.t the classical approach, i.e. the for loop plus an if condition inside it?

No. You can compare the code gen as people have showed you in the comments.

Uhm, then I don't understand the following. In this question I asked ...

Picking the origin of the question from here:

Thanks so much @sehe, I see what you mean. So if I use a filter I have on average O(N log(N)) in time, while with two for loops + the query inside (see edited question) inside I have a O(N M log(N)), correct?

I answered:

Yes. Although it's not depending on the adaptor form. It's depending on the use of the indexing query algorithm. In other words, all the following will have similar performance: https://godbolt.org/z/qdaonP1Pj

The point is not the range-adaptor. The point is the algorithm.

The bgi::query algorithm does not iterate through elements linearly.

Instead, the query uses... the tree structure to optimize. Worst case it would be similar perf (when everything overlaps or when the tree is packed suboptimally). In practice it can matter quite a bit to swap the loops around if e.g. N ⋙ M or when you know one tree is better packed/contains more disjoint shapes than the other.

Key to the optimization is that rtree is a datastructure with specific knowledge of geometrical relations, not just a vector.

Summary

The loop-form isn't the big factor. It's what you iterate over that's optimized by bgi::query. The following should al have similar (if not identical) performance:

Live On Compiler Explorer

#include <boost/geometry.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/function_output_iterator.hpp>
namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
using bgi::adaptors::queried;

void do_something_with_cells(int a, int b) {
    std::cout << "Intersect: " << a << " and " << b << "\n";
}

using P = bg::model::d2::point_xy<int>;
using B = bg::model::box<P>;
using T = bgi::rtree<std::pair<B, int>, bgi::rstar<16> >;

static constexpr std::array data = {
    std::pair(B{{0, 0},  {4,  4}}, 1),
    std::pair(B{{3, 3},  {7,  7}}, 2),
    std::pair(B{{6, 6}, {10, 10}}, 3),
    std::pair(B{{9, 9}, {13, 13}}, 4),
};

int main() {
    for (auto& [b, _] : data)
        if (std::string r; !bg::is_valid(b, r))
            std::cout << bg::wkt(b) << ": " << r << "\n";

    bgi::rtree<std::pair<B, int>, bgi::rstar<16> > a, b;
    a.insert(data.begin(), data.end());
    b.insert(data[1]);
    b.insert(data[3]);

    auto exercise = [](T const& t1, T const& t2) 
    {
        std::cout << "Classic iterators\n";
        for (auto& [box2, cell2] : t2) {
            auto f = bgi::qbegin(t1, bgi::intersects(box2)), l = bgi::qend(t1);
            for (; f != l; ++f) {
                do_something_with_cells(f->second, cell2);
            }
        }

        std::cout << "Output iterator\n";
        for (auto& [box2, cell2] : t2) {
            bgi::query( //
                t1, bgi::intersects(box2),
                boost::function_output_iterator([cell2 = cell2](auto& pair) {
                    do_something_with_cells(pair.second, cell2);
                }));
        }

        std::cout << "Range adaptor\n";
        for (auto& [box2, cell2] : t2) {
            for (auto& [bmatch, cmatch] : t1 | queried(bgi::intersects(box2))) {
                do_something_with_cells(cmatch, cell2);
            }
        }
    };

    exercise(a, b);
    exercise(b, a);
}

Printing

Classic iterators
Intersect: 1 and 2
Intersect: 2 and 2
Intersect: 3 and 2
Intersect: 3 and 4
Intersect: 4 and 4
Output iterator
Intersect: 1 and 2
Intersect: 2 and 2
Intersect: 3 and 2
Intersect: 3 and 4
Intersect: 4 and 4
Range adaptor
Intersect: 1 and 2
Intersect: 2 and 2
Intersect: 3 and 2
Intersect: 3 and 4
Intersect: 4 and 4
Classic iterators
Intersect: 2 and 1
Intersect: 2 and 2
Intersect: 2 and 3
Intersect: 4 and 3
Intersect: 4 and 4
Output iterator
Intersect: 2 and 1
Intersect: 2 and 2
Intersect: 2 and 3
Intersect: 4 and 3
Intersect: 4 and 4
Range adaptor
Intersect: 2 and 1
Intersect: 2 and 2
Intersect: 2 and 3
Intersect: 4 and 3
Intersect: 4 and 4

¹ As I hinted before, in certain worst case there might be a slight overhead over just linearly iterating.

sehe0
Related