The ST Monad provides a venerable method in Haskell for writing stateful imperative code. Writing such code, in contrast to the non-stateful approach, is sometimes better. Some algorithms are better understood or better illustrated with states, and another reason is increased performance. The difference between
IO is important, because when we implement an algorithm, we only want to deal with the internal states and not bother with side effects that don’t belong to it. Allowing stateful algorithm to remain pure under
ST, gives way to better code generation by the compiler.
Some algorithms are better written with Exceptions. For example, an algorithm for validating an expression tree may be such one. However, one needs to be aware that exceptions in pure code can only be caught in
IO, unless pure exceptions are used. We can use these pure exceptions under a monad transformer, but then we need to verify that there was no significant loss in performance. We suspect that the
CatchT transformer would provide us a zero-cost abstraction, being a
newtype. But how well would GHC succeed in optimizing away the transformations?
Fibonacci that throws, for kicks
First, let us look at the example for
ST brought from the Haskell Wiki, which presents us with the stateful implementation of computing the n-th Fibonacci number:
We would like to test the performance of pure exceptions. So, let us have a slightly modified version of it, being a modulo of Fibonacci using
Int. The change of type from
Int would be better for us when measuring performance, otherwise the run would have spent time adding really big numbers in each one of the loop iterations.
We will use this new
… and modify the function in various ways:
- Have the caller use
- Change the type signature bear
Intand be under
- Add a throw to some exception along the way.
We have yet to add a
catch anywhere. The problem is that we cannot have a pure function in
catch :: (Exception e, MonadCatch m) => m a -> (e -> m a) -> m a. If we try to use
catch, we will get the error
No instance for (MonadCatch (ST s)).
To solve, we shall use the
ST monad with
CatchT. First, we define
STCatch type synonym for a short hand:
Now, let us create our
fibMod_E variant, which is under
STCatch, and modify it to use pure exceptions, thrown using
throwM. We will also add a
catch wrap, which will fix
fibMod_E to return
-1 on the thrown exception. The
catch is conditional, so we can see its effect depending on the use.
Can we degrade an
ST exception back to an
IO exception? Yes! Using the following function, that requires the
RankNTypes extension for its type signature:
Now we are ready for testing. We will use the following utility, depending on criterion:
We shall test with various recursion depths, on the two fuctions under discussion:
And the result is:
The first two results are of no surprise. Both the
catch incur their overheads. The last result is more peculiar, because it suggests that the code for
fibMod_E emanated from the compiler is even faster, despite of the
if, as long as there are no wrapping
catch’s in the evaluation. The difference probably boils down to the generated machine code, but I’d leave that to a topic of a different post.
A few extra tests
(edit: added March 2, 2016)
Edward Kmett pointed out on Reddit that perhaps it would be interesting to test with
unsafeSTToIO. So I’ve added the following cases (and also regenerated the results above, because every little change can affect the optimizer, and they varied slightly).
The additional output is:
For the first two cases the result are around 11% better than the pure
runST. Interestingly, for the third one
runSTthrowIO still wins.
An even more drastic approach is to use
unsafeSTToIO in conjunction, modifying the original
fibMod, allowing to freely insert the the less pure
catch while keeping it in
ST only from an API’s perspective. It’s not entirely sound in terms of exception handling, but it is worth presenting.
With the prints:
However, it does not improve on our cases:
The first two cases are considerably worse, and the third is still a bit better than using
STCatch, but it’s not representive of the common case where
catch is probably going to appear in the evaluation at least once. Final conclusion is that pure exceptions are still a win, if we wish to remain sound.