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