Boost logo

Boost :

Subject: Re: [boost] Accelerating algorithms with SIMD - Segmented iterators and alternatives
From: Mathias Gaunard (mathias.gaunard_at_[hidden])
Date: 2010-10-11 17:50:29

On 11/10/2010 16:37, David Abrahams wrote:

>> and ideas about whether there is sufficient interest in the
>> alternative to iterators for me to develop them. The intent would
>> be to submit both the alternative to iterators and the SIMD helpers
>> to Boost.
> Now that your misconceptions about segmented iterators are cleared up,
> could you give a brief rundown of your alternative and its advantages?
> If all I have to do is read your earlier post and ignore claims of
> broken compatibility, just say so, but I don't want to waste time
> trying to decipher it if it's substantially wrong.

Here, I will only be talking of the full generator I described in that
other thread, not the step one.

It's push instead of pull, basically.

- It's a very simple, easy-to-grasp concept, it's basically just
allowing ranges to define their own for_each (I use an output iterator
in my example, but it's not really different from a function object)
- It is very easy to write an iteration primitive with it. See the
difference between binary_tree_iterator and binary_tree_generator. I
don't think a segmented iterator would be that easy to define for that
data structure.
- It is iteration governed by the data, rather than by the program that
wants to use the data. Therefore the iteration can have full knowledge
of the data layout and doesn't need to do useless operations at every
increment, since that information can be statically known from the place
the iteration is at, allowing it to be as efficient as possible. This is
also useful for when you have to wait for data, such as when you want to
iterate data coming from a network, which is typically done with a
reactive paradigm.
- It can be converted into a forward iterator through a "simple"
coroutine application. I still need to benchmark this to see how much of
a cost it is, but I'm no good at benchmarking.

Of course, there is the drawback that it makes the code using the
iteration primitive somewhat more complicated: but so do segmented
There are also several other drawbacks, in particular tied to the fact
that it cannot be conceptually much more than a forward iterator.

There is also an extra advantage I hadn't considered that I thought of
when considering SIMD:
- It is possible to push different types of data and have them
statically dispatched through overloading. Heterogeneous structures with
a pull paradigm require a dynamic dispatch.

I was in particular thinking of using this latter advantage so that the
iteration could dispatch its contents to the algorithm
element-by-element at the borders and pack-by-pack for the rest.

Of course I didn't introduce this idea as SIMD my main concern, I just
saw a potential useful application there.

Now, I'm not saying we should embrace push instead of pull; I think both
approaches should be allowed to co-exist, and that we should probably
try to standardize concepts and allow interoperability with other range
and iterator algorithms and adapters.
But this raises several questions: How do we choose between the two? How
do we integrate the approaches?

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