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

Subject: Re: [boost] Accelerating algorithms with SIMD - Segmented iterators and alternatives
From: Mathias Gaunard (mathias.gaunard_at_[hidden])
Date: 2010-10-14 15:00:15

On 13/10/10 18:50, David Abrahams wrote:

> I think you mean
>
>    1 2 | 3 4 5 6 | 7 8 9 10 | 11

What is that nonsense supposed to be?

All elements are of type pack<int, 4>, and therefore must have four values.

> right?  Are you really intending to manufacture zeros for padding?

Right, that was the very idea of the feature.

> Yes, this is exactly the same problem as std::deque has

No it isn't.
std::deque is not a different *behaviour* problem, it's a different 
*location* problem.

> which
> segmented iterators were designed for.

They do not help *at all* in this case, since the iterator of each 
segment must have the same type, and therefore *the same behaviour*.

>
>> I thought segmented iterators would solve this, since after all I've
>> got three segments, and you've been repeatedly saying on this list
>> that it is the solution to many iterator problems, but they
>> don't.
>
> Of course they do.

You just demonstrated a bit lower that they didn't.

> I think they do.  However, you might find that you need some dynamic
> dispatching to get it to work.  In other words,
>
>    if (operating on complete segment)
>       SIMD algorithm
>    else
>       elementwise algorithm

Therefore they do not allow to avoid the inefficiency, and they are no 
different from standard iterators in that respect.

>
>> My alternative not only does, but it could also allows not to have to
>> pad the ranges with zeroes, which is potentially more interesting to
>> write SIMD-aware algorithms.
>
> You don't need to pad with zeroes for segmented iterators.

Yes you do, since all elements must have the same type, a limitation 
that /could/ be lifted by using a for_each-like syntax.
The value type is a pack of 4 integers loaded in a single SIMD register. 
You must give a value to all four of them.

> I do know that it can address std::merge.  It's not necessarily
> pretty, though. ;-)

I would quite like to see any reference on this.