Re: [boost] [fusion] segmented fusion 2.0

Subject: Re: [boost] [fusion] segmented fusion 2.0
From: Eric Niebler (eric_at_[hidden])
Date: 2011-08-11 13:18:16

On 8/11/2011 1:58 AM, Joel de Guzman wrote:
> On 8/11/2011 12:28 PM, Eric Niebler wrote:
>> I took the liberty of rewriting all my old broken segmented fusion code
>> and checked in something (hopefully) a bit more maintainable and
>> friendly. Along with the changes, I added an algorithm called
>> segmented_fold_until. Many of the existing algorithms have segmented
>> versions that can be implemented trivially in terms of this one. (Recall
>> that the biggest problem with the old implementation was the need to
>> write a separate implementation of every algorithm for segmented data
>> structures, which was very complicated. Now that's almost trivial.)
>>
>> I hope in the coming weeks and months to produce segmented versions of
>> most of the existing fusion algorithms. Once that's done, I hope to
>> "bake it in" by making the existing algorithms select the segmented
>> flavors automatically.
> 
> I've been wanting to ask you what's cookin' :), now I know.
> This is awesome, Eric. Simply awesome!
> 
>> Also, some containers and views are naturally segmented, like
>> joint_view. Practically all of joint_view's implementation, including
>> its iterator, would vanish if it just advertised itself as segmented.
> 
> Cool! It would be interesting to see the compile time comparisons
> though.

I'm attaching a little test program that creates a big heterogeneous
tree and then does a fold. If you compile with USE_SEGMENTED it does a
segmented fold. Otherwise, it does an iterative fold.

The runtime results are the same, but it makes a big difference at
compile time. On my machine, I get:

segmented fold:  4.38s
iterative fold: 10.16s

Making a hierarchical data structure look flat is a lot of needless work
for the compiler.

Now take a look at fusion/algorithm/iteration/ext_/fold_s.hpp and see
how simple the implementation of the fold_s algorithm it.

-- 
Eric Niebler
BoostPro Computing
http://www.boostpro.com