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

Subject: Re: [boost] Accelerating algorithms with SIMD - Segmented iterators and alternatives
From: Mathias Gaunard (mathias.gaunard_at_[hidden])
Date: 2010-10-11 17:50:29

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)
- 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 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.

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.

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 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?