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-14 23:48:33

At Thu, 14 Oct 2010 20:00:15 +0100,
Mathias Gaunard wrote:
> 
> 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?

I fear this conversation is becoming uncivil.

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

That's what "if" statements are for.

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

Yes, they are different, because you don't need to do that test at the
lowest level, for each element.  That test would only be done at the
segment level.

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

Unless you process the uneven end bits with non-SIMD code.

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

Don't have one handy, sorry. :-(

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com