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-13 05:52:36

On 12/10/10 09:06, David Abrahams wrote:

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

Yes, since those require either bidirectional or random access iterators.

Ability to stop the iteration could be a useful addition to make the 
concept have more applications.
In functional languages, people seem happy to use exceptions for that; 
but I assume that certainly wouldn't be the case in C++.

In any case, linear operations or filters represent in my opinion a 
large enough spectrum of what people do with iterable ranges of data 
that it could be worthwhile to have concepts that allow them to be 
efficient, even if it cannot apply to other cases.

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

But do we want generic capability at the cost of complicated code which 
is hard to optimize?

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

Do you have some examples?

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

struct my_iteration
{
     void operator()(float f)
     {
         do_something_with_scalar(f);
     }

     void operator()(packed_view<float, 4> v)
     {
         do_something_with_vector(v);
     }
};

for_each(simd::packed_range(mystuff), my_iteration());

vs

for(packed_view<float, 4> v : simd::packed_range(mystuff))
    do_something_with_vector(v);

Using a pull solution for iteration, the former /could/ take care of the 
non-aligned cases at the beginning and at the end of the mystuff range 
through overloading.

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

Segmented iterators still allow bidirectional support, indeed (I think?).
But I'm note sure it can do random access as well, if you consider 
recursively segmented local iterators.

I believe writing a zip_iterator (or similar) would be no easier for 
segmented iterators than for generators due to the arbitrary recursion.