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

[Max Cantor]

Makes sense.  From what you wrote, it seems like this might be a dead-end and can't really be optimized away.  Do you agree?

Max

On May 10, 2010, at 8:38 PM, Jan-Willem Maessen wrote:

> 
> 
> 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]