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

Subject: Re: [boost] Accelerating algorithms with SIMD - Segmented iterators and alternatives
From: David Abrahams (dave_at_[hidden])
Date: 2010-10-13 11:00:15

At Wed, 13 Oct 2010 10:52:36 +0100,
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, ...
> 
> Yes, since those require either bidirectional or random access iterators.

Actually, all of those can be done with bidirectional iterators
(although the standard over-constrains sort).  binary_search can be
done with forward 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++.

Nooo.  Waaay too far from the machine model.  If we're talking about
HPC, let's figure out how to generate optimal (or near-optimal) code.

> 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 believe that segmented iterators do allow them to be efficient.

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

I don't believe you have to choose.

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

binary_search (equal_range, lower_bound, upper_bound), rotate, equal,
transform (2-input version), includes, merge...

These were just the first ones I encountered in the algorithms section
of http://www.sgi.com/tech/stl/stl_index_cat.html

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

Oh, I think I see what you're getting at.  Solving that problem for
segmented iterators would be interesting.

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

Just as with flat containers, some segmented iterators for
hierarchical containers can do random-access and some can't.
std::deque is an example that can.  I don't think recursive
segmentation is an obstacle as long as all the sizes are constant at
the leaves.

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

I'm not sure what you're getting at here, again.  Is it relevant?

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com