[fusion] segmented fusion 2.0
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. 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. Thoughts? Objections? -- Eric Niebler BoostPro Computing http://www.boostpro.com
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. Robert Ramey ?
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
On 8/11/2011 4:36 PM, Eric Niebler wrote:
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.
I'm sure you are planning to have some examples that illustrate the need for segmented structures and algorithms. It would be good to have real world examples to spark interest. Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
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. Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
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
Partially off-topic: Has there been any work done in boost on segmented iterators for regular algorithms (i.e. STL, not Fusion)?
On 8/11/2011 3:40 PM, Nathan Ridge wrote:
Partially off-topic: Has there been any work done in boost on segmented iterators for regular algorithms (i.e. STL, not Fusion)?
It wouldn't work without segmented flavors of the std algorithms. Have a look at Matt Austern's paper. The algorithms and iterators work together. -- Eric Niebler BoostPro Computing http://www.boostpro.com
Partially off-topic: Has there been any work done in boost on segmented iterators for regular algorithms (i.e. STL, not Fusion)?
It wouldn't work without segmented flavors of the std algorithms. Have a look at Matt Austern's paper. The algorithms and iterators work together.
Right, that's what I meant - a collection of segmented iterators and corresponding algorithms. A "segmented STL", if you will :) Nate
On 8/11/2011 4:38 PM, Nathan Ridge wrote:
Partially off-topic: Has there been any work done in boost on segmented iterators for regular algorithms (i.e. STL, not Fusion)?
It wouldn't work without segmented flavors of the std algorithms. Have a look at Matt Austern's paper. The algorithms and iterators work together.
Right, that's what I meant - a collection of segmented iterators and corresponding algorithms. A "segmented STL", if you will :)
You'd also need to reimplement the containers, since they would have to return segmented iterators. I don't think anybody has proposed to implement such a thing. It's a huge amount of work, and it wouldn't be as big a win. The runtime perf gains would be modest, and it doesn't eliminate complexity because there would be no equivalent universal "segmented iterator" in the runtime world. (It would need to store the path-to-the-current-position dynamically, which is a cost nobody would be willing to pay.) So std::map would still need to implement its own iterators, and at that point you have to ask yourself why you're doing all that extra work. I suppose this is why we don't see an STL implementation that uses segmented algorithms. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On 08/12/2011 02:22 AM, Eric Niebler wrote:
I don't think anybody has proposed to implement such a thing. It's a huge amount of work, and it wouldn't be as big a win.
It would definitely be a big win for numerical applications that need to tile loops etc. But then, ranges of ranges work just as well, and are a simpler concept. The runtime perf
gains would be modest, and it doesn't eliminate complexity because there would be no equivalent universal "segmented iterator" in the runtime world. (It would need to store the path-to-the-current-position dynamically, which is a cost nobody would be willing to pay.)
It can be reasonably well implemented using coroutines.
So std::map would still need to implement its own iterators, and at that point you have to ask yourself why you're doing all that extra work.
The segmented iterator of std::map would require using O(log n) memory (for the stack), while the flat one uses a constant amount of memory. O(log n) is still quite reasonable though.
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
On 8/11/2011 5:19 PM, Joel de Guzman wrote:
And, looking at the code, the implementation looks very sumptuous. I get indigestion with the old code :P
No kidding! That code was horrible. This code is still complex, but at least this time around I documented everything with pseudocode. It has helped immensely.
(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).
That's what I referred to by "baking it in". I imagine that all the ext_ directories go away, and segmentation support just becomes a native part of Fusion. These things would need to change: - We find a new home for segmented_iterator.hpp et. al. - Sequence intrinsics (begin, end, size, empty) have meaningful default implementations for segmented data structures. - As many algorithms as possible should dispatch to segmented flavors when appropriate. E.g., ext_/fold_s.hpp just gets merged into fold.hpp. - Fusion containers and views that are segmented (joint_view) advertize themselves as such, and the rest of their implementation goes away. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On 8/12/2011 8:37 AM, Eric Niebler wrote:
On 8/11/2011 5:19 PM, Joel de Guzman wrote:
And, looking at the code, the implementation looks very sumptuous. I get indigestion with the old code :P
No kidding! That code was horrible. This code is still complex, but at least this time around I documented everything with pseudocode. It has helped immensely.
(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).
That's what I referred to by "baking it in". I imagine that all the ext_ directories go away, and segmentation support just becomes a native part of Fusion. These things would need to change:
- We find a new home for segmented_iterator.hpp et. al. - Sequence intrinsics (begin, end, size, empty) have meaningful default implementations for segmented data structures. - As many algorithms as possible should dispatch to segmented flavors when appropriate. E.g., ext_/fold_s.hpp just gets merged into fold.hpp. - Fusion containers and views that are segmented (joint_view) advertize themselves as such, and the rest of their implementation goes away.
Sounds like a plan. If you have some initial sketch/notes that you can share, I'd love to get in the same page with you and share some effort to get this going asap. Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
On 8/11/2011 5:58 PM, Joel de Guzman wrote:
On 8/12/2011 8:37 AM, Eric Niebler wrote:
That's what I referred to by "baking it in". I imagine that all the ext_ directories go away, and segmentation support just becomes a native part of Fusion. These things would need to change:
- We find a new home for segmented_iterator.hpp et. al. - Sequence intrinsics (begin, end, size, empty) have meaningful default implementations for segmented data structures. - As many algorithms as possible should dispatch to segmented flavors when appropriate. E.g., ext_/fold_s.hpp just gets merged into fold.hpp. - Fusion containers and views that are segmented (joint_view) advertize themselves as such, and the rest of their implementation goes away.
Sounds like a plan. If you have some initial sketch/notes that you can share, I'd love to get in the same page with you and share some effort to get this going asap.
Here's my thinking: 1) support/ext_/is_segmented.hpp => support/ sequence/intrinsic/ext_/segments.hpp => sequence/intrinsic/ sequence/intrinsic/ext_/size_s.hpp => sequence/intrinsic/detail/ view/ext_/segmented_iterator.hpp => iterator/ view/ext_/segmented_iterator_range.hpp => view/iterator_range/detail/ view/ext_/segmented_begin.hpp => sequence/intrinsic/detail/ view/ext_/segmented_end.hpp => sequence/intrinsic/detail/ view/ext_/segmented_fold_until.hpp => support/ Various supporting implementation details make corresponding moves. container/ext_/tree.hpp becomes part of the test suite. It is poorly designed and doesn't deserve to be part of Fusion proper. 2) begin, end, size and empty dispatch to their segmented implementations by default. 3) The existing segmented algorithms (find_s, find_if_s, fold_s, for_each_s) just get merged with their non-segmented equivalents. 4) Wait for the dust to settle. Assuming all is looking good, try making joint_view segmented. 5) Use segmented_fold_until to write segmented flavors of as many algorithms as possible. I can do 1-3. 5 can be a team effort and can begin as soon as everything has found its rightful place. A word about segmented_fold_until. You call it with a hierarchical data structure, an initial state and a function. It walks the hierarchical structure and calls a function with each non-segmented range, the current state, and the "context". The context is actually the path through the tree to reach the current leaf range. You can pass it to make_segmented_iterator to (duh!) create a segmented iterator. The function that you pass to segmented_fold_until must wrap its returned object in a fusion::result, which contains a compile-time boolean: continue the fold or break. The returned object is the new state. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On 8/12/2011 9:46 AM, Eric Niebler wrote:
Sounds like a plan. If you have some initial sketch/notes that you can share, I'd love to get in the same page with you and share some effort to get this going asap.
Here's my thinking:
1) support/ext_/is_segmented.hpp => support/ sequence/intrinsic/ext_/segments.hpp => sequence/intrinsic/ sequence/intrinsic/ext_/size_s.hpp => sequence/intrinsic/detail/ view/ext_/segmented_iterator.hpp => iterator/ view/ext_/segmented_iterator_range.hpp => view/iterator_range/detail/ view/ext_/segmented_begin.hpp => sequence/intrinsic/detail/ view/ext_/segmented_end.hpp => sequence/intrinsic/detail/ view/ext_/segmented_fold_until.hpp => support/
Various supporting implementation details make corresponding moves.
container/ext_/tree.hpp becomes part of the test suite. It is poorly designed and doesn't deserve to be part of Fusion proper.
2) begin, end, size and empty dispatch to their segmented implementations by default.
3) The existing segmented algorithms (find_s, find_if_s, fold_s, for_each_s) just get merged with their non-segmented equivalents.
4) Wait for the dust to settle. Assuming all is looking good, try making joint_view segmented.
5) Use segmented_fold_until to write segmented flavors of as many algorithms as possible.
I can do 1-3. 5 can be a team effort and can begin as soon as everything has found its rightful place.
A word about segmented_fold_until. You call it with a hierarchical data structure, an initial state and a function. It walks the hierarchical structure and calls a function with each non-segmented range, the current state, and the "context". The context is actually the path through the tree to reach the current leaf range. You can pass it to make_segmented_iterator to (duh!) create a segmented iterator. The function that you pass to segmented_fold_until must wrap its returned object in a fusion::result, which contains a compile-time boolean: continue the fold or break. The returned object is the new state.
Thanks, Eric. If I haven't said so already, I think this is a very nice plan. I can definitely help out with 4 & 5. One thing to note though is that the fusion-0x code will fall out of sync once we go through this. I'm CC'ing Christopher. It would be foolish to merge fusion-0x now, in the middle of development, but I think that the 0x code should finally be merged to main as soon as the dust settles (after 3). Then, we can move to 4 and 5 with fusion-0x code in place. Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
On 8/15/2011 7:38 PM, Joel de Guzman wrote:
Thanks, Eric. If I haven't said so already, I think this is a very nice plan. I can definitely help out with 4 & 5.
One thing to note though is that the fusion-0x code will fall out of sync once we go through this. I'm CC'ing Christopher.
It would be foolish to merge fusion-0x now, in the middle of development, but I think that the 0x code should finally be merged to main as soon as the dust settles (after 3). Then, we can move to 4 and 5 with fusion-0x code in place.
OK, thanks for the heads up. I'm working on 1-3 now and will let you know when I'm done. It shouldn't cause you guys much grief since I make minimal changes to existing Fusion files. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On 8/15/2011 7:38 PM, Joel de Guzman wrote:
On 8/12/2011 9:46 AM, Eric Niebler wrote:
Here's my thinking:
1) support/ext_/is_segmented.hpp => support/ sequence/intrinsic/ext_/segments.hpp => sequence/intrinsic/ sequence/intrinsic/ext_/size_s.hpp => sequence/intrinsic/detail/ view/ext_/segmented_iterator.hpp => iterator/ view/ext_/segmented_iterator_range.hpp => view/iterator_range/detail/ view/ext_/segmented_begin.hpp => sequence/intrinsic/detail/ view/ext_/segmented_end.hpp => sequence/intrinsic/detail/ view/ext_/segmented_fold_until.hpp => support/
Various supporting implementation details make corresponding moves.
container/ext_/tree.hpp becomes part of the test suite. It is poorly designed and doesn't deserve to be part of Fusion proper.
2) begin, end, size and empty dispatch to their segmented implementations by default.
3) The existing segmented algorithms (find_s, find_if_s, fold_s, for_each_s) just get merged with their non-segmented equivalents.
These are now done. Sorry for the lag. It was harder than I thought.
4) Wait for the dust to settle. Assuming all is looking good, try making joint_view segmented.
5) Use segmented_fold_until to write segmented flavors of as many algorithms as possible.
I can do 1-3. 5 can be a team effort and can begin as soon as everything has found its rightful place.
A word about segmented_fold_until. <snip>
I've changed the interface to segmented_fold_until to make it more straightforward to customize its behavior. See algorithm/query/detail/segmented_find_if.hpp for an example.
Thanks, Eric. If I haven't said so already, I think this is a very nice plan. I can definitely help out with 4 & 5.
One thing to note though is that the fusion-0x code will fall out of sync once we go through this. I'm CC'ing Christopher.
It would be foolish to merge fusion-0x now, in the middle of development, but I think that the 0x code should finally be merged to main as soon as the dust settles (after 3). Then, we can move to 4 and 5 with fusion-0x code in place.
OK, everything is ready. I'll wait until fusion-0x is in place before spending any more time on this. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On 8/19/2011 7:19 AM, Eric Niebler wrote:
On 8/15/2011 7:38 PM, Joel de Guzman wrote:
On 8/12/2011 9:46 AM, Eric Niebler wrote:
Here's my thinking:
1) support/ext_/is_segmented.hpp => support/ sequence/intrinsic/ext_/segments.hpp => sequence/intrinsic/ sequence/intrinsic/ext_/size_s.hpp => sequence/intrinsic/detail/ view/ext_/segmented_iterator.hpp => iterator/ view/ext_/segmented_iterator_range.hpp => view/iterator_range/detail/ view/ext_/segmented_begin.hpp => sequence/intrinsic/detail/ view/ext_/segmented_end.hpp => sequence/intrinsic/detail/ view/ext_/segmented_fold_until.hpp => support/
Various supporting implementation details make corresponding moves.
container/ext_/tree.hpp becomes part of the test suite. It is poorly designed and doesn't deserve to be part of Fusion proper.
2) begin, end, size and empty dispatch to their segmented implementations by default.
3) The existing segmented algorithms (find_s, find_if_s, fold_s, for_each_s) just get merged with their non-segmented equivalents.
These are now done. Sorry for the lag. It was harder than I thought.
Wow, that was actually quicker than I thought! Awesome! All tests pass here.
4) Wait for the dust to settle. Assuming all is looking good, try making joint_view segmented.
5) Use segmented_fold_until to write segmented flavors of as many algorithms as possible.
I can do 1-3. 5 can be a team effort and can begin as soon as everything has found its rightful place.
A word about segmented_fold_until. <snip>
I've changed the interface to segmented_fold_until to make it more straightforward to customize its behavior. See algorithm/query/detail/segmented_find_if.hpp for an example.
Thanks, Eric. If I haven't said so already, I think this is a very nice plan. I can definitely help out with 4 & 5.
One thing to note though is that the fusion-0x code will fall out of sync once we go through this. I'm CC'ing Christopher.
It would be foolish to merge fusion-0x now, in the middle of development, but I think that the 0x code should finally be merged to main as soon as the dust settles (after 3). Then, we can move to 4 and 5 with fusion-0x code in place.
OK, everything is ready. I'll wait until fusion-0x is in place before spending any more time on this.
I haven't heard from Christopher, yet. Christopher, thoughts? We can probably proceed with the 0x merge later, Christopher is not yet ready. Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
On 8/12/2011 9:46 AM, Eric Niebler wrote:
4) Wait for the dust to settle. Assuming all is looking good, try making joint_view segmented.
I tried this today. It flushed out a couple of bugs in my segmented fusion code, but other than that, it Just Worked. That is, if joint_view merely exposes its internal segments (no need for joint_view_iterator), then all tests pass. This is a significant accomplishment. It meas that certain kinds of fusion data structures can be implemented very easily with no loss of functionality. I won't be committing that change, though. Compile-time performance for iterating through a joint_view is terrible. It seems single-stepping and comparing generic segmented_iterators is *much* more expensive than the same operations with the more specialized joint_view_iterators. For instance, the functional/invoke.cpp test takes 4-5x longer to compile (gcc 4.3, msvc 10) with generic segmented iterators! This is disappointing. I'll need to use the template profiler to see what's going on. Maybe I've just overlooked something obvious. Of course, single-stepping through a joint_view isn't necessarily the most common use scenario. These things will also be passed to fusion algorithms, which (if they are segment-aware) may in fact compile /faster/ if joint_view is segmented (unconfirmed). :-/ Regardless, it seems I need to improve the compile time of incrementing and comparing generic segmented iterators. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On 8/20/2011 5:41 AM, Eric Niebler wrote:
On 8/12/2011 9:46 AM, Eric Niebler wrote:
4) Wait for the dust to settle. Assuming all is looking good, try making joint_view segmented.
I tried this today. It flushed out a couple of bugs in my segmented fusion code, but other than that, it Just Worked. That is, if joint_view merely exposes its internal segments (no need for joint_view_iterator), then all tests pass. This is a significant accomplishment. It meas that certain kinds of fusion data structures can be implemented very easily with no loss of functionality.
I won't be committing that change, though. Compile-time performance for iterating through a joint_view is terrible. It seems single-stepping and comparing generic segmented_iterators is *much* more expensive than the same operations with the more specialized joint_view_iterators. For instance, the functional/invoke.cpp test takes 4-5x longer to compile (gcc 4.3, msvc 10) with generic segmented iterators! This is disappointing. I'll need to use the template profiler to see what's going on. Maybe I've just overlooked something obvious.
Of course, single-stepping through a joint_view isn't necessarily the most common use scenario. These things will also be passed to fusion algorithms, which (if they are segment-aware) may in fact compile /faster/ if joint_view is segmented (unconfirmed). :-/
Regardless, it seems I need to improve the compile time of incrementing and comparing generic segmented iterators.
That is interesting. If single-stepping through a joint_view isn't necessarily the most common use scenario, do you think invoke can be implemented another way? AFAICT, invoke is a real world use-case. Perhaps we should be thinking more in terms of algorithm composition from primitives such as fold, but the very notion of 'iterators' suggest (and we c++ folks take it as norm), that we iterate through the elements in a step-wise manner (unless I misunderstood what you mean by "single-stepping"). (BTW, Christopher sent me an email and says he won't be available in the next few months.) Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
On 8/20/2011 7:36 PM, Joel de Guzman wrote:
On 8/20/2011 5:41 AM, Eric Niebler wrote: <snip>
Of course, single-stepping through a joint_view isn't necessarily the most common use scenario. These things will also be passed to fusion algorithms, which (if they are segment-aware) may in fact compile /faster/ if joint_view is segmented (unconfirmed). :-/
Regardless, it seems I need to improve the compile time of incrementing and comparing generic segmented iterators.
That is interesting. If single-stepping through a joint_view isn't necessarily the most common use scenario, do you think invoke can be implemented another way?
I think it could be done with variadic templates, but I'm not saying invoke's implementation needs to change.
AFAICT, invoke is a real world use-case.
No doubt!
Perhaps we should be thinking more in terms of algorithm composition from primitives such as fold, but the very notion of 'iterators' suggest (and we c++ folks take it as norm), that we iterate through the elements in a step-wise manner (unless I misunderstood what you mean by "single-stepping").
Single-stepping though a joint_view is an important use case, and it needs to be well-supported. No argument. Which is why I'd like to find and fix the perf problem in segmented_iterator, or else leave joint_view_iterator alone. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On Thu, Aug 11, 2011 at 5:37 PM, Eric Niebler <eric@boostpro.com> wrote: [...]
- Fusion containers and views that are segmented (joint_view) advertize themselves as such, and the rest of their implementation goes away.
Does this imply that these segmented containers and views lose their fully linear iterators? Or would this linearization now just be encapsulated generically in, e.g., fusion::segmented_iterator? In other words, I would hope that old code that just trounced linearly through a joint_view via its iterator would still work. - Jeff
On 8/11/2011 6:03 PM, Jeffrey Lee Hellrung, Jr. wrote:
On Thu, Aug 11, 2011 at 5:37 PM, Eric Niebler <eric@boostpro.com> wrote: [...]
- Fusion containers and views that are segmented (joint_view) advertize themselves as such, and the rest of their implementation goes away.
Does this imply that these segmented containers and views lose their fully linear iterators? Or would this linearization now just be encapsulated generically in, e.g., fusion::segmented_iterator?
In other words, I would hope that old code that just trounced linearly through a joint_view via its iterator would still work.
See my reply to Mathias in this thread. In short: don't worry. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On 08/11/2011 06:28 AM, Eric Niebler wrote:
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.
Thoughts? Objections?
I don't think the flat iterator of joint_view should disappear. A segmented fusion sequence should also be iterable like a flat fusion sequence if I'm willing to pay the price.
On 8/11/2011 2:18 AM, Mathias Gaunard wrote:
On 08/11/2011 06:28 AM, Eric Niebler wrote:
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.
Thoughts? Objections?
I don't think the flat iterator of joint_view should disappear. A segmented fusion sequence should also be iterable like a flat fusion sequence if I'm willing to pay the price.
And it won't! That's the great thing ... one segmented_iterator class template is sufficient to present a flat view of *any* hierarchical data structure. It knows how to walk the tree of internal segments. Internally, it remembers the path it took through the tree to reach the current position. (I'm using "tree" generally here. A joint_view is just a very simple tree.) And, when you make a range out of two of these segmented iterators, you are essentially defining another hierarchical data structure -- a constrained view of the original container, delimited by the two paths that each iterator represents. You can pass this range to a segmented algorithm, and it does the segmented thing instead of the iterative thing. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On Aug 11, 2011, at 12:28 AM, Eric Niebler wrote:
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.
Thoughts? Objections?
Good work! Could this also be a starting point for compile-time/run-time segmented iterators, e.g. a fusion container of stl containers where each stl container contains a different type? Cheers, Gordon
participants (7)
-
Eric Niebler -
Gordon Woodhull -
Jeffrey Lee Hellrung, Jr. -
Joel de Guzman -
Mathias Gaunard -
Nathan Ridge -
Robert Ramey