By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,310 Members | 1,430 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,310 IT Pros & Developers. It's quick & easy.

using exceptions as a "deep" return

P: n/a
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
Mar 30 '06 #1
Share this Question
Share on Google+
40 Replies


P: n/a
* 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>.
--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Mar 30 '06 #2

P: n/a
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.
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?

--
Phlip
http://www.greencheese.org/ZeekLand <-- NOT a blog!!!
Mar 30 '06 #3

P: n/a
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.


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


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.
Mar 30 '06 #4

P: n/a
Alf P. Steinbach wrote:
* 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>.


Great link, thanks.
Mar 30 '06 #5

P: n/a
Mark P wrote:

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.

--
Ian Collins.
Mar 30 '06 #6

P: n/a
Mark P wrote:

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.

--

Pete Becker
Roundhouse Consulting, Ltd.
Mar 30 '06 #7

P: n/a
Mark P wrote:
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.

--
Phlip
http://www.greencheese.org/ZeekLand <-- NOT a blog!!!
Mar 30 '06 #8

P: n/a
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.


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;
}

Mar 30 '06 #9

P: n/a
Pete Becker wrote:
Mark P wrote:

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.


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
Mar 30 '06 #10

P: n/a
Mark P <us****@fall2005REMOVE.fastmailCAPS.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)
Mar 30 '06 #11

P: n/a
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 "unpredictable, uncorrectable, and dangerous" as shorter, without
shifting the burden of definition from exceptions to invariants.

--
Phlip
http://www.greencheese.org/ZeekLand <-- NOT a blog!!!
Mar 30 '06 #12

P: n/a
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_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.

Mar 30 '06 #13

P: n/a
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!!!
Mar 30 '06 #14

P: n/a

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

Mar 30 '06 #15

P: n/a
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!!!
Mar 30 '06 #16

P: n/a

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

Mar 30 '06 #17

P: n/a

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<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;
}

Mar 31 '06 #18

P: n/a
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
Mar 31 '06 #19

P: n/a
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!!!
Mar 31 '06 #20

P: n/a
Noah Roberts wrote:
500 iterations of 520 tests. Can't do more or exception version would
take forever. Guess that settles the speed question, no?


Thanks! But I can't tell what you mean by the results. Which was slower?

And we need Pete Becker to tell us if the depth of the call tree matters,
and if filling its stack frames with huge objects with expensive destructors
matters.

--
Phlip
http://www.greencheese.org/ZeekLand <-- NOT a blog!!!
Mar 31 '06 #21

P: n/a
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.
Mar 31 '06 #22

P: n/a

"Phlip" <ph*******@gmail.com> wrote in message
news:1D*******************@newssvr30.news.prodigy. com...

The topic we have all been avoiding:

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


I have implemented a min-max game tree scanner with alpha/beta
cutoff, where Alpha and Beta were implemented as exceptions.

This makes the algorithmic code so clean that there is no strictly
equivalent "orthodox" version that it could be compared against
without adding non-trivial amount of structural code. Comparing
the version having the necessary extra wiring, their performance
was about the same, but the simplicity of the exception-based
algorithm made me stick with it (FWIW, the product was initially
shareware and later "slightly commercialized", e.g. tagged with
some ads of a company who bought its distribution for marketing
purposes).

For background: both Alpha and Beta cutoffs are such that when
they occur, the game tree preorder scanner can prune exactly two
levels of recursion (i.e. to the next level of the _same_ player in a
two-player game). This can be a bit tedious to implement without
using exceptions, since a flag needs to be added in every return
value of the scoring function to indicate whether an Alpha or Beta
cutoff may occur, and this flag also needs to be checked in every
iteration of the level in the middle.

Cheers!

- Risto -
Mar 31 '06 #23

P: n/a

Risto Lankinen wrote:
For background: both Alpha and Beta cutoffs are such that when
they occur, the game tree preorder scanner can prune exactly two
levels of recursion (i.e. to the next level of the _same_ player in a
two-player game). This can be a bit tedious to implement without
using exceptions, since a flag needs to be added in every return
value of the scoring function to indicate whether an Alpha or Beta
cutoff may occur, and this flag also needs to be checked in every
iteration of the level in the middle.


Me thinks maybe you misunderstand the algorithm and/or have implemented
it inefficiently. Either that or you are talking about a different
algorithm, not the one designed by Knuth to improve the NegaMax. For
one thing, your statement that it, "can prune exactly two levels of
recursion," doesn't ring true. AB narrows the search window as it goes
so that it can drop uninteresting branches (complete branches, even at
the root+1) without searching them completely...as soon as it 'knows'
that the score is at least worse than some other, better move. The
assumption behind AB is that you and your opponent will always make the
best move that is possible.

int Search::search(int depth, int alpha, int beta)
{
if (depth == _targetDepth) //return
evaluator->fullEval(_searchBoard.get());
return quiescence(alpha, beta);

MoveList *moves = _moveControl->generateMoves(_searchBoard.get());
u_int16 m = moves->nextMove();
while (m && alpha < beta)
{
Move *move = new Move((m>>8), (m&0xFF));
_searchBoard->makeMove(move);
int score = -search(depth + 1, -beta, -alpha);
_searchBoard->unmakeMove(move);
if (score > alpha) alpha = score;
m = moves->nextMove();
delete move;
}
_moveControl->destroyMoves(moves);
return alpha;
}

I wrote this a few years ago before really learning that _ was bad so
forgive the icky variable names.

This same search function can be used with MTD(f) and other window
guessing searches. No flags, incredibly simple, and no using
exceptions as the return mechanism. Just a window and a target depth.

quiescence is a depthless version of the same algorithm that uses a
capture or escape only move generator meant to limit the horizon
effect.

Now, there are extensions to the basic AB search that you can add that
I am not doing. Null move heuristic, move ordering, etc... Move
ordering should be done by the generator so that is a non-issue. Null
move is an easy addition. Search extensions is something I hadn't
quite learned all the way and implemented when I last worked on this
guy...they do add a little bit extra in code. But the basic AB search,
like above, doesn't require the things you are talking about.

I've already shown exceptions to be significantly slower, by several
orders of magnitude, than the standard return mechanism, on at least
one widely used architecture/compiler and in an area like this search
that is extreemly important...the AB has to be fast or you will never
get deep enough to play decently. They also add nothing to the bargain
so they are a pure loss when used as a return mechanism. Exceptions
are for errors.

Mar 31 '06 #24

P: n/a
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/
Mar 31 '06 #25

P: n/a

Noah Roberts wrote:
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>


Oh man, what an incompetent moron.

ANSI C gives us the clock() function for doing this type of thing. No
need for Windows extensions.
void test(bool (*f)())
{
cout << static_cast<unsigned long>(GetTickCount()) << endl;


Good one, let's sample the tick count just before ostream flushes its
buffer to the operating system.

Let's not care about the time it takes to call GetTickCount().

Let's not take multiple samples of time and average them together.

Let's not parametrize anything interesting, like the call stack depth.

Mar 31 '06 #26

P: n/a
Kaz Kylheku wrote:
Oh man, what an incompetent moron.

ANSI C gives us the clock() function for doing this type of thing. No
need for Windows extensions.


You must be describing yourself. clock() has a resolution in tens of
milliseconds. Everyone knows it's not good for profiling.

Or would you have lost your cool over a POSIX method posted here?

--
Phlip
http://www.greencheese.org/ZeekLand <-- NOT a blog!!!
Mar 31 '06 #27

P: n/a

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?


Yes. Here is a benchmark program.

First, the CPU and compiler information. Linux gives us this, so I will
just paste. This box has four of these processors, by the way:

processor : 0
vendor_id : GenuineIntel
cpu family : 15
model : 4
model name : Intel(R) Xeon(TM) CPU 2.80GHz
stepping : 1
cpu MHz : 2793.087
cache size : 1024 KB
physical id : 0
siblings : 2
runqueue : 0
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 5
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge
mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm lm
bogomips : 5570.56

Next, the compiler, GNU C++:

g++ (GCC) 3.2.3 20030502 (Red Hat Linux 3.2.3-49)

I just used this with -O2 to make an a.out.

The program:

#include <cstdio>
#include <ctime>

using std::printf;
using std::clock_t;
using std::clock;

const int calibrate_iterations = 1000000;
const int return_test_iterations = 100000;
const int exception_test_iterations = 100000;

const int num_call_depths = 10;
const int starting_call_depth = 100;
const int call_depth_increment = 100;

static clock_t start;
static long sample_sum;
static long sample_count;

static void reset_chrono()
{
start = sample_sum = sample_count = 0;
}

static void start_chrono()
{
start = clock();
}

static void stop_chrono()
{
clock_t stop = clock();
clock_t diff = stop - start;
sample_sum += diff;
sample_count++;
}

double get_average_time()
{
return ((double) sample_sum) / sample_count / CLOCKS_PER_SEC;
}

/*
* Regular return.
*/

bool rt_top(int, int = 0);
bool rt_middle(int, int);
bool rt_bottom(int, int);

bool rt_test(int max_depth)
{
return rt_top(max_depth);
}

bool rt_top(int max_depth, int depth)
{
return rt_middle(max_depth, depth + 1);
}

bool rt_middle(int max_depth, int depth)
{
return rt_bottom(max_depth, depth + 1);
}

bool rt_bottom(int max_depth, int depth)
{
if (depth >= max_depth)
return false;
return rt_top(max_depth, depth + 1);
}

/*
* Exception-based return
*/

bool ex_top(int, int = 0);
bool ex_middle(int, int);
bool ex_bottom(int, int);

bool ex_test(int max_depth)
try {
return ex_top(max_depth);
} catch (...) {
return false;
}

bool ex_top(int max_depth, int depth)
{
ex_middle(max_depth, depth + 1);
}

bool ex_middle(int max_depth, int depth)
{
ex_bottom(max_depth, depth + 1);
}

bool ex_bottom(int max_depth, int depth)
{
if (depth >= max_depth)
throw false;
ex_top(max_depth, depth + 1);
}
int main()
{
/*
* First, calibrate test.
*/

reset_chrono();

for (int i = 0; i < calibrate_iterations; i++) {
start_chrono();
stop_chrono();
}

double chrono_bias = get_average_time();

printf("chrono_bias = %12.9fs\n", chrono_bias);

/*
* Now do return speed test.
*/

for (int depth = 0; depth < num_call_depths; depth++) {
int max_depth = starting_call_depth + depth *
call_depth_increment;

reset_chrono();

for (int i = 0; i < return_test_iterations; i++) {
start_chrono();
rt_test(max_depth);
stop_chrono();
}

double return_time = get_average_time() - chrono_bias;

reset_chrono();

for (int i = 0; i < exception_test_iterations; i++) {
start_chrono();
ex_test(max_depth);
stop_chrono();
}

double exception_time = get_average_time() - chrono_bias;

printf("\n");
printf("max_depth = %d\n", max_depth);
printf("return_time = %12.9fs\n", return_time);
printf("exception_time = %12.9fs\n", exception_time);
}

return 0;
}
The results:

chrono_bias = 0.000000400s

max_depth = 100
return_time = 0.000002000s
exception_time = 0.000009000s

max_depth = 200
return_time = 0.000003000s
exception_time = 0.000009400s

max_depth = 300
return_time = 0.000004900s
exception_time = 0.000009900s

max_depth = 400
return_time = 0.000006300s
exception_time = 0.000010000s

max_depth = 500
return_time = 0.000007700s
exception_time = 0.000010800s

max_depth = 600
return_time = 0.000009400s
exception_time = 0.000010500s

max_depth = 700
return_time = 0.000010900s
exception_time = 0.000011300s

max_depth = 800
return_time = 0.000012800s
exception_time = 0.000011100s

max_depth = 900
return_time = 0.000014200s
exception_time = 0.000011900s

max_depth = 1000
return_time = 0.000016400s
exception_time = 0.000012100s
As you can see, as the stack grows deeper, the exception mechanism
eventually becomes faster. The break-even point is somewhere at a depth
of about 700 to 800.

The results suggest that that exceptions have a high fixed cost on this
compiler, but a marginal additional cost to jump deeper.

In one experimental run, I moved the start_chrono() call for the
exception test to within the try { } region, and the results weren't
significantly affected. So there isn't much cost to setting up the
catch. The large, fixed overhead is somewhere in the processing of the
exception.

Mar 31 '06 #28

P: n/a

Kaz Kylheku wrote:
Noah Roberts wrote:
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>


Oh man, what an incompetent moron.


Heh. Can't argue on technical merit alone eh?
ANSI C gives us the clock() function for doing this type of thing. No
need for Windows extensions.
Guess you don't know that clock() can return just about anything,
useful or otherwise.

If the fact that I used the windows api instead of clock is the best
you got then you ain't got shit. The question is simply, so what if I
used one over the other? Do you know the differences enough to answer
that?
void test(bool (*f)())
{
cout << static_cast<unsigned long>(GetTickCount()) << endl;
Good one, let's sample the tick count just before ostream flushes its
buffer to the operating system.


Done in both cases and small enough to not show up in
measurements...irrelivant
Let's not care about the time it takes to call GetTickCount().
irrelivant....less than 1 millisecond...done in both.

Let's not take multiple samples of time and average them together.
5000 is not enough samples??!! I could do more but then I would have
to take the exception test out as it would take way too long.

You can do the math to get the average if you really want...its
easy...(v2 - v1)/5000

Let's not parametrize anything interesting, like the call stack depth.


Granted, it isn't a perfect test but it also doesn't have to be. With
differences that great you don't need to get into much detail. It is
sufficient to show that in a simple case like above, the one you
described, using exceptions as a return mechanism (something they were
never intended to be) is several orders of magnitude slower than using
the _appropriate_ mechanism built for that purpose. No other factor in
that test can make enough difference to account for the vast difference
in results.

The second and third output show that the time it takes to call
GetTickCount and flush the buffer is so minute that it is not
measurable in milliseconds. Since we are dealing with a difference of
nearly 2500 milliseconds the impact of a variable adding less than 1
millisecond has negligable effects.

But go ahead and continue using the language wrong. Keep writing code
that is incredibly ineffecient. Keep calling everyone else a moron.
So long as I don't ever have to fix it I don't care.

Mar 31 '06 #29

P: n/a

Kaz Kylheku wrote:
As you can see, as the stack grows deeper, the exception mechanism
eventually becomes faster. The break-even point is somewhere at a depth
of about 700 to 800.


Of course that is good because after a depth > 800 you get a few
microseconds faster using exceptions on every compiler and architecture.

Mar 31 '06 #30

P: n/a
Phlip wrote:
Kaz Kylheku wrote:
Oh man, what an incompetent moron.

ANSI C gives us the clock() function for doing this type of thing. No
need for Windows extensions.
You must be describing yourself. clock() has a resolution in tens of
milliseconds.


So does GetTickCount(). ISTR that on some WinCE systems, they crank it
up a bit, but normally it's 100Hz.
Everyone knows it's not good for profiling.
Idiot, you need a high resolution hardware clock in order to time a
/single/ event accurately. If you can repeat the event enough times,
you can use averaging to magnify the precision of a low resolution
clock.

You can even time events that are much shorter than the granularity of
the clock.

Suppose that you have a clock that increments every millisecond. Over
many trials, the event you are timing reads as zero milliseconds about
90% of the time, but 10% of the time, it registers as one millisecond.From that, you can estimate the duration of the event to be 0.1 milliseconds. One way to look at it is that there is a 10%
probability that the increment of the clock lands in the middle of the
event, which means that the event spans 10% of the clock period. This
estimate does assume that there is no bias introduced by some
dependency between the clock and the timing of event.

I think this has to do with that probability and statistics stuff I had
to pass once upon a time to get a CS degree. What do you think?
Or would you have lost your cool over a POSIX method posted here?


I haven't lost my cool; I just like to insult stupid people, because it
feels good.

Why don't you go net-psychoanalyze someone else.

Mar 31 '06 #31

P: n/a
Noah Roberts wrote:
Of course that is good because after a depth > 800 you get a few
microseconds faster using exceptions on every compiler and architecture.


You might consider focussing on people you can actually learn from here.

(And also me;)

--
Phlip
http://www.greencheese.org/ZeekLand <-- NOT a blog!!!
Mar 31 '06 #32

P: n/a
Noah Roberts wrote:
Let's not take multiple samples of time and average them together.
5000 is not enough samples??!! I could do more but then I would have
to take the exception test out as it would take way too long.


5000 is the number times the function is called, not the number of
times the clock is sampled.

Calling the function isn't sampling. Reading the clock is sampling.
You can do the math to get the average if you really want...its
easy...(v2 - v1)/5000
That depends on whether v2 and v1 have a good enough resolution
relative to the 5000, since they represent a single sampled clock
delta.

In the case of the return test, you witnessed that there was usually no
increment of the clock at all, so a zero average would be computed. At
odd times, you might catch a single increment of the tick by 10
milliseconds, and at those times, the above formula would yield 1/500th
of a millisecond.

A more accurate estimate is somwhere between zero and 1/500 ms, and can
be obtained with more clock samples.
Let's not parametrize anything interesting, like the call stack depth.


Granted, it isn't a perfect test but it also doesn't have to be. With
differences that great you don't need to get into much detail. It is
sufficient to show that in a simple case like above, the one you
described, using exceptions as a return mechanism (something they were
never intended to be)


Regardless of their intent, slow or fast, exceptions are a dynamic
non-local return mechanism. That is what they are. This is semantically
proved by the fact that in fact function activations terminate and
control ends up at a higher level.
is several orders of magnitude slower than using the _appropriate_ mechanism built for that purpose.


You don't appear to be qualified to prescribe to others what is an
appropriate mechanism for a given purpose.

I reproduced a situation in which returning to a top level by exception
was faster than cascading returns.

I didn't deserve to be insulted for proposing the skeptical hypothesis
that under some circumstances, it /might/ be faster to return by
exception.

I defended that hypothesis. And thus my wristwatch tells me that I'm,
oh, right about done here.

Mar 31 '06 #33

P: n/a
Kaz Kylheku wrote:
Phlip wrote:

The topic we have all been avoiding:

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

Yes. Here is a benchmark program.

bool ex_top(int max_depth, int depth)
{
ex_middle(max_depth, depth + 1);
}

Doesn't gcc complain about the lack of a return?
The results:

chrono_bias = 0.000000400s

max_depth = 100
return_time = 0.000002000s
exception_time = 0.000009000s

max_depth = 200
return_time = 0.000003000s
exception_time = 0.000009400s

max_depth = 300
return_time = 0.000004900s
exception_time = 0.000009900s

max_depth = 400
return_time = 0.000006300s
exception_time = 0.000010000s

max_depth = 500
return_time = 0.000007700s
exception_time = 0.000010800s

max_depth = 600
return_time = 0.000009400s
exception_time = 0.000010500s

max_depth = 700
return_time = 0.000010900s
exception_time = 0.000011300s

max_depth = 800
return_time = 0.000012800s
exception_time = 0.000011100s

max_depth = 900
return_time = 0.000014200s
exception_time = 0.000011900s

max_depth = 1000
return_time = 0.000016400s
exception_time = 0.000012100s
As you can see, as the stack grows deeper, the exception mechanism
eventually becomes faster. The break-even point is somewhere at a depth
of about 700 to 800.

The results suggest that that exceptions have a high fixed cost on this
compiler, but a marginal additional cost to jump deeper.

OK, I'll bite:

Pentium M 2GHz, Solaris snv_b33, Sun Studio 11.

Built with -O2.

chrono_bias = 0.000000540s

max_depth = 100
return_time = 0.000001060s
exception_time = 0.000005960s

max_depth = 200
return_time = 0.000002060s
exception_time = 0.000011260s

max_depth = 300
return_time = 0.000002360s
exception_time = 0.000016460s

max_depth = 400
return_time = 0.000003960s
exception_time = 0.000022360s

max_depth = 500
return_time = 0.000004860s
exception_time = 0.000027460s

max_depth = 600
return_time = 0.000006060s
exception_time = 0.000033260s

max_depth = 700
return_time = 0.000007160s
exception_time = 0.000038560s

max_depth = 800
return_time = 0.000008360s
exception_time = 0.000043560s

max_depth = 900
return_time = 0.000009360s
exception_time = 0.000049660s

max_depth = 1000
return_time = 0.000010260s
exception_time = 0.000054660s

As you can see, with this compiler, exceptions are always slower.

--
Ian Collins.
Mar 31 '06 #34

P: n/a

Kaz Kylheku wrote:
Noah Roberts wrote:
Let's not take multiple samples of time and average them together.


5000 is not enough samples??!! I could do more but then I would have
to take the exception test out as it would take way too long.


5000 is the number times the function is called, not the number of
times the clock is sampled.

Calling the function isn't sampling. Reading the clock is sampling.


WTF are you talking about? You do it that way you DEFINATELY have to
account for all of the following and more:

All calls to timing functions.
All time spent outside the program (os premption)
All time restablishing program counters, etc...

Since each run takes less than your measurable clock there is no way to
account for any of them. No...you run multiple times and take the time
pre/post iterations and then average. Then all the little stuff is
insignificant.

You can't take an average of any unit that is smaller than your
smallest measure. Only after you take enough samples to add up to at
least one of your measuring units can you even think about it.

I'm surprised you passed your statistics class with your methodology.

I could run 5000 iterations several times and take an average and this
would be more accurate, but the variation would not alter results this
vastly different. It is simply not necissary to get that detailed. It
would be like taking several samples of a blade of grass and comparing
to several samples of full grown adult fir trees. You don't have to
sample more than one of each to know what the outcome will be.

Besides, I did run the tests several times to see if there was ever a
significant value change and there wasn't. Exceptions always take at
least 2000x longer on this arch/compiler....no amount of multi-sample
averaging will change that.

Mar 31 '06 #35

P: n/a
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.

Mar 31 '06 #36

P: n/a

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.

Mar 31 '06 #37

P: n/a
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!

Mar 31 '06 #38

P: n/a
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.
Apr 1 '06 #39

P: n/a

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....3fe58585dd209c

Apr 1 '06 #40

P: n/a
Phlip wrote:

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.


Java containers do this sort of thing, too. Writing a function that
calls various container members, some of which return error codes and
some of which throw exceptions, is a nightmare.

--

Pete Becker
Roundhouse Consulting, Ltd.
Apr 1 '06 #41

This discussion thread is closed

Replies have been disabled for this discussion.