Subject: [boost] Metaprogrammers, all of you!
From: David Abrahams (dave_at_[hidden])
Date: 2010-10-12 16:20:26
I find it interesting, but also a bit sad, that the thread on
metaprogramming âplumbingâ is very active, while this fundamental
question of abstraction and generic programming has gone unaddressed.
At Tue, 12 Oct 2010 04:06:02 -0400, David Abrahams wrote:
> At Mon, 11 Oct 2010 22:50:29 +0100,
> Mathias Gaunard wrote:
> > On 11/10/2010 16:37, David Abrahams wrote:
> > >> and ideas about whether there is sufficient interest in the
> > >> alternative to iterators for me to develop them. The intent would
> > >> be to submit both the alternative to iterators and the SIMD helpers
> > >> to Boost.
> > >
> > > Now that your misconceptions about segmented iterators are cleared up,
> > > could you give a brief rundown of your alternative and its advantages?
> > > If all I have to do is read your earlier post and ignore claims of
> > > broken compatibility, just say so, but I don't want to waste time
> > > trying to decipher it if it's substantially wrong.
> > Here, I will only be talking of the full generator I described in that
> > other thread, not the step one.
> > It's push instead of pull, basically.
> > - It's a very simple, easy-to-grasp concept, it's basically just
> > allowing ranges to define their own for_each (I use an output iterator
> > in my example, but it's not really different from a function object)
> Nice for very linear things. Not so great for sort, binary_search,
> reverse, rotate, ...
> > - It is very easy to write an iteration primitive with it. See the
> > difference between binary_tree_iterator and binary_tree_generator. I
> > don't think a segmented iterator would be that easy to define for that
> > data structure.
> It may not matter that it isn't easy, if you really want generic capability.
> > - It is iteration governed by the data, rather than by the program that
> > wants to use the data. Therefore the iteration can have full knowledge
> > of the data layout and doesn't need to do useless operations at every
> > increment, since that information can be statically known from the place
> > the iteration is at, allowing it to be as efficient as possible. This is
> > also useful for when you have to wait for data, such as when you want to
> > iterate data coming from a network, which is typically done with a
> > reactive paradigm.
> > - It can be converted into a forward iterator through a "simple"
> > coroutine application. I still need to benchmark this to see how much of
> > a cost it is, but I'm no good at benchmarking.
> Reading through
> might help.
> > Of course, there is the drawback that it makes the code using the
> > iteration primitive somewhat more complicated: but so do segmented
> > iterators. There are also several other drawbacks, in particular
> > tied to the fact that it cannot be conceptually much more than a
> > forward iterator.
> ...nor even implement several of the algorithms that work with forward
> > There is also an extra advantage I hadn't considered that I thought of
> > when considering SIMD:
> > - It is possible to push different types of data and have them
> > statically dispatched through overloading. Heterogeneous structures with
> > a pull paradigm require a dynamic dispatch.
> I'm sorry, I can't understand what you're driving at here.
> > I was in particular thinking of using this latter advantage so that the
> > iteration could dispatch its contents to the algorithm
> > element-by-element at the borders and pack-by-pack for the rest.
> > Of course I didn't introduce this idea as SIMD my main concern, I just
> > saw a potential useful application there.
> > Now, I'm not saying we should embrace push instead of pull; I think both
> > approaches should be allowed to co-exist, and that we should probably
> > try to standardize concepts and allow interoperability with other range
> > and iterator algorithms and adapters.
> > But this raises several questions: How do we choose between the two? How
> > do we integrate the approaches?
> Although what you're describing is easier to make efficient for many
> (perhaps even the majority of cases), it doesn't sound like it
> actually has the same level of generality as segmented iterators do.
> Dave Abrahams
> BoostPro Computing
-- Dave Abrahams BoostPro Computing http://www.boostpro.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk