At Thu, 14 Oct 2010 08:07:47 -0700, Jeffrey Lee Hellrung, Jr. wrote:
On 10/14/2010 1:23 AM, David Abrahams wrote:
At Wed, 13 Oct 2010 12:08:43 -0700, Jeffrey Lee Hellrung, Jr. wrote: [...]
Yes. But I'm not convinced yet that iterators exposing the segmentation of the data structure are the right solution to presenting a flattened view of that data structure.
Good; that's not what they're for ;-)
I think I missed something, then.
Sorry, no, I was the one who missed something. Please allow me to correct what I said. Presenting a flattened view of a hierarchical data structure kills performance. Segmented iterators expose an additional non-flattened view so that appropriately constructed algorithms can avoid that performance loss...
Are we not applying sequential algorithms (e.g., fill, for_each, ...) to hierarchical data structures?
...where by "appropriately constructed," I mean algorithms that have been re-cast hierarchically. "Sequentialness" is not necessarily implied.
1) It doesn't play nice with standard C++ looping constructs, specifically for loops.
The whole point of hierarchical algorithms is to avoid flat loops for segmented data structures.
It certainly avoids flat loops, to the point of outright precluding their use. I can add here a 1a) How would you go about iterating through segmented data structures in parallel?
You mean two at once? I think you have to produce a new segmentation structure that bounds segments at the union of all segment boundaries in the two sequences. I would probably do that with a segmented zip view.
2) I have yet to see a benchmark comparison between segmented iterators and alternatives (other than a side-note claim in the paper). I'm open to looking at some specific comparisons if one has already done this, and this is something I'm interested enough in that I might try to do myself. Seems to me a more general solution is a "flat_multirange_iterator" templated on the outer range and the "segmentation depth". I.e., a flat_multirange_iterator< vector< vector<T> >, 2> would iterate over the T's.
That's gonna be slow. Lots of testing and branching.
"Note that the joined range incurs a performance cost due to the need to check if the end of a range has been reached internally during traversal."
First, that quote applies directly to a join_iterator, though I'll give you that it *may* apply to my hypothetical a flat_multirange_iterator.
It's exactly the same problem that the iterators of std::deque has.
What I'm having trouble with is it *looks* to me like you have the same tests and branches with a segmented iterator as with a flat_multirange_iterator.
I acknowledge that you retracted that analysis in a later post.
To address your claim that "that's the same problem ... that segmented iterators are solving", what I meant by a join_range or joint_range is, essentially, a flattened out Boost.Fusion sequence of ranges of *differing* types (but with compatible value_type's and references). E.g., the thing that boost::join [1] returns. Segmented iterators can't deal with such ranges (at least with a strict reading of Austern's paper),
I don't see why you say that.
Show me what the equivalent nested for-loop looks like if a join_range can be "segmentedly" iterated over.
Well, things get complicated when the element types or structure of a single sequence are heterogeneous.
If I tried, I'd be inclined to write a for-loop over a Boost.Fusion sequence.
Yeah, you need to do something like that.
If you want to include a join_iterator within the family of segmented iterators, you'd have to enrich the interface of segmented iterators to include Boost.Fusion sequences. Is that desirable?
IIUC, there already is support for segmented Boost.Fusion iterators somewhere. -- Dave Abrahams BoostPro Computing http://www.boostpro.com