using exceptions as a "deep" return

M

Mark P

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
 
A

Alf P. Steinbach

* Mark P:
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?

In some rare cases it can be a good approach.

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.

Measure -- that's the /only/ reasonable advice.

However, also see "ISO/IEC TR 18015:2006 C++ Performance - draft TR" at
<url: http://www.open-std.org/jtc1/sc22/wg21/docs/TR18015.pdf>.
 
P

Phlip

Mark said:
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.

Did you measure how fast this implementation is, compared to a version that
returns the value back up the stack? Both activities must unwind the stack,
so (for some C++ implementations) returning the value might be faster.

You need a better reason than "I don't feel like typing lots of return
statements" to violate the guideline in /C++ Coding Standards/ by Sutter &
Alexandrescu called "Use Exceptions for Exceptional Situations" (IIRC).
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.

This is a topic of many discussions, including philosophical ones over
whether a language should support exceptions at all. Google will find reams.
A more important question: Will anyone ever care if this routine is fast, or
are you just indulging in Creative Coding?
 
M

Mark P

Phlip said:
Did you measure how fast this implementation is, compared to a version that
returns the value back up the stack? Both activities must unwind the stack,
so (for some C++ implementations) returning the value might be faster.

You need a better reason than "I don't feel like typing lots of return
statements" to violate the guideline in /C++ Coding Standards/ by Sutter &
Alexandrescu called "Use Exceptions for Exceptional Situations" (IIRC).

It was this very phrase that prompted my question. I'm not sure whether
or not my situation qualifies as exceptional, but I'll consider this
further.
This is a topic of many discussions, including philosophical ones over
whether a language should support exceptions at all. Google will find reams.
A more important question: Will anyone ever care if this routine is fast, or
are you just indulging in Creative Coding?

Thanks for the advice. Yes, speed is critically important. Think
geometry processing for large scale semiconductor designs. I don't
really care how fast the exception handling is, within reason, since it
should be rare. My question was motivated by style and coding practice
concerns.

As far as actual performance issues, I only wonder whether code which
supports exception handling, though an exception is not actually thrown,
will suffer any performance degradation. My instinct is not, since lots
of things could throw runtime exceptions and I never give these a
thought as far as affecting performance, but then as you can see I don't
really know.
 
I

Ian Collins

Mark said:
As far as actual performance issues, I only wonder whether code which
supports exception handling, though an exception is not actually thrown,
will suffer any performance degradation. My instinct is not, since lots
of things could throw runtime exceptions and I never give these a
thought as far as affecting performance, but then as you can see I don't
really know.

As Phlip said, this has been debated at length here. In my experience,
with my compilers, you are correct.
 
P

Pete Becker

Mark said:
As far as actual performance issues, I only wonder whether code which
supports exception handling, though an exception is not actually thrown,
will suffer any performance degradation.

The answer is yes. While it's theoretically possible to write exception
handling code that does not inject any additional opcodes when no
exceptions are thrown, that's not all there is to performance. Such
implementations need data tables that must be available at runtime. That
means a bigger footprint, higher disk usage, maybe slower startup. And,
of courese, if you're not using an implementation that does that, you
may well have added code even when there no exceptions are thrown. More
important, if an exception is thrown, typical execution time is several
orders of magnitude slower than an ordinary return.
 
P

Phlip

Mark said:
It was this very phrase that prompted my question. I'm not sure whether
or not my situation qualifies as exceptional, but I'll consider this
further.

Your situation is the normal control flow, not the exceptional
(unpredictable, uncorrectable, and risky) control flow.
Thanks for the advice. Yes, speed is critically important.

Ah, then you have lots of unit tests, and you can time them. And when they
reveal bottlenecks you can tune the code and still pass all the tests.
Think geometry processing for large scale semiconductor designs. I don't
really care how fast the exception handling is, within reason, since it
should be rare. My question was motivated by style and coding practice
concerns.

Then the most important resource to optimize is programmer time. Write the
simple code, not the clever-clever code.
 
R

Rolf Magnus

Mark said:
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.

Stroustrup has a similar example in TC++PL:

void fnd(Tree* p, const string& s)
{
if (s == p->str) throw p;
if (p->left) fnd(p->left, s);
if (p->right) fnd(p->right, s);
}

Tree* find(Tree* p, const string& s)
{
try {
fnd(p, s);
}
catch (Tree* q)
{
return q;
}
return 0;
}
 
M

Mark P

Pete said:
The answer is yes. While it's theoretically possible to write exception
handling code that does not inject any additional opcodes when no
exceptions are thrown, that's not all there is to performance. Such
implementations need data tables that must be available at runtime. That
means a bigger footprint, higher disk usage, maybe slower startup. And,
of courese, if you're not using an implementation that does that, you
may well have added code even when there no exceptions are thrown. More
important, if an exception is thrown, typical execution time is several
orders of magnitude slower than an ordinary return.

Thanks. Your comments and others have convinced me to choose a
different route and I have changed my code to avoid this usage.

I'm curious about one point you made, which is that an implementation
may have added code even when no exceptions are thrown. Wouldn't that
same code be generated anyway since all sorts of functions not written
by me may also throw exceptions?

Mark
 
H

Herb Sutter

Please don't do that. :) While Andrei and I were writing C++ Coding
Standards, Bjarne specifically asked us to include the following
example... quoting from C++CS Item 72, which in turn references
[Stroustrup00] (The C++ Programming Language special 3rd ed.):

Example 2: Successful recursive tree search. When searching a
tree using a recursive algorithm, it can be tempting to return the
result -- and conveniently unwind the search stack -- by throwing
the result as an exception. But don't do it: An exception means
an error, and finding the result is not an error (see [Stroustrup00]).

At the end of the Item, the specific sections of [Stroustrup00] listed are
§8.3.3, §14.1, §14.4-5, §14.9, §E.3.5. (There are also references to other
books supporting the standards set out in the Item.)

Actually, I deliberately did _not_ use that phrase, because that
commonly-stated bit of wisdom is too vague and subjective. :) Indeed, as
Mark responded:
It was this very phrase that prompted my question. I'm not sure whether
or not my situation qualifies as exceptional, but I'll consider this
further.

You won't find that phrase in C++CS. Rather, C++CS Item 72 gives rigorous,
objective, and measurable guidance when it says:

Almost by definition, exceptions are for reporting
exceptions to normal processing-also known as "errors," defined
in Item 70 as violations of preconditions, postconditions, and
invariants. Like all error reporting, exceptions should not arise
during normal successful operation.

And later:

if you're throwing so frequently that the exception
throwing/catching handling performance overhead is actually
noticeable, you're almost certainly using exceptions for conditions
that are not true errors and therefore not correctly distinguishing
between errors and non-errors (see Item 70)

So that Item explicitly addresses this anti-idiom at least three times.
:) Interestingly, note that the Item's title is:

72. Prefer to use exceptions to report errors.

Note this works two ways: 1. Report errors using exceptions as opposed to
other methods (such as error codes or errno). 2. Use exceptions to report
errors as opposed to other conditions (such as successful search).
As far as actual performance issues, I only wonder whether code which
supports exception handling, though an exception is not actually thrown,
will suffer any performance degradation. My instinct is not, since lots
of things could throw runtime exceptions and I never give these a
thought as far as affecting performance, but then as you can see I don't
really know.

Compilers vary, but many compilers do implement EH to have zero cost when
an exception is not thrown. (FWIW, Visual C++ has this zero-cost EH in
64-bit mode, but unfortunately couldn't easily switch to this in 32-bit
mode due to backward binary compatibility issues.)

Herb
 
P

Phlip

Herb said:
Actually, I deliberately did _not_ use that phrase, because that
commonly-stated bit of wisdom is too vague and subjective. :)

When I indeed read whatever you two wrote in C++CS, I swooned with relief
that someone had so forcibly decried the VB6 technique of testing a
container for membership by dropping a key in and catching an error
exception. This prevented me from remembering the exact verbiage, as I hope
you can understand. IIRC.
You won't find that phrase in C++CS. Rather, C++CS Item 72 gives rigorous,
objective, and measurable guidance when it says:

Almost by definition, exceptions are for reporting
exceptions to normal processing-also known as "errors," defined
in Item 70 as violations of preconditions, postconditions, and
invariants. Like all error reporting, exceptions should not arise
during normal successful operation.

I liked my "unpredictable, uncorrectable, and dangerous" as shorter, without
shifting the burden of definition from exceptions to invariants.
 
K

Kaz Kylheku

Mark said:
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.

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.

OO dispatch is glorified goto also, and aspect-oriented programming is
glorified come-from. Who cares.
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.

There shouldn't be, but the reality is that exception handling
implementations bloat up code. There is always a penalty; you don't get
something for nothing. Even if you have instructions that are never
run, or data interspersed with code, that affects caching, and on a
larger scale, VM performance.

But note that in a reasonable implementation of exception handling, a
function that doesn't contain any try block, and has no local objects
whose destructors need calling, should have no evidence of any
exception handling support in the translated machine code.

In any case, it's not clear what the performance implications are and
are very likely to be compiler-specific.

You may be saving cycles by bailing out using exceptions in those cases
where it's obvious that the computation can short-circuit out with a
false value. It's possible that the search for the exception handler
across all those activation frames is faster than actually returning to
each frame and executing a return instruction, particularly if you are
also communicating some data back to the top level. If thre are no
destructors to clean up at a particular frame, no unwinding work to do,
there is no reason for control to jump there at all. In the ideal case,
the search finds the destination handler, restores the stack to that
point and branches directly there.

You might want to think about handling /all/ return cases this way,
rather than supporting a mixture of ordinary returns and exceptions.
I.e. always use throw to return in the false case, and use a normal
return to signal true:

bool nested_computation()
{
try {
recursive_part();
return true;
} catch (...) {
return false;
}
}

You never have to check any return values at any level. There is an
implicit short-circuiting AND between any two calls to the lower
levels, so inside the recursive function tree you have code like this:

{
try_this();
try_that();
try_other_thing();
}

If try_this() determines falsehood, it throws, and so try_that() is
never run. Otherwise it just returns normally, and try_that() is tried.
The code has no tests, no branches. Just a sequence of calls.

If everything returns a value, then you'd have to write this as:

return try_this() && try_that() && try_other_thing();

This has tests and branches!

So you actually have an opportunity to simplify that common case if you
use that exception as the protocol for returning from the hierarchy
whenever there is a false value computed.

Try it both ways and do some timing.
 
P

Phlip

Kaz said:
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?

;-)
 
N

Noah Roberts

Kaz said:
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.



OO dispatch is glorified goto also, and aspect-oriented programming is
glorified come-from. Who cares.



There shouldn't be, but the reality is that exception handling
implementations bloat up code. There is always a penalty; you don't get
something for nothing. Even if you have instructions that are never
run, or data interspersed with code, that affects caching, and on a
larger scale, VM performance.

But note that in a reasonable implementation of exception handling, a
function that doesn't contain any try block, and has no local objects
whose destructors need calling, should have no evidence of any
exception handling support in the translated machine code.

In any case, it's not clear what the performance implications are and
are very likely to be compiler-specific.

You may be saving cycles by bailing out using exceptions in those cases
where it's obvious that the computation can short-circuit out with a
false value. It's possible that the search for the exception handler
across all those activation frames is faster than actually returning to
each frame and executing a return instruction, particularly if you are
also communicating some data back to the top level. If thre are no
destructors to clean up at a particular frame, no unwinding work to do,
there is no reason for control to jump there at all. In the ideal case,
the search finds the destination handler, restores the stack to that
point and branches directly there.

You might want to think about handling /all/ return cases this way,
rather than supporting a mixture of ordinary returns and exceptions.
I.e. always use throw to return in the false case, and use a normal
return to signal true:

bool nested_computation()
{
try {
recursive_part();
return true;
} catch (...) {
return false;
}
}

You never have to check any return values at any level. There is an
implicit short-circuiting AND between any two calls to the lower
levels, so inside the recursive function tree you have code like this:

{
try_this();
try_that();
try_other_thing();
}

If try_this() determines falsehood, it throws, and so try_that() is
never run. Otherwise it just returns normally, and try_that() is tried.
The code has no tests, no branches. Just a sequence of calls.

If everything returns a value, then you'd have to write this as:

return try_this() && try_that() && try_other_thing();

This has tests and branches!

So you actually have an opportunity to simplify that common case if you
use that exception as the protocol for returning from the hierarchy
whenever there is a false value computed.

Try it both ways and do some timing.

You're joking right?

I sure hope so.

You have to be.

HAHAHAHA - good one.
 
P

Phlip

Noah said:
You're joking right?

The topic we have all been avoiding:

Is it possible, somewhere, somehow, that throwing the exception could
actually be faster than returning?

The odds are extremely low, because compiler implementers have overwhelming
incentive to optimize the non-exceptional control path at the expense of
the exceptional one. But I don't think anyone has asked or answered that
question.

Confession: I once used setjmp() and longjmp(), in C, for this very
convenience. I can't remember profiling it, but because longjmp() simply
whacks your stack, its opcodes are indeed faster!
 
N

Noah Roberts

Phlip said:
The topic we have all been avoiding:

Is it possible, somewhere, somehow, that throwing the exception could
actually be faster than returning?

Well, you rather took my quote out of context as I was replying to the
entire idea of using exceptions as an if statement but I did some
testing. There is no real comparison. The exception version performs
noticably worse in the most trivial case and by the time the if version
takes any measurable time at all the exception version has become so
out of hand as to not even run adiquately and requiring _hard_
stopping.

Results:
29055421
29055421
29055421
29057890

First two are start and end of 5000 iterations of "if" test. 3 & 4th
are begin and end of 5000 iterations of exception test. 5000 is about
as high as you can really go with the exception version.

Code:

#include <iostream>
#include <windows.h> // for cpu tick count.

using namespace std;

void te1() {}
void te2() {}
void te3() { throw false; }

bool tb1() { return true; }
bool tb2() { return true; }
bool tb3() { return false; }

bool tem()
{
try
{
te1(); te2(); te3();
return true;
}
catch (...)
{
return false;
}
}

bool tbm() { return tb1() && tb2() && tb3(); }

void test(bool (*f)())
{
cout << static_cast<unsigned long>(GetTickCount()) << endl;
for (int i = 0; i < 5000; ++i)
{
bool b = f();
int x = b ? 0:1;
}
cout << static_cast<unsigned long>(GetTickCount()) << endl;
}

int main()
{
test(tbm);
test(tem);

int x;
cin >> x;
}

Regardless of how this test had turned out I think it still a bad idea
to do what the person I was replying to was recommending. Exceptions
are NOT a return mechanism. The resulting code of that method of
design doesn't adiquately convey its purpose for one.

This is not a recursive test, I will perform that now and post
results...
 
N

Noah Roberts

Noah said:
This is not a recursive test, I will perform that now and post
results...

29673156
29673156
29673156
29675625

500 iterations of 520 tests. Can't do more or exception version would
take forever. Guess that settles the speed question, no?

#include <iostream>

#include <Windows.h>

using namespace std;

void te1(int i = 0) { if (i < 500) te1(i + 1); }
void te2(int i = 0) { if (i == 20) throw 5; te2(i + 1);}
void te3(int i = 0) { if (i < 500) te3(i + 1); }

bool tb1(int i = 0) { if (i == 500) return true; return tb1(i + 1); }
bool tb2(int i = 0) { if (i == 20) return false; return tb2(i + 1); }
bool tb3(int i = 0) { if (i == 500) return true; return tb3(i + 1); }

bool tem()
{
try
{
te1(); te2(); te3();
return true;
}
catch (...)
{
return false;
}
}

bool tbm() { return tb1() && tb2() && tb3(); }

void test(bool (*f)())
{
cout << static_cast<unsigned long>(GetTickCount()) << endl;
for (int i = 0; i < 5000; ++i)
{
bool b = f();
int x = b ? 0:1;
}
cout << static_cast<unsigned long>(GetTickCount()) << endl;
}

int main()
{
test(tbm);
test(tem);

int x;
cin >> x;
}
 
M

Mark P

Phlip said:
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
 
P

Phlip

Mark said:
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?
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top