Re: [boost] [fusion] segmented fusion 2.0

Subject: Re: [boost] [fusion] segmented fusion 2.0
From: Joel de Guzman (joel_at_[hidden])
Date: 2011-08-11 20:19:01

On 8/12/2011 1:18 AM, Eric Niebler wrote:
> 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.

I get similar results:

MSVC==================
segmented fold:  3.03s
iterative fold:  6.91s

G++===================
segmented fold:  5.01s
iterative fold: 13.28s

That is awesome, Eric!

And, looking at the code, the implementation looks very sumptuous.
I get indigestion with the old code :P

Way to go, Eric. Hats off to you!

(Aside: we should talk about naming ext_ into something more obvious.
Before it was a hidden curiosity. Now it seems its ready to take
front stage).

Regards,
-- 
Joel de Guzman
http://www.boostpro.com
http://boost-spirit.com