On Tue, May 11, 2010 at 8:28 PM, 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:
Is the CPS transformed MaybeT slower because it's done in 2-CPS, rather than in 1-CPS like the MaybeCPS? I only did MaybeT in 2-CPS because it was the easiest, not because I thought it would be easiest. Antoine