On Mar 2, 2008, at 6:31 PM, Andrew Sutton wrote:

...

If folks have ideas for potential projects then now would be a good time to start thinking about them - that way we can apply to Google to be a mentoring organisation with a good selection of ideas already up and running.

I've been thinking about Boost.Graph v2. I was hoping to finish the work that I started in the fall. Of course, I was hoping for a little more free reign with the interfaces for this work - source compatibility won't be high on my list of priorities in my proposal.

So long as Visual C++ 6/7 compatibility isn't also high on your list of priorities, go for it :) Half of the ugliness of the BGL implementation is in the workarounds needed to deal with compilers that can't handle class template partial specialization. - Doug

On Mar 5, 2008, at 7:32 AM, Andrew Sutton wrote:

...

Half of the ugliness of the BGL implementation is in the workarounds needed to deal with compilers that can't handle class template partial specialization.

Since I'm thinking about being experimental, and SoC is a sandbox within a sandbox, maybe it wouldn't hurt to build the next version using newer C++ features (esp. variadic templates).

I don't imagine that variadic templates would help all that much, but who knows?

I also have a couple of other goals that don't align very well the current implementation either. 1. Making the interface a little less generic without sacrificing flexibility. For example, I don't know that the vertex/edge storage stuff actually sees much use, and it can cause terrible inefficiency if you're not extremely careful with it (e.g., num_vertices()/ num_edges() using listS storage).

These are pretty important operations... I don't think they can go away, even though they do require linear time for some data structures.

Also, I never did understand why certain functions weren't just member functions (like add_vertex()).

It's so that people can use their own graph types with BGL algorithms. I guess one could have a member "add_vertex" in adjacency_list and also have the free function "add_vertex" that just forwards to the member, which might be easier for users... but I'm not convinced that the redundancy would help.

2. Revisit the interface and implementation for BFS/DFS, and get rid of the parameter passing.

... or use the Boost.Parameter library, which simplifies passing optional parameters. [*]

It's ugly and causes a lot of problems for people learning how to write the code. My gut feeling on this is that if you're using optional parameters to have the same algorithm behave somewhat differently, then building a new function might not be a bad idea.

Interesting. There's a lot of internal reuse of BFS and DFS that would go away if they lost some of their flexibility, but perhaps there's a way to have both.

I also want to redesign the searches for "stoppability" - either for user-selected termination (as per Loïc's request), or in the case of disjoint subgraphs.

DFS supports a "TerminatorFunc" to stop early, but this might not be the right approach. Why does everyone dislike throwing an exception to terminate the search? I bet if someone went ahead and benchmarked the two options, the exception would be faster for graphs of non- trivial size. - Doug [*] Now *that* is a library that could benefit from variadic templates!

On Wed, Mar 5, 2008 at 11:52 AM, Jonathan Franklin <franklin.jonathan@gmail.com> wrote:

On Wed, Mar 5, 2008 at 7:49 AM, Douglas Gregor <doug.gregor@gmail.com> wrote:

...

Why does everyone dislike throwing an exception to terminate the search?

I imagine that most people view using exceptions for control flow as being akin to using "goto". ;-)

Under normal circumstances, they're probably right. However with deep nesting or recursion, I'm not so sure. Throwing certainly seems to offer an extremely simple way to do it.

I bet if someone went ahead and benchmarked

...

the two options, the exception would be faster for graphs of non- trivial size.

I would be extremely interested in seeing any benchmark results.

I have a Pathfinding library that currently uses visitors much like the BGL, except mine uses a visitor.at_goal() function to signal when to terminate the search, rather than an exception. I modified the code to no longer call that function, and instead loop infinitely (until the search space is exhausted), meaning the visitor now had to throw an exception to exit once it reached the goal. Here are my results in Release mode, full optimizations, averaged over 10 runs each. There were only about 15,000 nodes generated in the search, so it wasn't a very large graph. at_goal() called every iteration - 0.121104 seconds exception - 0.130855 seconds Not very scientific I know...also it uses my own library, not BGL, but someone would have to modify BGL's algorithms and visitor class to use a function that returns a bool (continue searching, or not) to do a meaningful benchmark. 0.01 seconds might be enough for some people in games to want an alternative. Exceptions are also supported much more primitively on most consoles (either not at all, or they are much slower). Both of these may be why some people don't want exceptions as the early termination method. --Michael Fawcett

On Wed, Mar 5, 2008 at 1:51 PM, Jonathan Franklin <franklin.jonathan@gmail.com> wrote:

On Wed, Mar 5, 2008 at 11:15 AM, Michael Fawcett <michael.fawcett@gmail.com> wrote:

...

<snip>

There were only about 15,000 nodes generated in the

...

search, so it wasn't a very large graph.

Any way to crank that up to 150,000, or 1.5 million?

Same test, but I resized the image to 1280 x 1280 (it was at 128 x 128). There were 1,016,906 nodes generated during the search. I only did each version 5 times instead of 10 this time, since it took quite a bit longer. at_goal() - 19.05272 seconds exception - 18.85408 seconds So, throwing an exception was faster in this case. Just to make sure I didn't screw things up the first time, I tried it again with the 128 x 128 bitmap, and at_goal() was indeed faster than the exception again over 5 runs (this time by 0.02 seconds, not 0.01 like before). I forgot to mention before that this is using VS 2005 as the compiler. I'm pretty sure results for compilers with different exception implementations would vary greatly. --Michael Fawcett

On Wed, Mar 5, 2008 at 3:22 PM, Sebastian Redl <sebastian.redl@getdesigned.at> wrote:

Michael Fawcett wrote:

...

I forgot to mention before that this is using VS 2005 as the compiler. I'm pretty sure results for compilers with different exception implementations would vary greatly.

I imagine that a Linux/GCC build would indeed show quite different results. Do you have the platform available, or a an easily compilable/runnable test case for someone else to run?

I have cygwin available. This might take some time to do though, I'll try to get around to it before the end of the week. The code is unfortunately company code, so I can't share it, but I'm hoping to convince them to let me release it soon. --Michael Fawcett

On Sun, Apr 27, 2008 at 9:39 PM, David Abrahams <dave@boost-consulting.com> wrote:

on Thu Mar 06 2008, "Michael Fawcett" <michael.fawcett-AT-gmail.com> wrote:

...

On Wed, Mar 5, 2008 at 3:22 PM, Sebastian Redl <sebastian.redl@getdesigned.at> wrote:

...

Michael Fawcett wrote:

...

I forgot to mention before that this is using VS 2005 as the compiler. I'm pretty sure results for compilers with different exception implementations would vary greatly.

I imagine that a Linux/GCC build would indeed show quite different results. Do you have the platform available, or a an easily compilable/runnable test case for someone else to run?

I have cygwin available. This might take some time to do though, I'll try to get around to it before the end of the week.

Cygwin won't tell us much; it uses essentially the same crappy SJLJ exception implementation that VS uses in 32-bit mode, IIRC.

I don't know much about Cygwin, but the results were very different from Cygwin/gcc vs Windows/VS 2005. Why this was, I have no clue and never investigated further. --Michael Fawcett

On Mar 12, 2008, at 6:38 PM, Michael Fawcett wrote:

On Wed, Mar 5, 2008 at 4:22 PM, Sebastian Redl <sebastian.redl@getdesigned.at> wrote:

...

Michael Fawcett wrote:

...

I forgot to mention before that this is using VS 2005 as the compiler. I'm pretty sure results for compilers with different exception implementations would vary greatly.

I imagine that a Linux/GCC build would indeed show quite different results. Do you have the platform available, or a an easily compilable/runnable test case for someone else to run?

So I finally got it compiling and running under Cygwin/gcc. Here are the results (averaged over 5 runs):

1280 x 1280

at_goal() - 23.45162 seconds exception - 23.39538 seconds

128 x 128

at_goal() - 0.20304038 seconds exception - 0.1919092 seconds

So exception beat at_goal() in both cases here, but the margins are much smaller. I suspect that I wasn't compiling to gcc's fullest optimization potential, but I did use -O3.

Very interesting. Thanks for running these experiments! - Doug

on Wed Mar 05 2008, Sebastian Redl <sebastian.redl-AT-getdesigned.at> wrote:

Michael Fawcett wrote:

...

I forgot to mention before that this is using VS 2005 as the compiler.

64- or 32- bit? It matters. -- Dave Abrahams Boost Consulting http://boost-consulting.com

on Sun Apr 27 2008, "Michael Fawcett" <michael.fawcett-AT-gmail.com> wrote:

On Sun, Apr 27, 2008 at 9:38 PM, David Abrahams <dave@boost-consulting.com> wrote:

...

on Wed Mar 05 2008, Sebastian Redl <sebastian.redl-AT-getdesigned.at> wrote:

...

Michael Fawcett wrote:

...

I forgot to mention before that this is using VS 2005 as the compiler.

64- or 32- bit? It matters.

32-bit.

That's a poor test of any other compiler, or of what's possible, then. MS used the setjmp/longjmp approach to EH with that compiler, for compatibility with "structured exceptions." The 64-bit compiler has a "real" EH implementation ;-) One more thing to note about the case of terminating graph algorithms with exceptions: these algorithms have *lots* of hooks for each iteration of the process, each of which might need to terminate the algorithm (e.g. http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/DFSVisitor.html), so that can add up to quite a few tests for each iteration of the inner loop, which can be avoided if EH is used. -- Dave Abrahams Boost Consulting http://boost-consulting.com

Right. However, what we would like to accomplish here is to move away from speculation over how poorly one method performs over the other, and gather some good empirical data that covers all (or at least the most prevalent) usage patterns.

Fortunately, my proposal sorta covers this type empirical investigation. Part of it is to look at other some other graph libraries and see how they provide various aspects of the interface. My guess is I'll end up producing a bunch of little generic kernels that can be composed to provide variations on searches (e.g., traversal, find first, find all, etc.). Andrew Sutton asutton@cs.kent.edu

On Wed, Mar 5, 2008 at 1:14 PM, Michael Fawcett <michael.fawcett@gmail.com> wrote:

Same test, but I resized the image to 1280 x 1280 (it was at 128 x 128). There were 1,016,906 nodes generated during the search.

<snip>

at_goal() - 19.05272 seconds exception - 18.85408 seconds

So on this platform/configuration, w/ ~15K nodes, at_goal() was ~7.5% faster, and w/ ~1M nodes, exception was a little over 1% faster. It would be interesting to plot some curves to see where the turning point for this platform lies. I still wonder if the exception method would *significantly* outperform at_goal() for larger graphs. For me, 1% isn't all that compelling, unless it offers something else, such as design simplicity (or decreasing the WTF?!? (astonishment) factor). Jon

Douglas Gregor a écrit :

...

I also want to redesign the searches for "stoppability" - either for user-selected termination (as per Loïc's request), or in the case of disjoint subgraphs.

DFS supports a "TerminatorFunc" to stop early, but this might not be the right approach. Why does everyone dislike throwing an exception to terminate the search? I bet if someone went ahead and benchmarked the two options, the exception would be faster for graphs of non- trivial size.

There are two kind of early-stop. One is : "Stop the search". The other one is : "Stop looking in this direction, but continue the search". Throwing an exception may be a solution for the first category, but I don't see how is could help for the second. Maybe another way to go for the second would be to manually modify some well chosen colors in the visitor functions, but this approach seemed to scary for me to try it. -- Loïc

I don't imagine that variadic templates would help all that much, but who knows?

I thought vertex/edge property specification was built using recursive templates. I was thinking of that as an application for variadic templates, but I could be way off base :)

...

IFor example, I don't know that the vertex/edge storage stuff actually sees much use, and it can cause terrible inefficiency if you're not extremely careful with it (e.g., num_vertices()/ num_edges() using listS storage).

These are pretty important operations... I don't think they can go away, even though they do require linear time for some data structures.

I wouldn't get rid of the operations - they're pretty fundamental. I was just thinking about the underlying storage mechanisms for edge lists and vertex lists. I can certainly see arguments for using non- vector storage, but I don't know how often its used in practice.

It's so that people can use their own graph types with BGL algorithms.

Why not just build a simple wrapper class? My concern here is that trying to provide a generic interface for a number of different implementations may actually inhibit the utility of the specific implementations of graph types and algorithms within the library.

...

... or use the Boost.Parameter library, which simplifies passing optional parameters. [*]

I played with this last summer - it doesn't actually seem to solve the problem. In fact, it actually makes it a little bit worse because it hides (the inevitable) compiler errors behind a thick wall of preprocessor code. The problem is not passing optional parameters, but the fact that doing so is often used to select different versions of the same algorithm. It becomes very difficult to document.

...

DFS supports a "TerminatorFunc" to stop early, but this might not be the right approach. Why does everyone dislike throwing an exception to terminate the search? I bet if someone went ahead and benchmarked the two options, the exception would be faster for graphs of non- trivial size.

That's a good idea. I've always felt a little queasy about throwing exceptions as a means of terminating a function when no error has occurred, but there may not be anything /too/ wrong with it in this case. It would avoid the requirement to check a terminate condition in every iteration of the algorithm. Hiding the throw behind a function might not hurt either. Something like finish() or stop(). I don't know... maybe I'm thinking too hard. Building a version of BGL2 based on the current code base (or whatever's in sandbox) is just as good a summer project. Andrew Sutton asutton@cs.kent.edu

...

I played with this last summer - it doesn't actually seem to solve the problem. In fact, it actually makes it a little bit worse because it hides (the inevitable) compiler errors behind a thick wall of preprocessor code. The problem is not passing optional parameters, but the fact that doing so is often used to select different versions of the same algorithm. It becomes very difficult to document.

Perhaps we need to draw a line between customizing an algorithm (which could/should(?) be done through optional parameters) and selecting different variants of an algorithm (which should not be done through optional parameters). Drawing that distinction might simplify the use of these algorithms.

I think that's definitely a good idea. While it's not really an implementation issue, documenting functions, they're types, and concept requirements becomes ridiculously complicated when there are lots of options - especially if those options actually control the behavior of the algorithm.

...

I don't know... maybe I'm thinking too hard. Building a version of BGL2 based on the current code base (or whatever's in sandbox) is just as good a summer project.

I think we're just envisioning different "final products" for BGLv2, because we use BGL for different things. Today, I happen to be working with VTK, which has a new vtkGraph data type. They provide the appropriate graph_traits specializations, free functions, etc. so that a pointer to a vtkGraph (vtkGraph*) works off-the-shelf in BGL algorithms: no wrappers required. That's exactly the kind of thing that I believe the BGL excels at, and I think it's important for future revisions of the BGL to support that use case. There's a lot of cruft I'd like to eliminate---non-partial-specialization hacks, the property<...> class, etc.---and bits that I'd like to clean up--- property map creation is too hard, adjacency_list has too many knobs only useful in rare circumstances, etc.---but I think, fundamentally, the Graph concepts are just about right.

I can see (from my previous comments) why you'd think we're talking about different final products, which probably means that I did a poor job communicating my ideas :) I'm starting to see the BGL as three distinct libraries: the generic interface (concepts), the algorithms (based on concepts) and some graph type implementations. The changes to the latter two (algorithms and types) that I'm kicking around don't (or shouldn't) necessitate changes to the generic interface. It actually sounds like your cruft isn't too different than what I'm actually envisioning. I just want to put a little more focus on designing the class interface as a refinement of the generic interface. After all, STL containers provide coherent, usable interfaces as refinements of the concepts that enable the STL algorithms. I definitely agree with your list of things that need to be worked on... I'm not entirely sure of the best way to solve some of them. Maybe this summer would be a good time to experiment with some alternative designs since removing much of the cruft could potentially obsolete legacy BGL code - at least the declarations of graph types; probably not generic code. Getting rid of the property<> class will break the classes I wrote last summer :) Besides, new designs might give the opportunity to start thinking formally about new concepts like subgraphs and hypergraphs. I'll try to start making a coherent (and hopefully realistic) list of possible goals for the summer and their rationale. I'll try to send it up sometime in the next week or so to see if it anybody would be interested in mentoring such a proposal. Andrew Sutton asutton@cs.kent.edu

On Mar 3, 2008, at 3:01 PM, Loïc Joly wrote:

Doug Gregor a écrit :

...

A project idea: "porting" Boost to C++0x, providing alternative (= better, simpler, faster, etc) implementations of core Boost libraries by making use of C++0x features like variadic templates, rvalue references, and decltype.

I think it would be a wonderful idea, but do you think that the language itself, and the available compilers, are stable enough to allow for such an operation now ?

GCC 4.3 should be released in a few weeks, with decent support for those features. So, I think we can get started exercising those features in Boost, both to help squish the bugs in GCC and to entice other compiler vendors to start supporting these features.

Is that why you omit concepts in your feature list ?

Yes. ConceptGCC is buggy enough to prevent serious implementations of Boost at this time, and I'm most interested in getting the best use out of the C++0x features we have in released (or soon-to-be-released) compilers. - Doug

Doug Gregor wrote:

John, was it you who sent in the actual organization application last year?

I believe Jeff Garland (or Beman?) handled all that, I've been a mentor but I haven't had any direct contact with the Google folks. John.