J
Jon Harrop
Why are exceptions in C++ ~6x slower than exceptions in OCaml?
A
Alf P. Steinbach
* Jon Harrop:
Languages are not fast or slow; implementations are.
Languages are not fast or slow; implementations are.
K
Kaz Kylheku
Jon said:
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?
J
Jon Harrop
Kaz said:
Only if they are slow. In OCaml, exceptions are so fast that they are used
extensively.
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...
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
Ian Collins
I'm sure you don't have to be reminded that in this universe you don'tJon said:
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.
G
Grizlyk
Jon said:
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?
K
kwikius
Jon said:
And what does the exception handler do?
regards
Andy Little
P
peter koch
Jon Harrop skrev:
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
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
P
peter koch
Jon Harrop skrev:
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]
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.
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
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]
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.
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
P
Pete Becker
Jon said:
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.
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.
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)
J
Jon Harrop
kwikius said:
Returns the original tree.
J
Jon Harrop
Ian said:
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...
J
Jon Harrop
peter said:
Exactly, I don't think they do so I can't see why exceptions slow this
program down so much...
Pointers in this case.
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
Ok.
K
kwikius
Jon said:
Does it provide any indication that an error has occurred?
regards
Andy Little
J
Jon Harrop
kwikius said:
No error has occurred. The exception is used to short-circuit a computation.
It is used as a more sanitary longjmp.
I
IR
Jon said:
Thus "other" languages use the heap for many more things than C++.
Which is slower in most cases.
QED?
Cheers,
P
Pete Becker
IR said:Thus "other" languages use the heap for many more things than C++.
Which is slower in most cases.
QED?
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)
I
IR
Pete said:
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,
J
Jon Harrop
IR said:Thus "other" languages use the heap for many more things than C++.
Which is slower in most cases.
QED?
Heap is slower, but not 6x slower!
I
IR
Jon said:
What in the word "exception" (like in "exceptional", ie. "occurring
rarely", "out of the ordinary") didn't you understand?
Cheers,