[boost] Metaprogrammers, all of you!

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
> http://github.com/boost-lib/parameter/blob/master/test/efficiency.cpp
> 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
> iterators.
> 
> > 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
> http://www.boostpro.com
> 

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