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-13 12:09:38

On 13/10/10 16:00, David Abrahams wrote:
> At Wed, 13 Oct 2010 10:52:36 +0100,
> Mathias Gaunard wrote:
>>
>> On 12/10/10 09:06, David Abrahams wrote:
>>
>>> Nice for very linear things.  Not so great for sort, binary_search,
>>> reverse, rotate, ...
>>
>> Yes, since those require either bidirectional or random access iterators.
>
> Actually, all of those can be done with bidirectional iterators
> (although the standard over-constrains sort).  binary_search can be
> done with forward iterators.

I didn't know binary_search (and similar functions) worked with forward 
iterators. I have trouble seeing how they could work effectively at all.

>> But do we want generic capability at the cost of complicated code
>> which is hard to optimize?
>
> I don't believe you have to choose.

Segmented iterators are neither practical to write nor to use.
ou've

> rotate,

Interesting one, because it modifies itself.
I'm not convinced it's not possible to write it.

 > equal,
> transform (2-input version), includes, merge...

Indeed, there is a combination problem.

>> I believe writing a zip_iterator (or similar) would be no easier for
>> segmented iterators than for generators due to the arbitrary
>> recursion.
>
> I'm not sure what you're getting at here, again.  Is it relevant?

Well, the limitation is how you can combine those "generators" to 
iterate several at the same time, be it for merge or otherwise.

I don't see a good way to do this with segmented iterators either.