Re: [boost] Summer of Code 2008 [Graph version 2]

From: Michael Fawcett (michael.fawcett_at_[hidden])
Date: 2008-03-05 13:15:47

On Wed, Mar 5, 2008 at 11:52 AM, Jonathan Franklin
<franklin.jonathan_at_[hidden]> wrote:
> On Wed, Mar 5, 2008 at 7:49 AM, Douglas Gregor <doug.gregor_at_[hidden]>
>  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