Boost logo

Boost :

Subject: Re: [boost] Accelerating algorithms with SIMD - Segmented iterators and alternatives
From: David Abrahams (dave_at_[hidden])
Date: 2010-10-14 23:41:26

At Thu, 14 Oct 2010 08:07:47 -0700,
Jeffrey Lee Hellrung, Jr. wrote:
> 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.

Sorry, no, I was the one who missed something. Please allow me to
correct what I said.

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

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

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

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

It's exactly the same problem that the iterators of std::deque has.

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

I acknowledge that you retracted that analysis in a later post.

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

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

Dave Abrahams
BoostPro Computing

Boost list run by bdawes at, gregod at, cpdaniel at, john at