Re: The performance cost of using exceptions?

From: Markus Mottl (mottl@miss.wu-wien.ac.at)
Date: Tue May 16 2000 - 15:45:27 MET DST

  • Next message: Markus Mottl: "Re: The performance cost of using exceptions?"

    > 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
    



    This archive was generated by hypermail 2b29 : Wed May 17 2000 - 19:33:56 MET DST