caml-list - the Caml user's mailing list
 help / color / mirror / Atom feed
* The performance cost of using exceptions?
@ 2000-05-13 21:59 Daniel Ortmann
  2000-05-15  7:31 ` Markus Mottl
  2000-05-16  9:55 ` Xavier Leroy
  0 siblings, 2 replies; 9+ messages in thread
From: Daniel Ortmann @ 2000-05-13 21:59 UTC (permalink / raw)
  To: caml-list

Are programs written to make heavy use of exceptions going to be markedly
slower than programs written more traditionally with loops/ifs, etc?

(My uninformed mental picture of exception is that they would use some type of
underlying setjump/longjump overhead.)

Thanks in advance to anyone who replies.

-- 
Daniel Ortmann, IBM Circuit Technology, Rochester, MN 55901-7829
ortmann@vnet.ibm.com or ortmann@us.ibm.com and 507.253.6795 (external)
ortmann@rchland.ibm.com and tieline 8.553.6795 (internal)
ortmann@isl.net and 507.288.7732 (home)

"The answers are so simple, and we all know where to look,
but it's easier just to avoid the question." -- Kansas



^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: The performance cost of using exceptions?
  2000-05-13 21:59 The performance cost of using exceptions? Daniel Ortmann
@ 2000-05-15  7:31 ` Markus Mottl
  2000-05-16  9:30   ` Frank Atanassow
  2000-05-16  9:55 ` Xavier Leroy
  1 sibling, 1 reply; 9+ messages in thread
From: Markus Mottl @ 2000-05-15  7:31 UTC (permalink / raw)
  To: ortmann; +Cc: OCAML

> Are programs written to make heavy use of exceptions going to be markedly
> slower than programs written more traditionally with loops/ifs, etc?

That depends on how you use them. It is well possible to do this in such a
way that you actually increase performance.

For example, when inserting elements into a binary tree, the naive version
always copies the "spine" of the tree, even if the element is already a
member.

But if you use exceptions, you can "jump back" and can thus prevent the
spine from being copied. This normally reduces the load of the garbage
collector and yields some percent more performance.

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl



^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: The performance cost of using exceptions?
  2000-05-15  7:31 ` Markus Mottl
@ 2000-05-16  9:30   ` Frank Atanassow
  2000-05-16 13:45     ` Markus Mottl
  2000-05-16 15:04     ` Pierpaolo Bernardi
  0 siblings, 2 replies; 9+ messages in thread
From: Frank Atanassow @ 2000-05-16  9:30 UTC (permalink / raw)
  To: Markus Mottl; +Cc: OCAML

Markus Mottl writes:
 > > Are programs written to make heavy use of exceptions going to be markedly
 > > slower than programs written more traditionally with loops/ifs, etc?
 > 
 > That depends on how you use them. It is well possible to do this in such a
 > way that you actually increase performance.
 > 
 > For example, when inserting elements into a binary tree, the naive version
 > always copies the "spine" of the tree, even if the element is already a
 > member.
 > 
 > But if you use exceptions, you can "jump back" and can thus prevent the
 > spine from being copied. This normally reduces the load of the garbage
 > collector and yields some percent more performance.

I don't see how this would improve performance. If the element is in the tree,
you will be copying the spine until you descend to a point where you discover
the node exists. If you then escape via an exception, the copied nodes will be
collected. Otherwise (but it depends on your specification, I suppose) the
functional way would be to just return the subtree(s) intact, so there would
be no need to copy their spines. Either way, you're generating the same amount
of garbage.

-- 
Frank Atanassow, Dept. of Computer Science, Utrecht University
Padualaan 14, PO Box 80.089, 3508 TB Utrecht, Netherlands
Tel +31 (030) 253-1012, Fax +31 (030) 251-3791



^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: The performance cost of using exceptions?
  2000-05-13 21:59 The performance cost of using exceptions? Daniel Ortmann
  2000-05-15  7:31 ` Markus Mottl
@ 2000-05-16  9:55 ` Xavier Leroy
  1 sibling, 0 replies; 9+ messages in thread
From: Xavier Leroy @ 2000-05-16  9:55 UTC (permalink / raw)
  To: Daniel Ortmann, caml-list

> Are programs written to make heavy use of exceptions going to be markedly
> slower than programs written more traditionally with loops/ifs, etc?
> (My uninformed mental picture of exception is that they would use
> some type of underlying setjump/longjump overhead.)

The OCaml compiler "knows" about exceptions, so it can implement them
more efficiently than setjmp/longjmp.  Namely, there is no need to
save registers to install an exception handler and to restore them
when raising an exception.

As rought approximations, I would say that raising an exception costs
no more than, say, two calls to unknown functions, and installing an
exception handler costs no more than one such call.

- Xavier Leroy



^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: The performance cost of using exceptions?
  2000-05-16  9:30   ` Frank Atanassow
@ 2000-05-16 13:45     ` Markus Mottl
  2000-05-16 15:04     ` Pierpaolo Bernardi
  1 sibling, 0 replies; 9+ messages in thread
From: Markus Mottl @ 2000-05-16 13:45 UTC (permalink / raw)
  To: Frank Atanassow; +Cc: OCAML

> I don't see how this would improve performance. If the element is in the tree,
> you will be copying the spine until you descend to a point where you discover
> the node exists. If you then escape via an exception, the copied nodes will be
> collected. Otherwise (but it depends on your specification, I suppose) the
> functional way would be to just return the subtree(s) intact, so there would
> be no need to copy their spines. Either way, you're generating the same amount
> of garbage.

The spine will not be generated until the insertion into the subtree
finishes. Only the runtime stack will grow (in any case). You can always
prevent spine copying by testing for physical equality on substructures,
but this requires at least one check for each node whereas exceptions need
not check - they just unwind the stack.

Setting up the exception handler costs a bit time (one time effort!) so
inserting an element into very small datastructures could be costly. But
performance normally depends on inserting elements into big datastructures,
in which case exceptions really excel. The break-even point is surely
highly dependent on the quality of the exception handling mechanism. In my
tests it was somewhere around inserting 100 elements (test function below)
into an unbalanced binary tree.

Let's assume the following test function:

  let test f empty n =
    let s = ref empty in
    for i = 1 to n do s := f (Random.int (n/10)) !s done

It just inserts n random integers in the range of 0..n/10 into some
datastructure.

Take the following straightforward insertion function for binary trees:

  let rec insert1 x = function
    | `Nil -> `Node (`Nil, x, `Nil)
    | `Node(l, el, r) as node ->
        let c = compare x el in
        if c = 0 then node
        else if c < 0 then `Node (insert1 x l, el, r)
        else `Node (l, el, insert1 x r)

Timing for running it with "test insert1 `Nil 100000":

  3.040u 0.040s 0:03.07 100.3%    0+0k 0+0io 133pf+0w

Now the version with exceptions (use insert2 with the test function):

  let rec insert2 x = function
    | `Nil -> `Node (`Nil, x, `Nil)
    | `Node(l, el, r) ->
        let c = compare x el in
        if c = 0 then raise Exit
        else if c < 0 then `Node (insert2 x l, el, r)
        else `Node (l, el, insert2 x r)
  let insert2 x s = try insert2 x s with Exit -> s

Timing:

  1.950u 0.010s 0:01.95 100.5%    0+0k 0+0io 138pf+0w

Wow! That's much faster!

But not really fair... - the first function copies the spine, the second
does not. So let's make a fairer comparison:

  let rec insert3 x = function
    | `Nil -> `Node (`Nil, x, `Nil)
    | `Node (l, el, r) as node ->
        let c = compare x el in
        if c = 0 then node
        else if c < 0 then
          let l' = insert3 x l in
          if l == l' then node
          else `Node (l', el, r)
        else
          let r' = insert3 x r in
          if r == r' then node
          else `Node (l, el, r')

This does not use exceptions, but checks for physical equality to prevent
spine copying. Timing:

  2.070u 0.000s 0:02.07 100.0%    0+0k 0+0io 133pf+0w

Not bad! That's already much faster than the first version, though, not
quite as good as the version using exceptions. Could be fine for small
datastructures!

But wait, we can even further improve the speed of the version that uses
exceptions: the idea is that we do not do the recursive call within the
constructor parameter but outside! This is possibly a tweak that only works
with specific compilers. It seems that the OCaml-compiler makes
arrangements to allocate the constructor in the upper version, which costs
time: if an exception occurs, this effort is wasted.

Here the fastest version with exceptions:

  let rec insert4 x = function
    | `Nil -> `Node (`Nil, x, `Nil)
    | `Node (l, el, r) ->
        let c = compare x el in
        if c = 0 then raise Exit
        else if c < 0 then
          let l' = insert4 x l in
          `Node (l', el, r)
        else
          let r' = insert4 x r in
          `Node (l, el, r')
  let insert4 x s = try insert4 x s with Exit -> s

Timing:

  1.880u 0.030s 0:01.90 100.5%    0+0k 0+0io 139pf+0w

Well, another 2-3%... - not overwhelming, but we don't want to give it away
either...

As we could see, we can gain quite some performance by making clever use of
exceptions. This also suggests that the implementation of sets in the
standard library be revised: the current one not only copies the spine, it
also unnecessarily calls the balance function each time!

The fastest insertion implementation for our standard sets (balanced binary
trees - see "set.ml" in the standard library) given the test function above
is:

  let rec my_add1 x = function
    | Empty -> Node(Empty, x, Empty, 1)
    | Node(l, v, r, _) ->
        let c = Ord.compare x v in
        if c = 0 then raise Exit
        else if c < 0 then
          let l' = my_add1 x l in
          bal l' v r
        else
          let r' = my_add1 x r in
          bal l v r'
  let my_add1 x s = try my_add1 x s with Exit -> s

As I mentioned, this version with exceptions might come with a slight
penalty for tiny sets. But at least the spine copying and redundant balance
call should be eliminated: this nearly doubles the speed on the above test
(and even more for more data)!

Here the version without exceptions but with test for physical equality:

  let rec my_add2 x = function
    | Empty -> Node(Empty, x, Empty, 1)
    | Node(l, v, r, _) as t ->
        let c = Ord.compare x v in
        if c = 0 then t else
        if c < 0 then
          let l' = my_add2 x l in
          if l == l' then t
          else bal l' v r
        else
          let r' = my_add2 x r in
          if r == r' then t
          else bal l v r'

Well, that's probably enough now about tweaking algorithms with
exceptions...

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl




^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: The performance cost of using exceptions?
  2000-05-16  9:30   ` Frank Atanassow
  2000-05-16 13:45     ` Markus Mottl
@ 2000-05-16 15:04     ` Pierpaolo Bernardi
  2000-05-16 16:11       ` Jean-Francois Monin
  1 sibling, 1 reply; 9+ messages in thread
From: Pierpaolo Bernardi @ 2000-05-16 15:04 UTC (permalink / raw)
  To: Frank Atanassow; +Cc: Markus Mottl, OCAML, Pierre.Weis, caml-redist


On Tue, 16 May 2000, Frank Atanassow wrote:
> Markus Mottl writes:

>  > But if you use exceptions, you can "jump back" and can thus prevent the
>  > spine from being copied. This normally reduces the load of the garbage
>  > collector and yields some percent more performance.
> 
> I don't see how this would improve performance. If the element is in the tree,
> you will be copying the spine until you descend to a point where you discover
> the node exists. 

Usually, that is, in the most straightforward implementation, you rebuild
the path on the way up.  By throwing the exception, you don't cons any new
node.

> If you then escape via an exception, the copied nodes will be
> collected. Otherwise (but it depends on your specification, I suppose) the
> functional way would be to just return the subtree(s) intact, so there would
> be no need to copy their spines. Either way, you're generating the same amount
> of garbage.

For this to work, you should either have a low-level pointer equality
operator (present in OCaml, but not in other func. languages), or you
must return a flag to signal whether the returned tree is unchanged.
Both variants are ugly and cumbersome, IMO.


Gxis,
  Pierpaolo




^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: The performance cost of using exceptions?
  2000-05-16 15:04     ` Pierpaolo Bernardi
@ 2000-05-16 16:11       ` Jean-Francois Monin
  0 siblings, 0 replies; 9+ messages in thread
From: Jean-Francois Monin @ 2000-05-16 16:11 UTC (permalink / raw)
  To: Pierpaolo Bernardi
  Cc: Frank Atanassow, Markus Mottl, OCAML, Pierre.Weis, caml-redist

> From: Pierpaolo Bernardi <bernardp@cli.di.unipi.it>
> 
> Usually, that is, in the most straightforward implementation, you rebuild
> the path on the way up.  By throwing the exception, you don't cons any new
> node.
> [...]
> For this to work, you should either have a low-level pointer equality
> operator (present in OCaml, but not in other func. languages), or you
> must return a flag to signal whether the returned tree is unchanged.
> Both variants are ugly and cumbersome, IMO.

This theme was discussed last year under a thread called
 "List.filter in Ocaml 2.02"

-- 
Jean-Francois Monin, CNET DTL/MSV,          Tel +33 2 96 05 26 79
2 av. Pierre Marzin, 22307 Lannion, France  Fax +33 2 96 05 39 45
 NEW                       JeanFrancois.Monin@francetelecom.fr





^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: The performance cost of using exceptions?
  2000-05-16 16:02 Dave Berry
@ 2000-05-16 17:13 ` Markus Mottl
  0 siblings, 0 replies; 9+ messages in thread
From: Markus Mottl @ 2000-05-16 17:13 UTC (permalink / raw)
  To: Dave Berry; +Cc: OCAML

> How about having a compiler that detects this pattern and emits the
> necessary pointer comparisons?  Then you could write your code cleanly
> (without exceptions, flags or comparisons), and the compiler can emit
> whatever code is most efficient for its runtime.

One could surely do this, especially if the compiler "sees" that only one
or a few arguments of a constructor change: then checking for physical
identity would allow it to return the "original" value.

But I am not sure whether this is generally a good idea, because the
compiler cannot predict runtime behaviour: it may well be that you use sets
without ever inserting already existing elements into them. Then all these
checks are superfluous.

The good thing about the version with exceptions is that you do not need
the checks for physical equality anymore, which quickly pays with
increasing data amounts and is not really so "unclean".

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl




^ permalink raw reply	[flat|nested] 9+ messages in thread

* RE: The performance cost of using exceptions?
@ 2000-05-16 16:02 Dave Berry
  2000-05-16 17:13 ` Markus Mottl
  0 siblings, 1 reply; 9+ messages in thread
From: Dave Berry @ 2000-05-16 16:02 UTC (permalink / raw)
  To: Pierpaolo Bernardi, Frank Atanassow
  Cc: Markus Mottl, OCAML, Pierre.Weis, caml-redist

How about having a compiler that detects this pattern and emits the
necessary pointer comparisons?  Then you could write your code cleanly
(without exceptions, flags or comparisons), and the compiler can emit
whatever code is most efficient for its runtime.

Dave.


On Tue, 16 May 2000, Frank Atanassow wrote:
> Markus Mottl writes:
> the functional way would be to just return the subtree(s) intact, so there
would
> be no need to copy their spines.

For this to work, you should either have a low-level pointer equality
operator (present in OCaml, but not in other func. languages), or you
must return a flag to signal whether the returned tree is unchanged.



^ permalink raw reply	[flat|nested] 9+ messages in thread

end of thread, other threads:[~2000-05-17 17:28 UTC | newest]

Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2000-05-13 21:59 The performance cost of using exceptions? Daniel Ortmann
2000-05-15  7:31 ` Markus Mottl
2000-05-16  9:30   ` Frank Atanassow
2000-05-16 13:45     ` Markus Mottl
2000-05-16 15:04     ` Pierpaolo Bernardi
2000-05-16 16:11       ` Jean-Francois Monin
2000-05-16  9:55 ` Xavier Leroy
2000-05-16 16:02 Dave Berry
2000-05-16 17:13 ` Markus Mottl

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).