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
> >> 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)
> void operator()(packed_view<float, 4> v)
> for_each(simd::packed_range(mystuff), my_iteration());
> for(packed_view<float, 4> v : simd::packed_range(mystuff))
> 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
> I believe writing a zip_iterator (or similar) would be no easier for
> segmented iterators than for generators due to the arbitrary
I'm not sure what you're getting at here, again. Is it relevant?
-- Dave Abrahams BoostPro Computing http://www.boostpro.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk