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. 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
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);
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
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.
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
Den 02-02-2012 03:00, Dave Abrahams skrev:
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 wrote:
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
Den 01-02-2012 18:02, Mathias Gaunard skrev:
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
Den 01-02-2012 18:02, Mathias Gaunard skrev:
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.
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
participants (5)
-
Beman Dawes -
Dave Abrahams -
Julian Gonggrijp -
Mathias Gaunard -
Thorsten Ottosen