| Topic: |
DEVELOP > c-Plus-Plus |
| User: |
"Mark P" |
| Date: |
29 Mar 2006 09:43:04 PM |
| Object: |
using exceptions as a "deep" return |
I'm implementing an algorithm and the computational flow is a somewhat
deep. That is, fcn A makes many calls to fcn B which makes many calls
to fcn C, and so on. The return value of the outermost fcn is a boolean
and there are certain places within the inner functions where it may
become apparent that the return value is false. In this case I'd like
to halt the computation immediately and return false.
My current approach is to have any of the inner functions throw an
exception if the return value is ever determined early like this. Then
within fcn A I'll catch the exception and return false. Is this a good
approach or is there a more C++ way to handle this? It's sort of a
glorified goto, but it does get the job done.
On a related note, if an exception is never thrown, is there any
performance penalty to enclosing a block of code within a try-catch
block. The exceptional case above should be rare and I don't want to
hurt the common case by doing this.
Thanks,
Mark
.
|
|
| User: "Kaz Kylheku" |
|
| Title: Re: using exceptions as a "deep" return |
31 Mar 2006 04:29:13 PM |
|
|
Ian Collins wrote:
OK, I'll bite:
Pentium M 2GHz, Solaris snv_b33, Sun Studio 11.
Built with -O2.
chrono_bias = 0.000000540s
Wouldn't you know it, that awful clock() function that may return "just
about anything, useful or otherwise" is actually working on a
different OS and development platform.
max_depth = 400
return_time = 0.000003960s
exception_time = 0.000022360s
Wow, that is quite interesting. Thanks for the data points.
GNU C++ works more according to my intuition about exceptions. I
suspected that just mashing through the stack would be faster than
actually taking the branches through the return points, regardless of
whatever fixed cost. That's why I wrote the test that way: to see how a
delta in the depth would affect the two approaches.
Still, both compilers could use some work. That fixed cost in g++'s
implementation is quite disturbing. Something happens at the start of
the exception processing on upon its termination which eats up a lot of
time. But once the unwinding loop actually gets going, it's quite
rapid. If that apparently fixed cost could be drastically reduced,
exceptions could compete with normal returns in broader circumstances.
I'm recompiling the program with -pg to get some profiling info out of
it.
The profiling shows that less time is spent in the ex_() functions.
part of the reason for that is that they never return. The way I set up
the test, the recursion just dives straight down and then throws. The
other half of the work, returning, is never done.
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls us/call us/call name
30.40 3.07 3.07 184000000 0.02 0.02 rt_bottom(int,
int)
26.24 5.72 2.65 184000000 0.01 0.01 rt_middle(int,
int)
24.75 8.22 2.50 184000000 0.01 0.01 rt_top(int, int)
6.73 8.90 0.68 184000000 0.00 0.00 ex_top(int, int)
5.94 9.50 0.60 184000000 0.00 0.00 ex_bottom(int,
int)
4.85 9.99 0.49 184000000 0.00 0.00 ex_middle(int,
int)
0.79 10.07 0.08 3000000 0.03 0.03 stop_chrono()
0.20 10.09 0.02 3000000 0.01 0.01 start_chrono()
0.10 10.10 0.01 1000000 0.01 1.78 ex_test(int)
0.00 10.10 0.00 1000000 0.00 8.22 rt_test(int)
0.00 10.10 0.00 21 0.00 0.00 reset_chrono()
0.00 10.10 0.00 21 0.00 0.00
get_average_time()
0.00 10.10 0.00 10 0.00 0.00 putchar
Still, 0.60 seconds spent in all the ex_bottom() calls versus 3.07
seconds in all the rt_bottom() calls. That's a whopping discrepancy
even considering that one of the two actually returns whereas the other
never does. Is it that much more expensive to return from a function
than to enter into it?
It would be nice to profile into the run-time support routines that
support exception handling, which is what I was /really/ after, but it
apperas that for that we'd have to get libgcc.a recompiled with
profiling support.
As you can see, with this compiler, exceptions are always slower.
By the way, I'm skeptical of your results. I have it from a reliable
source that
"after a depth > 800 you get a few microseconds faster
using exceptions on every compiler and architecture. "
Hee hee. Sigh.
.
|
|
|
| User: "Ian Collins" |
|
| Title: Re: using exceptions as a "deep" return |
31 Mar 2006 06:30:55 PM |
|
|
Kaz Kylheku wrote:
Wow, that is quite interesting. Thanks for the data points.
GNU C++ works more according to my intuition about exceptions. I
suspected that just mashing through the stack would be faster than
actually taking the branches through the return points, regardless of
whatever fixed cost. That's why I wrote the test that way: to see how a
delta in the depth would affect the two approaches.
Have you tried higher levels of optimisation? At -O4, CC optimises most
of the code away in the non-exception case, giving a constant time less
than chrono_bias.
Still, both compilers could use some work. That fixed cost in g++'s
implementation is quite disturbing. Something happens at the start of
the exception processing on upon its termination which eats up a lot of
time. But once the unwinding loop actually gets going, it's quite
rapid. If that apparently fixed cost could be drastically reduced,
exceptions could compete with normal returns in broader circumstances.
Considering exceptions are for exceptional circumstances, I'm only realy
concern with normal operation, if the trade of is expensive throwing so
be it.
--
Ian Collins.
.
|
|
|
| User: "Noah Roberts" |
|
| Title: Re: using exceptions as a "deep" return |
31 Mar 2006 11:45:14 PM |
|
|
Ian Collins wrote:
Considering exceptions are for exceptional circumstances, I'm only realy
concern with normal operation, if the trade of is expensive throwing so
be it.
I don't know if you missed it, but that is exactly what this argument
is all about...using exceptions as a standard return mechanism:
http://groups.google.com/group/comp.lang.c++/tree/browse_frm/thread/1a5e7fef082b5472/179d4b2939989852?rnum=11&_done=%2Fgroup%2Fcomp.lang.c%2B%2B%2Fbrowse_frm%2Fthread%2F1a5e7fef082b5472%2Ffea01693094898b0%3F#doc_983fe58585dd209c
.
|
|
|
|
|
| User: "Noah Roberts" |
|
| Title: Re: using exceptions as a "deep" return |
31 Mar 2006 04:43:35 PM |
|
|
Kaz Kylheku wrote:
By the way, I'm skeptical of your results. I have it from a reliable
source that
"after a depth > 800 you get a few microseconds faster
using exceptions on every compiler and architecture. "
Hee hee. Sigh.
.... and _I'm_ the moron.
.
|
|
|
|
|
| User: "Kaz Kylheku" |
|
| Title: Re: using exceptions as a "deep" return |
31 Mar 2006 05:38:26 PM |
|
|
Ian Collins wrote:
bool ex_top(int max_depth, int depth)
{
ex_middle(max_depth, depth + 1);
}
Doesn't gcc complain about the lack of a return?
Ah yes it does! But not if you have -O2 on the command line.
Before I posted the program, I wanted to have a peek at the assembly
language output, to make sure that there was no funny optimization,
like Scheme-like tail calls. But I didn't specify -O2. Now I remember
that the warnings did appear.
The optimized assembly language output shows that gcc has analyzed the
functions and turned the whole thing into tail calls (which I was
hoping wouldn't happen!)
Actually each function builds up and tears down the stack frame, but
then does a jump to the next one. With -fomit-frame-pointer, that
disappears, and here is what ex_top looks like, haha, with identifiers
demangled through c++filt:
..globl ex_top(int, int)
.type ex_top(int, int),@function
ex_top(int, int):
..LFB31:
incl 8(%esp)
..LCFI34:
jmp ex_middle(int, int)
Increment the depth and jump!
This is why the exception returns appear so fast and don't appear to
become more expensive with increasing depth. There are no additional
stack frames to search through.
Let's re-do the test with -O2 and -fno-optimize-sibling-calls. I
changed the ex_() functions to have void returns:
Now the exception times get quite gross. Your Sun compiler trounces
g++:
max_depth = 100
return_time = 0.000001670s
exception_time = 0.000200370s
max_depth = 200
return_time = 0.000003270s
exception_time = 0.000388070s
Ick!
.
|
|
|
|
| User: "Phlip" |
|
| Title: Re: using exceptions as a "deep" return |
30 Mar 2006 04:11:12 PM |
|
|
Kaz Kylheku wrote:
Mark P wrote:
My current approach is to have any of the inner functions throw an
exception if the return value is ever determined early like this.
No problem with this. That is all that C++ style exceptions are,
anyway: a non-local, dynamic return mechanism. For error handling, you
need something better.
Regardless of the "premature optimization" angle, are you disputing Sutter?
;-)
--
Phlip
http://www.greencheese.org/ZeekLand <-- NOT a blog!!!
.
|
|
|
| User: "Mark P" |
|
| Title: Re: using exceptions as a "deep" return |
30 Mar 2006 06:50:04 PM |
|
|
Phlip wrote:
Kaz Kylheku wrote:
Mark P wrote:
My current approach is to have any of the inner functions throw an
exception if the return value is ever determined early like this.
No problem with this. That is all that C++ style exceptions are,
anyway: a non-local, dynamic return mechanism. For error handling, you
need something better.
Regardless of the "premature optimization" angle, are you disputing Sutter?
;-)
I should add one other practical detail to this discussion. In my chain
of function calls, I don't have direct control over some of the
intermediate functions. Specifically, I use a std::set with a custom
comparison functor, and should the functor ever find that two elements
compare equal, it turns out that this implies that the result of my
entire computation is false. So you see that passing back a chain of
return values may not even be possible since the calls to the functor
are dictated by the std::set.
My current solution, in light of all of the earlier discussions, has
been to modify the functor to apply some sort of lexicographic
comparison so that two objects never compare equal. Then the algorithm,
at some later point, will rediscover these two "practically" equal
objects and return false. This could lead to substantially more
computational work before the algorithm makes this discovery on its own.
Another solution I've considered is to have the comparison functor
modify a parameter in the controlling object (i.e., the object directing
the high level computation) and let the controlling object regularly
poll this parameter to see if the computation can be halted. The
comparison functor already has local state and a pointer to the
controlling object for other reasons, so this isn't hard to implement,
but I find this sort of polling to be unappealing. Sort of like
manually implementing exception handling in a very limited way.
In any event, my current direction is to continue with the approach of
paragraph 2 above, not using exceptions and possibly doing extra work
within the algorithm.
Mark
.
|
|
|
| User: "Bart van Ingen Schenau" |
|
| Title: Re: using exceptions as a "deep" return |
31 Mar 2006 11:20:13 AM |
|
|
Mark P wrote:
I should add one other practical detail to this discussion. In my
chain of function calls, I don't have direct control over some of the
intermediate functions. Specifically, I use a std::set with a custom
comparison functor, and should the functor ever find that two elements
compare equal, it turns out that this implies that the result of my
entire computation is false. So you see that passing back a chain of
return values may not even be possible since the calls to the functor
are dictated by the std::set.
Even though you can't change how std::set calls your comparison functor,
that does not preclude finding out if two elements in the set would
compare equal.
std::set allows you to determine this, because one of the invariants of
the class is that no two elements in a std::set ever compare equal. If
you use the simple std::set::insert(Key) function to add elements to
the set, you can immediately look at the return value to determine if
insertion was successful.
If you use some other method of populating the set, you could verify
that after the insertions, the set contains as many elements as you
tried to insert into it.
Mark
Bart v Ingen Schenau
--
a.c.l.l.c-c++ FAQ: http://www.comeaucomputing.com/learn/faq
c.l.c FAQ: http://www.eskimo.com/~scs/C-faq/top.html
c.l.c++ FAQ: http://www.parashift.com/c++-faq-lite/
.
|
|
|
|
| User: "Phlip" |
|
| Title: Re: using exceptions as a "deep" return |
30 Mar 2006 08:07:43 PM |
|
|
Mark P wrote:
My current solution, in light of all of the earlier discussions, has been
to modify the functor to apply some sort of lexicographic comparison so
that two objects never compare equal. Then the algorithm, at some later
point, will rediscover these two "practically" equal objects and return
false. This could lead to substantially more computational work before
the algorithm makes this discovery on its own.
Hmm. Someday all of us hope to be good enough at STL to be able to tell the
difference between an elegant solution and STL abuse.
Right now I'm just thinking "wow! functors!", and can't constructively
criticize them!
Another solution I've considered is to have the comparison functor modify
a parameter in the controlling object (i.e., the object directing the high
level computation) and let the controlling object regularly poll this
parameter to see if the computation can be halted. The comparison functor
already has local state and a pointer to the controlling object for other
reasons, so this isn't hard to implement, but I find this sort of polling
to be unappealing. Sort of like manually implementing exception handling
in a very limited way.
In any event, my current direction is to continue with the approach of
paragraph 2 above, not using exceptions and possibly doing extra work
within the algorithm.
Why not assign the boolean to a member of the root-most object, then croak
all the inner loops?
--
Phlip
http://www.greencheese.org/ZeekLand <-- NOT a blog!!!
.
|
|
|
| User: "Mark P" |
|
| Title: Re: using exceptions as a "deep" return |
30 Mar 2006 08:42:20 PM |
|
|
Phlip wrote:
Mark P wrote:
My current solution, in light of all of the earlier discussions, has been
to modify the functor to apply some sort of lexicographic comparison so
that two objects never compare equal. Then the algorithm, at some later
point, will rediscover these two "practically" equal objects and return
false. This could lead to substantially more computational work before
the algorithm makes this discovery on its own.
Hmm. Someday all of us hope to be good enough at STL to be able to tell the
difference between an elegant solution and STL abuse.
Right now I'm just thinking "wow! functors!", and can't constructively
criticize them!
Another solution I've considered is to have the comparison functor modify
a parameter in the controlling object (i.e., the object directing the high
level computation) and let the controlling object regularly poll this
parameter to see if the computation can be halted. The comparison functor
already has local state and a pointer to the controlling object for other
reasons, so this isn't hard to implement, but I find this sort of polling
to be unappealing. Sort of like manually implementing exception handling
in a very limited way.
In any event, my current direction is to continue with the approach of
paragraph 2 above, not using exceptions and possibly doing extra work
within the algorithm.
Why not assign the boolean to a member of the root-most object, then croak
all the inner loops?
If I understand you, I think that's basically what I said in the
preceding paragraph about polling a parameter. As I said though, I find
this unappealing and it feels like manual exception handling.
.
|
|
|
|
|
|
|
|
Related Articles |
|
|
