Re: [boost] [fusion] segmented sequences [ was Re: [fusion] ftag ]

From: Eric Niebler (eric_at_[hidden])
Date: 2006-09-25 12:41:15

Joel de Guzman wrote:
> Andy Little wrote:
> 
>> There do seem to be limits to when the compiler will optimise a view though, It 
>> may have something to do with copying references(aka joint-view) as raw bytes, 
>> after which AFAICS the compiler will treat them as pointers. that said that is 
>> only an impression so far.
> 
> Ok, now I understand. You sent me an email about stacked fold of
> stacked joint_view created by push_back being difficult for the
> compiler to optimize. Here's why (and there's a solution):
> 
> joint_view is a prime example of a segmented sequence. The resulting
> iterators from it will have some overhead. That is inevitable.
> See joint_view_iterator so you'll know what I mean.
> 
> However, Eric Niebler did some work on segmented algorithms. His
> initial testing (for proto and early spirit-2 experiments) shows
> some exciting results. Basically, a segmented sequence is a sequence
> of sequences (for each segment). Instead of creating an iterator that
> "weaves" through each segment (like joint_view_iterator), segmented
> algorithms apply the algorithm recursively to each of the segments.
> For example, a fold of a joint_view will be 2 calls to fold, one
> for the left join and one for the right.
> 
> I know this is a bit hand-wavy, but once you see it in action, it
> really makes a lot of sense. I'm CCing Eric. I think now is the right
> time to incorporate his work into the fusion code base.

Thanks, Joel, I agree now would be a good time to integrate my work on 
segmented fusion. I haven't done any additional work on it since the 
"segmented fusion, a-ha!" days on spirit-devel. The latest version can 
be found in an attachment on the following message:
http://article.gmane.org/gmane.comp.parsers.spirit.devel/2781

The next step would be to port this code to the latest Fusion-2 and add 
some tests. Perhaps we could check this in on a branch, or in an 
"experimental" sub-directory. And we can't make joint_view a segmented 
sequence until we have segmented versions of all the Fusion algorithms.

Trouble is, I haven't had much time to work on this. :-(

-- 
Eric Niebler
Boost Consulting
www.boost-consulting.com