Subject: Re: [boost] sentinels vs iterators
From: Eric Niebler (eniebler_at_[hidden])
Date: 2014-08-21 12:23:54
On 8/21/2014 3:12 AM, Joaquin M Lopez Munoz wrote:
> Eric Niebler <eniebler <at> boost.org> writes:
>> On 08/20/2014 07:40 AM, Beman Dawes wrote:
>>>
>>> See http://beman.github.io/ntcts_iterator/
>>>
>>> or https://github.com/Beman/ntcts_iterator
>>
>> The need for such a thing is an unfortunate side-effect of the fact that
>> a range's begin and end iterators must have the same type. I'm building
>> a range library that loosens that restriction and writing a proposal to
>> get it into the standard.
>
> Hi Eric,
>
> This might be connected in a way with your sentinel idea. Some
> months ago I explored a container-like construct for polymorphic
> objects that group elements by run-time type so as to greatly
> speed up for_each processing:
>
> http://bannalia.blogspot.com.es/2014/05/fast-polymorphic-collections.html
>
> This poly_collection class (currently just a sketch to show the
> underlying ideas) has a for_each member function
>
> template<typename F> F for_each(F f);
>
> that internally dispatches to the different same-type chunks
> the collection is comprised of:
>
> template<typename F>
> F for_each(F f)
> {
> for(const auto& p:chunks)p.second->for_each(f);
> return std::move(f);
> }
>
> The performance gains are massive, as shown in the article. Now, if
> we wished to use the standard for_each algorithm rather than
> the provided member function:
>
> poly_collection<base> c;
> ...
> std::foreach(c.begin(),c.end(),f);
>
> then poly_collection would have to implement an iterator type
> that sequentally traverses all the chunks, which implies a fairly
> expensive increment operation (in pseudocode):
>
> iterator& operator++()
> {
> node+=chunk_element_size;
> if(node==chunk_end()){
> node=next_chunk_begin(node);
> }
> return *this;
> }
>
> That is, incrementing involves checking against chunk end, which,
> combined with the begin!=end check of std::for_each, implies two
> checks per step. This is slower than poly_collection::for_each,
> which can get by with just one check per step.
>
> I wonder: maybe a sentinel-based range can be used so that
> std::for_each(c,f) is as efficient as c.for_each(f) for a
> poly_collection c?
You're looking for segmented iterators and hierarchical algorithms. Matt
Austern wrote a paper about it:
http://lafstern.org/matt/segmented.pdf
Segmented iterators force you to rewrite all the algorithms. They are a
different beast than iterators with sentinels, which are not nearly so
invasive. I'm not proposing segmented iterators.
Eric