Re: [boost] [range] Performance benchmarks?

Subject: Re: [boost] [range] Performance benchmarks?
From: Mathias Gaunard (mathias.gaunard_at_[hidden])
Date: 2012-02-01 12:02:55

On 02/01/2012 04:39 PM, Beman Dawes wrote:
> A question came up in a long bikeshed discussion on a C++ committee
> mailing list as to the performance of range based interface versus a
> begin/end iterator interface (I.E. traditional STL interface) to the
> same algorithms.

It's exactly the same performance, because a range is just a pair of 
begin/end iterators and all the code is implemented using the iterators.

> Out of curiosity, I checked the Boost.Range docs, but
> didn't see any performance measurements.
>
> It might encourage potential users to take the leap if the Boost.Range
> "Introduction" page made some mention of performance implications for
> use of the Boost library.
>
> The intro gives a "Push the even values from a map in reverse order
> into the container target" example:
>
>       // Assume that is_even is a predicate that has been implemented
> elsewhere...
>       push_back(target, my_map | map_values | filtered(is_even()) | reversed);
>
> Are there any benchmarks available for this?  What does the straight
> STL version of the code look like?

What it seems you want to compare is not ranges vs iterators, but rather 
algorithms vs range/iterator adaptors.

It really depends on what you call the STL version. There are many ways 
to write this.

std::vector<Map::mapped_type> my_map_values;
std::transform(my_map.begin(), my_map.end(), 
std::back_inserter(my_map_values), [&](Map::value_type const& v) { 
return v.second; } );
std::copy_if(my_map_values.rbegin(), my_map_values.rend(), 
std::back_inserter(target), is_even());

This version is necessarily worse for large map sizes because it 
includes a "my_map_values" temporary. If you allow the use of a 
transform_iterator adaptor like the one in Boost, then the temporary can 
be avoided.

I chose to use the built-in standard reverse iterators, but std::reverse 
could have been used too instead.

Another possible version without any algorithm is

foreach(auto const& i : make_range(my_map.rbegin(), my_map.rend()))
   if(is_even(i.second))
     target.push_back(i.second);