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-13 13:45:27

At Wed, 13 Oct 2010 17:09:38 +0100,
Mathias Gaunard wrote:
> 
> I didn't know binary_search (and similar functions) worked with
> forward iterators. I have trouble seeing how they could work
> effectively at all.

O(N) steps, O(log N) comparisons.  Better than linear search if
comparison is not cheap.

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

Why do you say that?  I don't think anyone has made a serious effort.

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

I'd like to see that one.

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

Ah.

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

:-) zip_iterator

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