Boost logo

Boost :

Subject: Re: [boost] Accelerating algorithms with SIMD - Segmented iterators and alternatives
From: Felipe Magno de Almeida (felipe.m.almeida_at_[hidden])
Date: 2010-10-13 16:34:57


On Wed, Oct 13, 2010 at 2:45 PM, David Abrahams <dave_at_[hidden]> wrote:
> At Wed, 13 Oct 2010 17:09:38 +0100,

[snip]

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

I've been watching this thread and I've been thinking of saying my
experience trying to use segmented iterators.

I am working on a project that has a hierarchical structure where an
object can own other objects of the same type. It is a tree-structure.

This hierarchical structure might be acessible hierachically or
not. Conceptually it always is, but it might be accessible only
through input_iterators which would flatinize the hierarchy in a
efficient way. But, some other implementation might be able to access
it hierarchically, which would allow some algorithms, e.g. find, to work
in better-than-a-linear time.

At first I thought that segmented iterators were what I needed. But
then trying to work with it. I found that segmented iterators would
differentiate segment iterators from local iterators in a way that
didn't work in a tree-like structure.

The nodes of the trees had to be moved to be the first in the local
sequence because only local iterators are dereferenced in
segmented-aware algorithms. This meant that segmented iterators
weren't completely overhead-free.

This doesn't mean segmented iterators aren't good, just that the
use-case that I tried didn't seem to fit it.

[snip]

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

Regards,

-- 
Felipe Magno de Almeida

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk