Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at