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