On 10/14/2010 8:41 PM, David Abrahams wrote:
At Thu, 14 Oct 2010 08:07:47 -0700, Jeffrey Lee Hellrung, Jr. wrote: [...] 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. [...]
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. [...]
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.
If you can provide more direction here, I would appreciate it. There is boost::fusion::joint_view, but that only concatenates 2 Boost.Fusion sequences, not 2 ranges... By the way, I did run a comparison between a segmented iteration, with nested for-loops, and a flattened iteration. I was very much surprised in the runtime difference. It obviously depends on the operation you do per iteration, but for just incrementing a counter, the difference was 2 or 3 orders of magnitude. Needless to say, I'm more convinced of the value of exposing the segmentation of data structures now. Here's what I'm getting from this discussion: I see 2 viable approaches to address iteration over non-linear data structures, where efficiency is a major concern. One is an external, segmented iterator interface, possibly enriched to enable iteration over Boost.Fusion sequences at any depth. The other is an internal "push" or visitation iteration suggested originally by Mathias. Neither models seem to yield *convenient* implementations of *all* iteration algorithms in <algorithm>, but I can see enough utility that one model and/or the other would be worth investigating. I'm not sure yet if either iteration model is more powerful than the other, though it seems there are some algorithms expressable via segmented iteration that would be challenging to express via push iteration. In any case, David, I appreciate your patience and participation. - Jeff