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