[boost] [range] Performance benchmarks?
Beman Dawes
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. 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?
--Beman
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Mathias Gaunard
> 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);
Dave Abrahams
on Wed Feb 01 2012, Mathias Gaunard <mathias.gaunard-AT-ens-lyon.org> wrote:
> 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.
No, a range is not _necessarily_ a pair of begin/end iterators. We're
explicitly interested in what happens to efficiency when algorithms are
/implemented/ using range primitives rather than by iterator
increment, comparison, etc.
Andrei Alexandrescu's "Iterators Must Go" suggests a model where there
are no iterator operations visible in algorithm implementations.
--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com
Mathias Gaunard
>
> on Wed Feb 01 2012, Mathias Gaunard<mathias.gaunard-AT-ens-lyon.org> wrote:
>
>> 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.
>
> No, a range is not _necessarily_ a pair of begin/end iterators.
They are in Boost, and in particular in Boost.Range, which was being
asked about here.
Dave Abrahams
on Wed Feb 01 2012, Mathias Gaunard <mathias.gaunard-AT-ens-lyon.org> wrote:
> On 02/01/2012 10:19 PM, Dave Abrahams wrote:
>>
>> on Wed Feb 01 2012, Mathias Gaunard<mathias.gaunard-AT-ens-lyon.org> wrote:
>>
>>> 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.
>>
>> No, a range is not _necessarily_ a pair of begin/end iterators.
>
> They are in Boost, and in particular in Boost.Range, which was being
> asked about here.
I understand. Maybe Beman didn't know that Boost.Range ranges were
iterator pairs. In the end,
We're explicitly interested in what happens to efficiency when
algorithms are /implemented/ using range primitives rather than by
iterator increment, comparison, etc.
--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com
Thorsten Ottosen
> 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.
I have to say, I haven't compared the generated assembler.
-Thorsten
Thorsten Ottosen
>
> on Wed Feb 01 2012, Mathias Gaunard<mathias.gaunard-AT-ens-lyon.org> wrote:
>> They are in Boost, and in particular in Boost.Range, which was being
>> asked about here.
>
> I understand. Maybe Beman didn't know that Boost.Range ranges were
> iterator pairs. In the end,
>
> We're explicitly interested in what happens to efficiency when
> algorithms are /implemented/ using range primitives rather than by
> iterator increment, comparison, etc.
>
Well, the only way to answer that is by implementing Alexandrescu's
range abstractions and start comparing it with BoostRange. Not trivial
IMO. Then make sure that the underlyigng algorithms/loop-unrolling are
exactly the same. So basically, a huge (but very interesting) work.
An advantage of range primitives is whever we need to store a predicate
or functor; in Boost.Range, we need to store one in each iterator which
is not optimal (clever implementation of
transform_iterator/filter_iterator would optimize this away for empty
functors/predicates).
Again, I don't know what the speed difference will be between the two
ideas; If the data being processed is large, I guess storing an extra
function in the end iterator is of no significance.
The iterator-based range library also seem to work well with the
existing standard library;
-Thorsten
Thorsten Ottosen
>> 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.
Well, sometimes the high-leve range adaptors can make better decisions.
For exmple, assuming the adaptors don't turn the iterators into
bidirectional iterators, boost::push_back( out_range, ... ) will
only grow the output vector once. Of course, the old version can call
reserve(), if people remember that.
OTOH, range adaptors sometimes inhibit (manual) loop-unrolling. For
example, copy_if( ... ) can unroll the inner loop for random access
iterator wheres copy( ... | filtered(...) ...) cannot.
I suspect that the difference is minor because the iterator comparison
will be dwarfed by the cost of calling the predicate and copying the value.
-Thorsten
Julian Gonggrijp
> Den 02-02-2012 03:00, Dave Abrahams skrev:
>>
>> We're explicitly interested in what happens to efficiency when
>> algorithms are /implemented/ using range primitives rather than by
>> iterator increment, comparison, etc.
>>
>
> Well, the only way to answer that is by implementing Alexandrescu's range abstractions and start comparing it with BoostRange. Not trivial IMO. Then make sure that the underlyigng algorithms/loop-unrolling are exactly the same. So basically, a huge (but very interesting) work.
It's definitely not trivial, but couldn't such a library be a very
exciting addition to Boost? Not just because of the benchmarking
opportunity but because of the possibility to pioneer into potential
(far) future additions to the standard?
If "ranges as a primitive" is deemed promising enough to invest effort
into, perhaps we should try to start a joint initiative? Say, set up a
github repository, using some existing libraries like Boost.Container
as seeds, and collaborate on it with as many Boost members as can be
motivated to make a (small) contribution...
Wild ideas aside: I read Andrei Alexandrescu's slides, and I figure
not everyone might agree to what he's saying. If anyone knows about a
clever critical response, I would be most interested to hear.
For completeness, here are the slides:
http://www.uop.edu.jo/download/PdfCourses/Cplus/iterators-must-go.pdf
And here's a short article by the same author which also touches on
random access ranges:
http://www.informit.com/articles/printerfriendly.aspx?p=1407357
-Julian