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

From: Joel de Guzman (joel_at_[hidden])
Date: 2006-09-25 11:15:17

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.

Regards,
-- 
Joel de Guzman
http://www.boost-consulting.com
http://spirit.sf.net