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-14 11:07:47

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.  Are we not applying sequential 
algorithms (e.g., fill, for_each, ...) to hierarchical data structures?

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

>> 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. 
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.  Comparing the nested for-loop on page 5 of 
the Austern paper (which is what a segmented iterator would give you) 
with the flattened while-loop on page 6 (let's replace the 
while-condition with true put an inserted break statement when !(node != 
nodes.end())), they both have the same number of iterator increments, 
comparisons, and assignments.  What am I missing?  Are compilers just 
able to produce better code for nested for-loops than flattened loops?

>> 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.  If I tried, I'd be inclined to 
write a for-loop over a Boost.Fusion sequence.  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?  Maybe?

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

Yes :(

- Jeff