Boost logo

Boost :

Subject: Re: [boost] Accelerating algorithms with SIMD - Segmented iterators and alternatives
From: David Abrahams (dave_at_[hidden])
Date: 2010-10-15 12:15:54

At Thu, 14 Oct 2010 23:27:21 -0700,
Jeffrey Lee Hellrung, Jr. wrote:
> > 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...

Eric knows more about this than I do. Eric?

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

Some things definitely become significantly more complicated to implement.

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

Anything that requires bidirectional or random access, for example.

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

np. Glad this topic is getting some much-needed exposure.

Dave Abrahams
BoostPro Computing

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