serpent7776/cpp-ranges-bench

Comparison of C++ ranges performance for filter-take-enumerate-reverse case

cpp-ranges-bench's Issues

Benchmarks should avoid intermediate storage

The intro to the blog post notes that filter -> reverse is a tricky combination for ranges libraries. Because of this, most of the benchmarks save the results of the filter into a temporary vector and then reverse that.

However, the C like benchmark says that it "collects the result in a vector and when it's done, it reverses it in-place".

But we can of course do the equivalent -- collect in forward order, then reverse in-place at the end -- for other libraries too, so that they can also avoid any intermediate storage. For example, changing the Flux code to:

std::vector<Out> fluxranges(const std::vector<Data>& v, std::predicate<Data> auto accept, size_t max_items)
{
    auto found = flux::zip(flux::ints(), flux::ref(v).filter(accept).take(max_items))
                    .map([](const auto& it){
                        return Out{.n=uint64_t(std::get<0>(it)), .id=std::get<1>(it).id, .name=std::get<1>(it).name};
                    })
                    .template to<std::vector>();
    flux::inplace_reverse(found);
    return found;
}

results in a much fairer comparison, as the solutions are now doing the same amount of work. Equivalent changes can be made for the std ranges and range-v3 functions as well, and all result in speedups for most of the tests.

Bug in Flux test

Hi @serpent7776,

I'm the author of the Flux library. Unfortunately Flux didn't do very well in your recent blog post, but it seems that this might be because of a bug in the test case.

On line 246:

cpp-ranges-bench/test.cpp

Lines 244 to 246 in 934135e

	std::vector<Out> fluxranges(const std::vector<Data>& v, std::predicate<Data> auto accept, size_t max_items)
	{
	auto filtered = flux::from(std::move(v)).filter(accept).take(max_items);

you're calling flux::from(std::move(v)), which tells Flux to take ownership of v. Unfortunately, because v is a const std::vector, it's not movable, so this is causing the whole input vector to be copied at every entry to the function!

Calling flux::ref(v).filter(accept).take(max_items) instead will iterate over v by reference, meaning no copy will be made. With this change, the timings for Flux (in my tests) are much more in line with the other libraries.