At Wed, 13 Oct 2010 10:52:36 +0100, Mathias Gaunard wrote:
On 12/10/10 09:06, David Abrahams wrote:
Nice for very linear things. Not so great for sort, binary_search, reverse, rotate, ...
Yes, since those require either bidirectional or random access iterators.
Actually, all of those can be done with bidirectional iterators (although the standard over-constrains sort). binary_search can be done with forward iterators.
Ability to stop the iteration could be a useful addition to make the concept have more applications. In functional languages, people seem happy to use exceptions for that; but I assume that certainly wouldn't be the case in C++.
Nooo. Waaay too far from the machine model. If we're talking about HPC, let's figure out how to generate optimal (or near-optimal) code.
In any case, linear operations or filters represent in my opinion a large enough spectrum of what people do with iterable ranges of data that it could be worthwhile to have concepts that allow them to be efficient, even if it cannot apply to other cases.
I believe that segmented iterators do allow them to be efficient.
It may not matter that it isn't easy, if you really want generic capability.
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.
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.
Do you have some examples?
binary_search (equal_range, lower_bound, upper_bound), rotate, equal, transform (2-input version), includes, merge... These were just the first ones I encountered in the algorithms section of http://www.sgi.com/tech/stl/stl_index_cat.html
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.
struct my_iteration { void operator()(float f) { do_something_with_scalar(f); }
void operator()(packed_view<float, 4> v) { do_something_with_vector(v); } };
for_each(simd::packed_range(mystuff), my_iteration());
vs
for(packed_view<float, 4> v : simd::packed_range(mystuff)) do_something_with_vector(v);
Using a pull solution for iteration, the former /could/ take care of the non-aligned cases at the beginning and at the end of the mystuff range through overloading.
Oh, I think I see what you're getting at. Solving that problem for segmented iterators would be interesting.
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.
Segmented iterators still allow bidirectional support, indeed (I think?). But I'm note sure it can do random access as well, if you consider recursively segmented local iterators.
Just as with flat containers, some segmented iterators for hierarchical containers can do random-access and some can't. std::deque is an example that can. I don't think recursive segmentation is an obstacle as long as all the sizes are constant at the leaves.
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? -- Dave Abrahams BoostPro Computing http://www.boostpro.com