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
> 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)
> void operator()(packed_view<float, 4> 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?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk