Re: [boost] Accelerating algorithms with SIMD - Segmented iterators and alternatives

Subject: Re: [boost] Accelerating algorithms with SIMD - Segmented iterators and alternatives
From: David Abrahams (dave_at_[hidden])
Date: 2010-10-12 04:06:02

At Mon, 11 Oct 2010 22:50:29 +0100,
Mathias Gaunard wrote:
> 
> On 11/10/2010 16:37, David Abrahams wrote:
> 
> >> and ideas about whether there is sufficient interest in the
> >> alternative to iterators for me to develop them.  The intent would
> >> be to submit both the alternative to iterators and the SIMD helpers
> >> to Boost.
> >
> > Now that your misconceptions about segmented iterators are cleared up,
> > could you give a brief rundown of your alternative and its advantages?
> > If all I have to do is read your earlier post and ignore claims of
> > broken compatibility, just say so, but I don't want to waste time
> > trying to decipher it if it's substantially wrong.
> 
> Here, I will only be talking of the full generator I described in that 
> other thread, not the step one.
> 
> It's push instead of pull, basically.
> 
> - It's a very simple, easy-to-grasp concept, it's basically just 
> allowing ranges to define their own for_each (I use an output iterator 
> in my example, but it's not really different from a function object)

Nice for very linear things.  Not so great for sort, binary_search,
reverse, rotate, ...

> - It is very easy to write an iteration primitive with it. See the 
> difference between binary_tree_iterator and binary_tree_generator. I 
> don't think a segmented iterator would be that easy to define for that 
> data structure.

It may not matter that it isn't easy, if you really want generic capability.

> - It is iteration governed by the data, rather than by the program that 
> wants to use the data. Therefore the iteration can have full knowledge 
> of the data layout and doesn't need to do useless operations at every 
> increment, since that information can be statically known from the place 
> the iteration is at, allowing it to be as efficient as possible. This is 
> also useful for when you have to wait for data, such as when you want to 
> iterate data coming from a network, which is typically done with a 
> reactive paradigm.
> - It can be converted into a forward iterator through a "simple" 
> coroutine application. I still need to benchmark this to see how much of 
> a cost it is, but I'm no good at benchmarking.

Reading through
http://github.com/boost-lib/parameter/blob/master/test/efficiency.cpp
might help.

> Of course, there is the drawback that it makes the code using the
> iteration primitive somewhat more complicated: but so do segmented
> iterators.  There are also several other drawbacks, in particular
> tied to the fact that it cannot be conceptually much more than a
> forward iterator.

...nor even implement several of the algorithms that work with forward
iterators.

> There is also an extra advantage I hadn't considered that I thought of 
> when considering SIMD:
> - It is possible to push different types of data and have them 
> statically dispatched through overloading. Heterogeneous structures with 
> a pull paradigm require a dynamic dispatch.

I'm sorry, I can't understand what you're driving at here.

> I was in particular thinking of using this latter advantage so that the 
> iteration could dispatch its contents to the algorithm 
> element-by-element at the borders and pack-by-pack for the rest.
> 
> Of course I didn't introduce this idea as SIMD my main concern, I just 
> saw a potential useful application there.
> 
> Now, I'm not saying we should embrace push instead of pull; I think both 
> approaches should be allowed to co-exist, and that we should probably 
> try to standardize concepts and allow interoperability with other range 
> and iterator algorithms and adapters.
> But this raises several questions: How do we choose between the two? How 
> do we integrate the approaches?

Although what you're describing is easier to make efficient for many
(perhaps even the majority of cases), it doesn't sound like it
actually has the same level of generality as segmented iterators do.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com