Re: The performance cost of using exceptions?
 Markus Mottl
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Markus Mottl <mottl@m...> 
Subject:  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 breakeven 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 OCamlcompiler 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 23%...  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.wuwien.ac.at, http://miss.wuwien.ac.at/~mottl