using exceptions as a "deep" return

[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

[Herb Sutter]

Mark P <us****@fall200 5REMOVE.fastmai lCAPS.fm> wrote:

Phlip wrote:

Mark P wrote:

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.

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.)
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).

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

---
Herb Sutter (www.gotw.ca) (www.pluralsight.com/blogs/hsutter)

Convener, ISO WG21 (C++ standards committee) (www.gotw.ca/iso)
Architect, Developer Division, Microsoft (www.gotw.ca/microsoft)

[Phlip]

Herb Sutter wrote:

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).

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 "unpredicta ble, uncorrectable, and dangerous" as shorter, without
shifting the burden of definition from exceptions to invariants.

--
Phlip
http://www.greencheese.org/ZeekLand <-- NOT a blog!!!

[Kaz Kylheku]

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.

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_computat ion()
{
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.

[Phlip]

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!!!

[Noah Roberts]

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.

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_computat ion()
{
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.

[Phlip]

Noah Roberts wrote:

Try it both ways and do some timing.

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!

--
Phlip
http://www.greencheese.org/ZeekLand <-- NOT a blog!!!

[Noah Roberts]

Phlip wrote:

Noah Roberts wrote:

Try it both ways and do some timing.

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?

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<uns igned long>(GetTickCo unt()) << endl;
for (int i = 0; i < 5000; ++i)
{
bool b = f();
int x = b ? 0:1;
}
cout << static_cast<uns igned long>(GetTickCo unt()) << 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...

[Noah Roberts]

Noah Roberts wrote:

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<uns igned long>(GetTickCo unt()) << endl;
for (int i = 0; i < 5000; ++i)
{
bool b = f();
int x = b ? 0:1;
}
cout << static_cast<uns igned long>(GetTickCo unt()) << endl;
}

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

int x;
cin >> x;
}

[Mark P]

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 "practicall y" 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

[Phlip]

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 "practicall y" 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!!!