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

[Antoine Latter]

On Tue, May 11, 2010 at 8:28 PM, wren ng thornton <wren at freegeek.org> wrote:
> 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