RE: The performance cost of using exceptions?

RE: The performance cost of using exceptions?

[Dave Berry]

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.

Re: The performance cost of using exceptions?

[Markus Mottl]

> 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

Re: The performance cost of using exceptions?

[Jean-Francois Monin]

> 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

Re: The performance cost of using exceptions?

[Pierpaolo Bernardi]

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

Re: The performance cost of using exceptions?

[Markus Mottl]

> 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

Re: The performance cost of using exceptions?

[Xavier Leroy]

> 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

Re: The performance cost of using exceptions?

[Frank Atanassow]

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

Re: The performance cost of using exceptions?

[Markus Mottl]

> 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

The performance cost of using exceptions?

[Daniel Ortmann]

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