[Haskell-cafe] Speed of Error handling with Continuations vs. Eithers

[wren ng thornton]

Max Cantor wrote:
> Based on some discussions in #haskell, it seemed to be a consensus
> that using a modified continuation monad for Error handling instead
> of Eithers would be a significant optimization since it would
> eliminate a lot of conditional branching (everytime >>= is called
> in the Either monad, there is a conditional.  
> 
> I implemented a ErrCPS monad which does exactly that, but the speed
> has been disappointing.  It runs almost exactly 3x slower than a
> drop in replacement using the MonadError instance of Either from mtl.


I have noticed speedup in my CPS version of Maybe[1] (kidnapped from the 
Wiki) so the difference is curious. Jan-Willem's comments about closures 
are significant when doing CPS work, but I'd expect Maybe and Either to 
perform similarly, whatever their performance is. It's been a while 
since I've benchmarked MaybeCPS, so perhaps I now have the slowdown too. 
Let's look at the code and see if we can find other differences...

[1] 
http://community.haskell.org/~wren/wren-extras/src/Control/Monad/MaybeCPS.hs


Here's one big difference:

>> newtype ErrCPS e m a = ErrCPS { runErrCPS ::
>>     forall r . (e -> m r) --  error handler
>>     -> (a -> m r) --  success handler
>>     -> m r }

The analogous version I use is:

     newtype MaybeCPS a = MaybeCPS
         (forall r. (a -> Maybe r) -> Maybe r)

While I also offer a transformer version of MaybeCPS, the transformer 
*does* suffer from significant slowdown. Also, for MaybeCPS it's better 
to leave the handlers inline in client code rather than to abstract them 
out; that helps to keep things concrete. So perhaps you should first try 
a direct CPS translation:

     newtype ErrCPS e a = ErrCPS
         (forall r. (a -> Either e r) -> Either e r)

     runErrCPS :: ErrCPS e a -> Either e a
     runErrCPS (ErrCPS f) = f return

I'd be curious if this version suffers the same slowdown.

-- 
Live well,
~wren