Exceptions

[bjeremy]

Why are exceptions in C++ ~6x slower than exceptions in OCaml?

Not sure.. but I bet if we buy your online book you'll tell us why.

 

[Kai-Uwe Bux]

What in the word "exception" (like in "exceptional", ie. "occurring
rarely", "out of the ordinary") didn't you understand?

Where in the standard does it say that try-throw-catch has to be used with
exceptions? Technically, try-throw-catch is flow controll construct.
Nothing implies that it has to be slow. If it weren't for a certain coding
tradition among C++ folks, this flow construct might be used in C++ much
more frequently. Personally, I think it's a shame that unlike other
features of C++, try-throw-catch is not explored with the same open mind
like, say, templates. After all, with try-throw-catch you can put a jump
into a library and have the client provide the target location.

However, since we have a tradition of reserving try-throw-catch for
exceptions and another tradition of using exceptions by and large only for
error handling, compiler writers tend to heavily optimize the execution
path where nothing is thrown. None of this, however, is in any way
legislated or supported by the standard. It's just a tradition. Had
try-throw-catch been approached differently by the C++ community, current
compilers might have different optimizations.


Best

Kai-Uwe Bux

 

[kwikius]

No error has occurred. The exception is used to short-circuit a computation.

Why not just use a goto?

regards
Andy Little

 

[Alf P. Steinbach]

* kwikius:

Why not just use a goto?

Presumably he's doing a recursive descent of a tree, "simplifying" or
"optimizing" the code by using exceptions as success return values, like

struct Result
{
int value;
Result( int v ): value( v ) {}
};

void findOrX( Node* node, int x )
{
if( node == 0 ) { return; }
if( node->value == x ) { throw Result( node ); }
findOrX( node->left, x );
findOrX( node->right, x );
}

Node* find( Node* node, int x )
{
try
{
findOrX( node, x );
return 0;
}
catch( Result const& r )
{
return r.value;
}
}

An alternative design not using exceptions as success return values:

Node* find( Node* node, int x )
{
if( node == 0 || node->value == x ) { return node; }
Node* result;
(result = find( node->left )) || (result = find( node->right ));
return result;
}

Huh, shorter code, too! <g>

 

[kwikius]

Where in the standard does it say that try-throw-catch has to be used with
exceptions? Technically, try-throw-catch is flow controll construct.
Nothing implies that it has to be slow. If it weren't for a certain coding
tradition among C++ folks, this flow construct might be used in C++ much
more frequently.

The same can be said about goto, and it suffers from a similar problem
that overruse makes code difficult to understand and organise.

The fact that exceptions are restricted by policy to dealing with 'bad'
situations has resulted in compilers being optimised for that type of
use. C++ exception mechanism is already result in some perceived loss
in performance relative to C, (though in practise alternative error
handling strategies need to be used which also add overhead, but that
is a subtler argument which will make Trolls happily prove how much
faster C is).

Therefore I am happy to live with the current policy, that exceptions
provide the least possible overhead, unless actually invoked at which
point we can assume that something bad has occurred which has f*cked up
our application and needs to be dealt with, either in worst case by
aborting (ideally with some friendly feedback to the user first) or by
trying to return the application (if possible) to a useable state and
trying to deal with the source of the problem,often also requiring some
feedback/action from the user.

regards
Andy Little

 

[Jon Harrop]

Why not just use a goto?

Correctness first, safety second. Using a goto in this case would leak stack
because the exception is used to bail from a recursive function. The C
longjmp function can be used in this case, and it works well, but that
isn't idiomatic C++.

 

[Jon Harrop]

An alternative design not using exceptions as success return values:

Node* find( Node* node, int x )
{
if( node == 0 || node->value == x ) { return node; }
Node* result;
(result = find( node->left )) || (result = find( node->right ));
return result;
}

I tried both designs and this one is much faster because exceptions are so
slow in C++.

Huh, shorter code, too! <g>

In my case it was closer because the function was more complicated and there
were more recursive calls.

 

[kwikius]

An alternative design not using exceptions as success return values:

Node* find( Node* node, int x )
{
if( node == 0 || node->value == x ) { return node; }
Node* result;
(result = find( node->left )) || (result = find( node->right ));
return result;
}

Huh, shorter code, too! <g>

AFAICS its a redblack tree :

(recursion sucks too for any sort of performance ;-0)

namespace detail{
inline
Node * next_node(Node *node, int x)
{
return node->value > x
? node->left
: node->value < x
? node->right
: node;
}
}

Node* find(Node* node ,int x)
{
assert(node);
Node* current_node = node;
while((current_node = detail::next_node(node,x)) != node){
node = current_node;
}
return node;
}

regards
Andy Little

 

[kwikius]

AFAICS its a redblack tree :

(recursion sucks too for any sort of performance ;-0)

Hmm... This version works slightly better

namespace detail{
inline
Node * next_node(Node *node, int x)
{
return node?
(node->value > x
? node->left
: node->value < x
? node->right
: node)
:0;
}
}
// return null node on not found
Node* find(Node* node ,int x)
{
assert(node);
Node* current_node = node;
while((current_node = detail::next_node(node,x)) != node){
node = current_node;
}
return node;
}


regards
Andy Little

 

[Alf P. Steinbach]

* kwikius:

AFAICS its a redblack tree :

(recursion sucks too for any sort of performance ;-0)

namespace detail{
inline
Node * next_node(Node *node, int x)
{
return node->value > x
? node->left
: node->value < x
? node->right
: node;
}
}

Node* find(Node* node ,int x)
{
assert(node);
Node* current_node = node;
while((current_node = detail::next_node(node,x)) != node){
node = current_node;
}
return node;
}

Well, I didn't mean to illustrate search procedure, only exception
versus not in what I presumed to be Jon Harrop's recursive case. And I
didn't mean to illustrate performance. For that, a simple while loop,
no function calls, would suffice:

Node* find( Node* node, int x )
{
while( node != 0 && node->value != x )
{
node = (x < node->value? node->left : node->right);
}
return node;
}

Huh, shorter code, too! <g>

 

[Jon Harrop]

Well, I didn't mean to illustrate search procedure, only exception
versus not in what I presumed to be Jon Harrop's recursive case. And I
didn't mean to illustrate performance. For that, a simple while loop,
no function calls, would suffice:

Node* find( Node* node, int x )
{
while( node != 0 && node->value != x )
{
node = (x < node->value? node->left : node->right);
}
return node;
}

Huh, shorter code, too! <g>

My code was doing insertion and rebalancing rather than searching (which is
much easier, of course). I'm not sure that the O(log n) recursive calls
will have a significant impact on performance. I didn't time an iterative
version though...

 

[kwikius]

Correctness first, safety second. Using a goto in this case would leak stack
because the exception is used to bail from a recursive function. The C
longjmp function can be used in this case, and it works well, but that
isn't idiomatic C++.

We are a long way from idiomatic C++ AFAICS. runtime recursion isnt
much use for anything except toy code in C++ and nor are arbitrary
exceptions. Maybe you should be using another language...

regards
Andy Little

 

[kwikius]

Alf P. Steinbach wrote:

Huh, shorter code, too! <g>

OK... I think I'm going to retire from the low level coding contest...

std::map usually works for me

regards
Andy Little

 

[kwikius]

Node* find( Node* node, int x )
{
while( node != 0 && node->value != x )
{
node = (x < node->value? node->left : node->right);
}
return node;
}

Huh, shorter code, too! <g>

Oh and you win the contest I guess .. ;-)

regards
Andy Little

 

[Kai-Uwe Bux]

We are a long way from idiomatic C++ AFAICS. runtime recursion isnt
much use for anything except toy code in C++

Huh? Recursion is idiomatic in C++. As usual in imperative programming
languages, one can replace recursion by iteration for performance reasons.
However (as in other imperative languages) one would want to stay with
recursion whenever iterative solutions would require manual management of a
recursion stack. Thus, you will find recursion in divide-and-conquer
algorithms that need to recurse into more than one branch (such as
quick-sort or intro-sort). It is not so much a matter of whether you are
doing toy code as whether elimination of recursion is easy. If it isn't,
there is little to no gain in moving to an iterative solution.

and nor are arbitrary
exceptions. Maybe you should be using another language...

The OP did exactly that, which is what triggered the first post. His OCaml
version fared much better using exceptions.


Best

Kai-Uwe Bux

 

[kwikius]

Huh? Recursion is idiomatic in C++. As usual in imperative programming
languages, one can replace recursion by iteration for performance reasons.

I rest my case...

The OP did exactly that, which is what triggered the first post. His OCaml
version fared much better using exceptions.

Good for him. If I ever code in Occam I'll bear it in mind.

regards
Andy Little

 

[Kai-Uwe Bux]

I rest my case...

Wow, and that before you even made one.

Maybe, it's just because I am not a native speaker, but when did "idiomatic"
become to mean "optimized for performance"? And when did code written
trading performance for maintainability become synonymous with "toy" code?


Best

Kai-Uwe Bux

 

[kwikius]

Wow, and that before you even made one.

You just made it for me. ;-)

Maybe, it's just because I am not a native speaker, but when did "idiomatic"
become to mean "optimized for performance"?

FWIW the dictionary definition of idiomatic is "peculiar to or
charcteristic of a particular language". I guess you could say
recursion is idiomatic of some arbitrary FP language, but not C++

And when did code written
trading performance for maintainability become synonymous with "toy" code?

Op's whole thrust is regarding performance, so what does he do? Use
recursion and abuse exceptions.
I suspect he knew the answer to his question all along. Perhaps he'd
have more satisfaction on a functional newsgroup using his example to
demonstrate the superiority of FP language X over C++, which I am sure
he will be able to achieve in a totally unbiased way.

In C++ don't use recursion if you can help it IMO. Its far more
efficient in code space and time to use a loop. rationale: recursion
isnt idiomatic in C++.

regards
Andy Little

 

[Kai-Uwe Bux]

You just made it for me. ;-)

I see. In that case, you are very welcome

FWIW the dictionary definition of idiomatic is "peculiar to or
charcteristic of a particular language". I guess you could say
recursion is idiomatic of some arbitrary FP language, but not C++

That is interesting. It seems to imply that templates are the most idiomatic
part of C++ since I have seen just about any other feature of C++
elsewhere. On second thought, that does not even sound too unreasonable.

Op's whole thrust is regarding performance, so what does he do? Use
recursion and abuse exceptions.

True, in C++ one should not try to achieve optimum performance this way.

I suspect he knew the answer to his question all along. Perhaps he'd
have more satisfaction on a functional newsgroup using his example to
demonstrate the superiority of FP language X over C++, which I am sure
he will be able to achieve in a totally unbiased way.

I did not get the impression that the OP was acting in bad faith.

In C++ don't use recursion if you can help it IMO. Its far more
efficient in code space and time to use a loop. rationale: recursion
isnt idiomatic in C++.

Here, I would say, you have it just a little bit backwards: the rationale to
prefer iteration to recursion (in cases where it does not impair the
readability of the code) is that it boosts performance. Therefore,
iteration becomes the preferred solution for a wide range of algorithmic
problems and thus may be regarded more idiomatic.

Nonetheless, I still would code quick-sort and the likes of it using
recursion any day.


Best

Kai-Uwe Bux

 

[Rolf Magnus]

Only if they are slow.

Actually, it's the other way round.

In OCaml, exceptions are so fast that they are used extensively.

In C++, exceptions are supposed to be used only in exceptional cases.
Therefore, implementations typically use exception-handling mechanisms that
will have a very low or no overhead in the case no exception is thrown at
the expense of the overhead in case one is thrown.