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
>> 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
>> 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
> 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
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk