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

Subject: Re: [boost] Accelerating algorithms with SIMD - Segmented iterators and alternatives
From: Jeffrey Lee Hellrung, Jr. (jhellrung_at_[hidden])
Date: 2010-10-13 06:44:37

On 10/13/2010 02:52 AM, Mathias Gaunard wrote:
> On 12/10/10 09:06, David Abrahams wrote:
>
>> Nice for very linear things. Not so great for sort, binary_search,
>> reverse, rotate, ...
[...]
> 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.

I could see this.

[...]
>>> 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?

find_if?  adjacent_find?  adjacent_difference?  parallel_for_each?  I 
suppose (some of) these could be implemented using a for_each-style of 
iteration, but would require caching (of the previously visited element, 
in the case of adjacent_*) and exceptions (in the case of 
find_if/adjacent_find)...which would seem to negate the performance 
motivation.  Or maybe I'm being too dense...

[...]
>>> - 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());

One might describe this as expressing iteration in terms of the visitor 
pattern...?  I honestly didn't understand what you meant between "push" 
and "pull" before this snippet.

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

Seems to me segmented iterators and a visitation-based/push-based 
iteration address fundamentally different problems.  At least, I don't 
see how segmented iterators help here.  The problem that 
visitation-based iteration seems to try to solve is improving iteration 
efficiency over join(t)_range-like ranges...

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

What do you mean by generators in this context?

- Jeff