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-15 02:27:21

On 10/14/2010 8:41 PM, David Abrahams wrote:
> At Thu, 14 Oct 2010 08:07:47 -0700,
> Jeffrey Lee Hellrung, Jr. wrote:
[...]
> 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.
[...]
>> 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.
[...]
>> 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.

If you can provide more direction here, I would appreciate it.  There is 
boost::fusion::joint_view, but that only concatenates 2 Boost.Fusion 
sequences, not 2 ranges...

By the way, I did run a comparison between a segmented iteration, with 
nested for-loops, and a flattened iteration.  I was very much surprised 
in the runtime difference.  It obviously depends on the operation you do 
per iteration, but for just incrementing a counter, the difference was 2 
or 3 orders of magnitude.  Needless to say, I'm more convinced of the 
value of exposing the segmentation of data structures now.

Here's what I'm getting from this discussion:  I see 2 viable approaches 
to address iteration over non-linear data structures, where efficiency 
is a major concern.  One is an external, segmented iterator interface, 
possibly enriched to enable iteration over Boost.Fusion sequences at any 
depth.  The other is an internal "push" or visitation iteration 
suggested originally by Mathias.  Neither models seem to yield 
*convenient* implementations of *all* iteration algorithms in 
<algorithm>, but I can see enough utility that one model and/or the 
other would be worth investigating.  I'm not sure yet if either 
iteration model is more powerful than the other, though it seems there 
are some algorithms expressable via segmented iteration that would be 
challenging to express via push iteration.

In any case, David, I appreciate your patience and participation.

- Jeff