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 04:36:48

On 8/11/2011 12:30 AM, Robert Ramey wrote:
> Eric Niebler wrote:
> 
>> 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.
> 
> what does "segmented" mean here.  How would "segmented" fusion
> be different from plain old fusion.

For a full explanation, see Matt Austern's "Segmented Algorithms and
Hierarchical Data Structures":

http://lafstern.org/matt/segmented.pdf

Many data structures are hierarchical like trees and deques. Iterators
for these must present a "flat" view, and that can be expensive. In the
runtime world, you pay for that at runtime. In Fusion, you pay for it at
compile time -- and at library design time because the metaprogramming
gets hairy. Notice that there is no Fusion tree data structure.

So, to answer your question, segmented fusion is different because, when
dealing with naturally hierarchical data, compile times will be better.
And Fusion-ifying such hierarchical data structures goes from being a
guru-level job (present a flat view) to a trivial one (expose the
internal segments, Fusion does the rest).

My interest in this comes from Proto. Proto trees are hierarchical
Fusion data structures. If I have to solve this problem once for myself,
I may as well do it in a way that nobody ever needs to solve it again.

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