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

Subject: Re: [boost] Accelerating algorithms with SIMD - Segmented iterators and alternatives
From: Eric Niebler (eric_at_[hidden])
Date: 2010-10-16 17:11:11

(Sorry for the delay.)

On 10/15/2010 9:15 AM, David Abrahams wrote:
> 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?

For a long time, Fusion has shipped with half-baked, undocumented,
partial support for segmented Fusion sequences. Everything is under ext_
directories scattered throughout boost/fusion. There are two segmented
algorithms: for_each_s and find_if_s. There is a segmented data
structure: tree. There are primitives: is_segmented, and segments. There
are iterators that make a segmented sequence look flat:
segmented_iterator and iterator_range specialized on segmented_iterators
that is itself segmented.

The segmented_iterator and segmented iterator_range support are by far
the most complicated---and most in dire need of a complete rewrite. But
the implementation was so hair-pullingly horrific that I dare not tread
there again. Aparantly, they've been failing their regression tests for
a while. There's a trac ticket, but I'm scared of it. Yes, really. It's
a perpetual To-Do item.

The benefit of segmented Fusion is that it makes the implementation of
inherently segmented data structures (like trees and joins)
embarrassingly trivial, and it makes iteration over them efficient at
compile time. The trouble with segmented Fusion is that to reap those
benefits, you need a segmented version of each algorithm, many of which
are non-trivial to write. It adds a lot of complexity to Fusion, about
which Joel has expressed concern (not unreasonably, I might add).

So that's where we are.

-- 
Eric Niebler
BoostPro Computing
http://www.boostpro.com