Re: [boost] Accelerating algorithms with SIMD - Segmented iterators and alternatives

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
http://www.boostpro.com