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 04:23:06

At Wed, 13 Oct 2010 12:08:43 -0700,
Jeffrey Lee Hellrung, Jr. wrote:
> 
> On 10/13/2010 08:04 AM, David Abrahams wrote:
> > At Wed, 13 Oct 2010 03:44:37 -0700,
> > Jeffrey Lee Hellrung, Jr. wrote:
> >> 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...
> >
> > That's the same problem (in essence) that segmented iterators are
> > solving.  Did you read the Austern paper?
> 
> 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 ;-)

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

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

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

> and I think such ranges are closer to what Mathias has in mind (to
> be verified......).  But perhaps I'm just not seeing your
> generalization beyond the immediate scope of the Austern paper?
> 
> - Jeff
> 
> [1]
> http://www.boost.org/doc/libs/1_44_0/libs/range/doc/html/range/reference/utilities/join.html

Looks like this doc is missing something about the value/reference
type requirements, BTW.

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