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

Subject: Re: [boost] Accelerating algorithms with SIMD - Segmented iterators and alternatives
From: Jeffrey Lee Hellrung, Jr. (jhellrung_at_[hidden])
Date: 2010-10-13 15:08:43

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.  1) It doesn't play nice with standard C++ 
looping constructs, specifically for loops.  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.

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), 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