Exceptions

[Jon Harrop]

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

--
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/product...ex.html?usenet

[Alf P. Steinbach]

* Jon Harrop:

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

Languages are not fast or slow; implementations are.

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

[Kaz Kylheku]

Jon Harrop wrote:

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

Remember that C++ exceptions are typically implemented in such a way
that they can transparently travel through frames that don't know
anything about exceptions, including frames set up by code that wasn't
necessarily even written in C++. It could be written in C and compiled
with a C compiler, or even written by hand in assembly language---as
long at follow the instruction set architecture's conventions with
regard to the stack. C++ code that does have any destructors to run,
and doesn't catch any exceptions can be also compiled as though
exceptions didn't exist, if things are implemented this way. But this
means that the exception handling search has to parse its way through
the machine's stack layout.

Would it be okay to slow down code that doesn't care about exceptions
by, say, 15% in order to speed up exceptions six fold? A lot of the
users of C++ would not want that trade off. Exceptions tend to be
regarded as rare events that occur in, well, exceptional circumstances.

Here is a consideration: Do OCaml exceptions have an ABI that non-OCaml
components running in the same image can use for interoperability?

Lastly, what compilers have you compared, anyway? How many compilers
are there for OCaml, and what kinds of things, in the area of
exceptions, did their writers consider important?

[Jon Harrop]

Kaz Kylheku wrote:

Would it be okay to slow down code that doesn't care about exceptions
by, say, 15% in order to speed up exceptions six fold? A lot of the
users of C++ would not want that trade off. Exceptions tend to be
regarded as rare events that occur in, well, exceptional circumstances.

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

Here is a consideration: Do OCaml exceptions have an ABI that non-OCaml
components running in the same image can use for interoperability?

OCaml can interface to C using a variety of macros from OCaml's library to
handle values and exceptions. I don't know how the exceptions are
implemented though.

Presumably garbage collection makes exceptions much faster, as C++ will have
to call all destructors in every scope that it unwinds past. In fact, C++
probably has to store such information in every stack frame, which might
explain why it has such big stack frames...

Lastly, what compilers have you compared, anyway? How many compilers
are there for OCaml, and what kinds of things, in the area of
exceptions, did their writers consider important?

Just one OCaml compiler and g++ 4. My main test was a balanced binary tree
set implementation. I tried using exceptions to bail when inserting an
already-present element, to return the original tree unaltered. In OCaml,
this was significantly more efficient and clearer than unwinding the stack
by hand. In C++, it is much slower.

--
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/product...ex.html?usenet

[Ian Collins]

Jon Harrop wrote:

>
Just one OCaml compiler and g++ 4. My main test was a balanced binary tree
set implementation. I tried using exceptions to bail when inserting an
already-present element, to return the original tree unaltered. In OCaml,
this was significantly more efficient and clearer than unwinding the stack
by hand. In C++, it is much slower.

I'm sure you don't have to be reminded that in this universe you don't
get something for nothing. At some point in anything other than a
trivial application you garbage collector is going to kick in and do its
stuff. At that point, you will pay the cost of destroying the objects
created on the stack.

--
Ian Collins.

[Grizlyk]

Jon Harrop wrote:

Kaz Kylheku wrote:

Would it be okay to slow down code that doesn't care about exceptions
by, say, 15% in order to speed up exceptions six fold? A lot of the
users of C++ would not want that trade off. Exceptions tend to be
regarded as rare events that occur in, well, exceptional circumstances.

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

Are you really write program as expecting exceptions? It is wrong
paradigm for C++ to use exception as return value or as representation
of concrete correct state. For example, error during remote transfer
over bad quality connection in most cases must not be treated as
exception.

The goal of exception using is safe termination (mostly) or restarting
separated part of program, if someting unexpected happends in it. In
most most cases does not matter time of exception execution if your
memory no longer exist.

In any case, what the trouble has C++ that results in slow exception
handling?

[kwikius]

Jon Harrop wrote:

I tried using exceptions to bail when inserting an
already-present element, to return the original tree unaltered.

And what does the exception handler do?

regards
Andy Little

[peter koch]

Jon Harrop skrev:

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

--
Dr Jon D Harrop, Flying Frog Consultancy

This answer can not be answered without you giving us information about
the compiler used. Different compilers use different ways to handle
exceptions, and each method has its trade-offs.
One thing to say about exceptions is that they are meant for
exceptional stuff: thus C++ users would prefer to have fast code when
exceptions are not thrown, rather than having a fast path when an
actual throw occurs. In another post you mention the usage of
exceptions for a fast return after a binary tree search. I would say
that for a generic tree, using throw in this situation is not a smart
design decision.

/Peter

[peter koch]

Jon Harrop skrev:

Kaz Kylheku wrote:

Would it be okay to slow down code that doesn't care about exceptions
by, say, 15% in order to speed up exceptions six fold? A lot of the
users of C++ would not want that trade off. Exceptions tend to be
regarded as rare events that occur in, well, exceptional circumstances.

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

Right. So we have an example where you use a style from one programming
language in another programming language. It should be no surprise that
such an approach has less than optimal performance.

[snip]

Presumably garbage collection makes exceptions much faster, as C++ will have
to call all destructors in every scope that it unwinds past. In fact, C++
probably has to store such information in every stack frame, which might
explain why it has such big stack frames...

It is correct that for objects with a non-trivial destructor, the
exception will have to be "caught" in order to release the ressources.
In the cases where the only resource involved is memory, C++ will have
to do more stops in order to clean up. But It still puzzles me if most
of your functions have such heavy objects: I believe most functions
would not contain such objects. Are you passing by value instead of be
reference? This could also explain your "big" stack frames.

>

Lastly, what compilers have you compared, anyway? How many compilers
are there for OCaml, and what kinds of things, in the area of
exceptions, did their writers consider important?

Just one OCaml compiler and g++ 4. My main test was a balanced binary tree
set implementation. I tried using exceptions to bail when inserting an
already-present element, to return the original tree unaltered. In OCaml,
this was significantly more efficient and clearer than unwinding the stack
by hand. In C++, it is much slower.

I have no personal experience with g++ 4, but believe it should be
quite good. So far as I know, g++ implements exception handling by
having an external table that links instruction pointer adress and
exception handling. This approach gives no overhead at all when you
follow the non-exceptional path, but a rather slow response whenever an
exception is thrown.

/Peter

[Pete Becker]

Jon Harrop wrote:

Kaz Kylheku wrote:

>Would it be okay to slow down code that doesn't care about exceptions
by, say, 15% in order to speed up exceptions six fold? A lot of the
users of C++ would not want that trade off. Exceptions tend to be
regarded as rare events that occur in, well, exceptional circumstances.

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

That's backwards. C++ exceptions were designed for use only in
exceptional circumstances, so programmers who understand the language
don't put a premium on speed there.

>Here is a consideration: Do OCaml exceptions have an ABI that non-OCaml
components running in the same image can use for interoperability?

OCaml can interface to C using a variety of macros from OCaml's library to
handle values and exceptions. I don't know how the exceptions are
implemented though.

Presumably garbage collection makes exceptions much faster, as C++ will have
to call all destructors in every scope that it unwinds past. In fact, C++
probably has to store such information in every stack frame, which might
explain why it has such big stack frames...

Wow, big stack frames! But this, too, is nonsense. There's nothing in
the C++ language definition that requires storing information about
destructors in stack frames, and I don't know of any compiler that does
that.

>Lastly, what compilers have you compared, anyway? How many compilers
are there for OCaml, and what kinds of things, in the area of
exceptions, did their writers consider important?

Just one OCaml compiler and g++ 4. My main test was a balanced binary tree
set implementation. I tried using exceptions to bail when inserting an
already-present element, to return the original tree unaltered. In OCaml,
this was significantly more efficient and clearer than unwinding the stack
by hand. In C++, it is much slower.

I don't doubt it. Bad designs tend to have poor performance. Using C++
exceptions as an alternate return mechanism is a bad design. That's not
what they're intended for.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

[Jon Harrop]

kwikius wrote:

Jon Harrop wrote:

>I tried using exceptions to bail when inserting an
already-present element, to return the original tree unaltered.

And what does the exception handler do?

Returns the original tree.

--
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/product...ex.html?usenet

[Jon Harrop]

Ian Collins wrote:

I'm sure you don't have to be reminded that in this universe you don't
get something for nothing. At some point in anything other than a
trivial application you garbage collector is going to kick in and do its
stuff. At that point, you will pay the cost of destroying the objects
created on the stack.

Yes. I don't know precisely where the time is spent but the version with GC
uses less memory and is faster. I used new for all allocations originally,
which I expected to be slow, but converting to using the STL allocators and
containers, it is still slow and also appears to leak memory...

--
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/product...ex.html?usenet

[Jon Harrop]

peter koch wrote:

Jon Harrop skrev:

>Only if they are slow. In OCaml, exceptions are so fast that they are
used extensively.

Right. So we have an example where you use a style from one programming
language in another programming language. It should be no surprise that
such an approach has less than optimal performance.

Yes.

>Presumably garbage collection makes exceptions much faster, as C++ will
have to call all destructors in every scope that it unwinds past. In
fact, C++ probably has to store such information in every stack frame,
which might explain why it has such big stack frames...

It is correct that for objects with a non-trivial destructor, the
exception will have to be "caught" in order to release the ressources.
In the cases where the only resource involved is memory, C++ will have
to do more stops in order to clean up. But It still puzzles me if most
of your functions have such heavy objects:

Exactly, I don't think they do so I can't see why exceptions slow this
program down so much...

I believe most functions
would not contain such objects. Are you passing by value instead of be
reference?

Pointers in this case.

This could also explain your "big" stack frames.

Well, C++ always seems to have big stack frames, it just uses the stack for
many more things than other languages.

Here's some of the code:

typedef const Node * Set;

Set E=0;
Set R(Set l, int n, Set r) { return new Node(true, l, n, r); }
Set B(Set l, int n, Set r) { return new Node(false, l, n, r); }

Set ins(const int x, Set p) {
if (!p) return R(E, x, E);
const int y = p->n;
if (p->is_red) {
if (x<y) {
Set l2=ins(x, p->l);
if (l2 == p->l) return p;
delete p->l;
return R(l2, y, p->r);
}
if (x>y) {
Set r2=ins(x, p->r);
if (r2 == p->r) return p;
delete p->r;
return R(p->l, y, r2);
}
}
else {
if (x<y) {
Set l2 = ins(x, p->l);
if (l2 == p->l) return p;
delete p->l;
if (l2->is_red && l2->l && l2->l->is_red)
return R(B(l2->l->l, l2->l->n, l2->l->r), l2->n, B(l2->r, y, p->r));
if (l2->is_red && l2->r && l2->r->is_red)
return R(B(l2->l, l2->n, l2->r->l), l2->r->n, B(l2->r->r, y, p->r));
return B(l2, y, p->r);
}
if (x>y) {
Set r2 = ins(x, p->r);
if (r2 == p->r) return p;
delete p->r;
if (r2->is_red && r2->l && r2->l->is_red)
return R(B(p->l, y, r2->l->l), r2->l->n, B(r2->l->r, r2->n, r2->r));
if (r2->is_red && r2->r && r2->r->is_red)
return R(B(p->l, y, r2->l), r2->n, B(r2->r->l, r2->r->n, r2->r->r));
return B(p->l, y, r2);
}
}
return p;
}

With an exception the code is slightly simpler but much slower:

Set ins(const int x, Set p) {
if (!p) return R(E, x, E);
const int y = p->n;
if (p->is_red) {
if (x < y) {
Set l2=ins(x, p->l);
delete p->l;
return R(l2, y, p->r);
}
if (x y) {
Set r2=ins(x, p->r);
delete p->r;
return R(p->l, y, r2);
}
}
else {
if (x < y) {
Set l2 = ins(x, p->l);
delete p->l;
if (l2->is_red && l2->l && l2->l->is_red)
return R(B(l2->l->l, l2->l->n, l2->l->r), l2->n, B(l2->r, y, p->r));
if (l2->is_red && l2->r && l2->r->is_red)
return R(B(l2->l, l2->n, l2->r->l), l2->r->n, B(l2->r->r, y, p->r));
return B(l2, y, p->r);
}
if (x y) {
Set r2 = ins(x, p->r);
delete p->r;
if (r2->is_red && r2->l && r2->l->is_red)
return R(B(p->l, y, r2->l->l), r2->l->n, B(r2->l->r, r2->n, r2->r));
if (r2->is_red && r2->r && r2->r->is_red)
return R(B(p->l, y, r2->l), r2->n, B(r2->r->l, r2->r->n, r2->r->r));
return B(p->l, y, r2);
}
}
throw Found();
}

Contrast with the OCaml:

let rec ins x = function
E -R(E, x, E)
| R(a, y, b) ->
if x < y then R(ins x a, y, b) else
if x y then R(a, y, ins x b) else raise Found
| B(a, y, b) ->
if x < y then match ins x a, y, b with
R(R(a, x, b), y, c), z, d -R(B(a, x, b), y, B(c, z, d))
| R(a, x, R(b, y, c)), z, d -R(B(a, x, b), y, B(c, z, d))
| a, x, b -B(a, x, b) else
if x y then match a, y, ins x b with
a, x, R(R(b, y, c), z, d) -R(B(a, x, b), y, B(c, z, d))
| a, x, R(b, y, R(c, z, d)) -R(B(a, x, b), y, B(c, z, d))
| a, x, b -B(a, x, b) else raise Found

let add x s =
try match ins x s with
R(a, y, b) -B(a, y, b)
| s -s
with Found -s

>Just one OCaml compiler and g++ 4. My main test was a balanced binary
tree set implementation. I tried using exceptions to bail when inserting
an already-present element, to return the original tree unaltered. In
OCaml, this was significantly more efficient and clearer than unwinding
the stack by hand. In C++, it is much slower.

I have no personal experience with g++ 4, but believe it should be
quite good. So far as I know, g++ implements exception handling by
having an external table that links instruction pointer adress and
exception handling. This approach gives no overhead at all when you
follow the non-exceptional path, but a rather slow response whenever an
exception is thrown.

Ok.

--
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/product...ex.html?usenet

[kwikius]

Jon Harrop wrote:

kwikius wrote:

Jon Harrop wrote:

I tried using exceptions to bail when inserting an
already-present element, to return the original tree unaltered.

And what does the exception handler do?

Returns the original tree.

Does it provide any indication that an error has occurred?

regards
Andy Little

[Jon Harrop]

kwikius wrote:

Does it provide any indication that an error has occurred?

No error has occurred. The exception is used to short-circuit a computation.
It is used as a more sanitary longjmp.

--
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/product...ex.html?usenet

[IR]

Jon Harrop wrote:

Well, C++ always seems to have big stack frames, it just uses the
stack for many more things than other languages.

Thus "other" languages use the heap for many more things than C++.
Which is slower in most cases.

QED? :-p
Cheers,
--
IR

[Pete Becker]

IR wrote:

Jon Harrop wrote:

>Well, C++ always seems to have big stack frames, it just uses the
stack for many more things than other languages.

Thus "other" languages use the heap for many more things than C++.
Which is slower in most cases.

QED? :-p

No, no, no. You're missing the point. C++ is bad. So criticisms should
always be vague and scary, never objective.

This reminds me of the olden days, when the opening paragraph of every
article about Java was a cheap shot at C++. You had to read the second
paragraph to find out what the article was actually about. I especially
liked the claim (in an article in "The Java Report") that C++ can't have
garbage collection because it doesn't run in a virtual machine. So many
errors in so few words.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

[IR]

Pete Becker wrote:

IR wrote:

>Jon Harrop wrote:

>>Well, C++ always seems to have big stack frames, it just uses
the stack for many more things than other languages.

Thus "other" languages use the heap for many more things than
C++. Which is slower in most cases.

QED? :-p

No, no, no. You're missing the point. C++ is bad. So criticisms
should always be vague and scary, never objective.

I do agree with you. C++ is the root of all evil. The best proof is
that even after more than 10 years using it, I am still able to
write buggy code if I want to (and even sometimes if I don't want!).
What a shame...

However, I see nothing in your sentence that forbids me to counter
such subjective and vague criticisms with an argument which is
almost as subjective and misinformed as Jon's...

;-)
Cheers,
--
IR

[Jon Harrop]

IR wrote:

Jon Harrop wrote:

>Well, C++ always seems to have big stack frames, it just uses the
stack for many more things than other languages.

Thus "other" languages use the heap for many more things than C++.
Which is slower in most cases.

QED? :-p

Heap is slower, but not 6x slower!

--
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/product...ex.html?usenet

[IR]

Jon Harrop wrote:

IR wrote:

>Jon Harrop wrote:

>>Well, C++ always seems to have big stack frames, it just uses the
stack for many more things than other languages.

Thus "other" languages use the heap for many more things than C++.
Which is slower in most cases.

QED? :-p

Heap is slower, but not 6x slower!

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

[bjeremy]

Jon Harrop wrote:

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

--
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/product...ex.html?usenet

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

[Kai-Uwe Bux]

IR wrote:

Jon Harrop wrote:

>IR wrote:

>>Jon Harrop wrote:
Well, C++ always seems to have big stack frames, it just uses the
stack for many more things than other languages.

Thus "other" languages use the heap for many more things than C++.
Which is slower in most cases.

QED? :-p

Heap is slower, but not 6x slower!

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]

Jon Harrop wrote:

kwikius wrote:

Does it provide any indication that an error has occurred?

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:

Jon Harrop wrote:

>kwikius wrote:

>>Does it provide any indication that an error has occurred?

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

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>

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

[kwikius]

Kai-Uwe Bux wrote:

IR wrote:

Jon Harrop wrote:

IR wrote:
Jon Harrop wrote:
Well, C++ always seems to have big stack frames, it just uses the
stack for many more things than other languages.

Thus "other" languages use the heap for many more things than C++.
Which is slower in most cases.

QED? :-p

Heap is slower, but not 6x slower!

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.

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]

kwikius wrote:

Jon Harrop wrote:

>kwikius wrote:

Does it provide any indication that an error has occurred?

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

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

--
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/product...ex.html?usenet

[Jon Harrop]

Alf P. Steinbach wrote:

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.

--
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/product...ex.html?usenet

[kwikius]

Alf P. Steinbach wrote:

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]

kwikius wrote:

Alf P. Steinbach wrote:

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)

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:

Alf P. Steinbach wrote:

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

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>

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

[kwikius]

Jon Harrop wrote:

kwikius wrote:

Jon Harrop wrote:

kwikius wrote:
Does it provide any indication that an error has occurred?

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

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

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

[Jon Harrop]

Alf P. Steinbach wrote:

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

--
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/product...ex.html?usenet

[kwikius]

Alf P. Steinbach wrote:

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

kwikius wrote:

>
Jon Harrop wrote:

>kwikius wrote:

Jon Harrop wrote:
kwikius wrote:
Does it provide any indication that an error has occurred?

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

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

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]

Kai-Uwe Bux wrote:

kwikius wrote:

Jon Harrop wrote:

kwikius wrote:
Jon Harrop wrote:
kwikius wrote:
Does it provide any indication that an error has occurred?

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

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

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.

I rest my case...

<...>

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.

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

regards
Andy Little

[Kai-Uwe Bux]

kwikius wrote:

>
Kai-Uwe Bux wrote:

>kwikius wrote:

>
Jon Harrop wrote:
kwikius wrote:
Jon Harrop wrote:
kwikius wrote:
Does it provide any indication that an error has occurred?

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

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

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.

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]

Kai-Uwe Bux wrote:

kwikius wrote:

Kai-Uwe Bux wrote:

kwikius wrote:


Jon Harrop wrote:
kwikius wrote:
Jon Harrop wrote:
kwikius wrote:
Does it provide any indication that an error has occurred?

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

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

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.

I rest my case...

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]

kwikius wrote:

>
Kai-Uwe Bux wrote:

>kwikius wrote:

>
Kai-Uwe Bux wrote:
kwikius wrote:
Jon Harrop wrote:
kwikius wrote:
Jon Harrop wrote:
kwikius wrote:
Does it provide any indication that an error has occurred?

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

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

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.

I rest my case...

Wow, and that before you even made one.

You just made it for me. ;-)

I see. In that case, you are very welcome :-)

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

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.

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

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]

Jon Harrop wrote:

>users of C++ would not want that trade off. Exceptions tend to be
regarded as rare events that occur in, well, exceptional circumstances.

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.

[Pete Becker]

kwikius wrote:

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

Um, not according to my dictionary: "using, containing, or denoting
expressions that are natural to a native speaker."

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

[Jon Harrop]

kwikius wrote:

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.

Note that there is still no evidence of that in this case.

--
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/product...ex.html?usenet

[kwikius]

Jon Harrop wrote:

kwikius wrote:

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.

Note that there is still no evidence of that in this case.

Correction to the above. I meant data space rather than code space.
Apologies.

regards
Andy Little