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

[Jan-Willem Maessen]

On Mon, May 10, 2010 at 5:38 AM, Max Cantor <mxcantor at gmail.com> 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.
>

My suspicion, based on using a similar monad to implement IO in Eager
Haskell, is that you're creating a lot of closures.  This is rather more
expensive in general than the extra control flow required to inspect the
Eithers.

In more detail: CPS works well if the compiler can inline most of the
continuation passing and turn your code back into direct style, at least
along the "no failures" path.  In this case you can avoid creating closures
except at what would have been actual function call points in your original
code, and at catch points for the error continuation.  However, I expect
that you're probably calling functions that are polymorphic in Monad (stuff
like mapM etc.) that is not being inlined or specialized.  These end up
building a continuation rather naively on the heap.  You're essentially
moving the call stack to the heap, and the compiler can't assist you in
moving it back again; hence, slow code.

To make matters worse, you get a lot more branch prediction leverage with
pointer-tagged Either than you possibly could with a closure invocation on a
modern architecture.  But I suspect that's rather unimportant compared to
allocation time / memory footprint issues here.

-Jan-Willem Maessen


>
> 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.
>
> mkEMA and midError are basically toy functions but I dont know why Either
> is so much faster.  I've experimented with putting some seq's in the
> bindErrCPS and even {-# INLINE (>>=) #-} in the Monad instance, but to no
> avail.
>
> I've copy/pasted the code below, any suggestions on optimization, or if
> this is simply a bad idea would be much appreciated.  Strangely, compiling
> with -O2 seems to have no effect on the speed:
>
>
> -Max
> [... code snipped]
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100510/81f1bfd5/attachment.html