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-14 23:41:26

At Thu, 14 Oct 2010 08:07:47 -0700,
Jeffrey Lee Hellrung, Jr. wrote:
> 
> On 10/14/2010 1:23 AM, David Abrahams wrote:
> > At Wed, 13 Oct 2010 12:08:43 -0700,
> > Jeffrey Lee Hellrung, Jr. wrote:
> [...]
> >> Yes.  But I'm not convinced yet that iterators exposing the
> >> segmentation of the data structure are the right solution to
> >> presenting a flattened view of that data structure.
> >
> > Good; that's not what they're for ;-)
> 
> I think I missed something, then.  

Sorry, no, I was the one who missed something.  Please allow me to
correct what I said.

Presenting a flattened view of a hierarchical data structure kills
performance.  Segmented iterators expose an additional non-flattened
view so that appropriately constructed algorithms can avoid that
performance loss...

> Are we not applying sequential algorithms (e.g., fill, for_each,
> ...) to hierarchical data structures?

...where by "appropriately constructed," I mean algorithms that have
been re-cast hierarchically.  "Sequentialness" is not necessarily
implied.

> >> 1) It doesn't play nice with standard C++ looping constructs,
> >> specifically for loops.
> >
> > The whole point of hierarchical algorithms is to avoid flat loops for
> > segmented data structures.
> 
> It certainly avoids flat loops, to the point of outright precluding
> their use.  I can add here a 1a) How would you go about iterating
> through segmented data structures in parallel?

You mean two at once?  I think you have to produce a new segmentation
structure that bounds segments at the union of all segment boundaries
in the two sequences.  I would probably do that with a segmented zip
view.

> >> 2) I have yet to see a benchmark comparison between segmented
> >> iterators and alternatives (other than a side-note claim in the
> >> paper).  I'm open to looking at some specific comparisons if one has
> >> already done this, and this is something I'm interested enough in that
> >> I might try to do myself.  Seems to me a more general solution is a
> >> "flat_multirange_iterator" templated on the outer range and the
> >> "segmentation depth".  I.e., a flat_multirange_iterator<  vector<
> >> vector<T>  >, 2>  would iterate over the T's.
> >
> > That's gonna be slow.  Lots of testing and branching.
> >
> >    "Note that the joined range incurs a performance cost due to the
> >    need to check if the end of a range has been reached internally
> >    during traversal."
> 
> First, that quote applies directly to a join_iterator, though I'll
> give you that it *may* apply to my hypothetical a
> flat_multirange_iterator. 

It's exactly the same problem that the iterators of std::deque has.

> What I'm having trouble with is it *looks* to me like you have the
> same tests and branches with a segmented iterator as with a
> flat_multirange_iterator.

I acknowledge that you retracted that analysis in a later post.

> >> To address your claim that "that's the same problem ... that segmented
> >> iterators are solving", what I meant by a join_range or joint_range
> >> is, essentially, a flattened out Boost.Fusion sequence of ranges of
> >> *differing* types (but with compatible value_type's and
> >> references). E.g., the thing that boost::join [1] returns.
> >> Segmented iterators can't deal with such ranges (at least with a
> >> strict reading of Austern's paper),
> >
> > I don't see why you say that.
> 
> Show me what the equivalent nested for-loop looks like if a join_range
> can be "segmentedly" iterated over.  

Well, things get complicated when the element types or structure of a
single sequence are heterogeneous.

> If I tried, I'd be inclined to write a for-loop over a Boost.Fusion
> sequence.

Yeah, you need to do something like that.

> If you want to include a join_iterator within the family of
> segmented iterators, you'd have to enrich the interface of segmented
> iterators to include Boost.Fusion sequences.  Is that desirable?

IIUC, there already is support for segmented Boost.Fusion iterators
somewhere.

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