[Haskell-cafe] Much faster complex monad stack based on CPS state

[Ryan Ingram]

My guess is that Cont plays really nicely with GHC's inliner, so things that
end up looking like

 return x >>= \y -> ...

get optimized really well

    return x >>= f
    -- inline >>=
    = ContState $ \s0 k -> runCS (return x) s0 $ \a s1 -> runCS (f a) s1 k
    -- inline return
    = ContState $ \s0 k -> runCS (ContState $ \s2 k2 -> k2 x s2) s0 $ \a s1
-> runCS (f a) s1 k
    -- runCS record selector
    = ContState $ \s0 k -> (\s2 k2 -> k2 x s2) s0 $ \a s1 -> runCS (f a) s1
k
    -- beta
    = ContState $ \s0 k -> (\k2 -> k2 x s0) $ \a s1 -> runCS (f a) s1 k
    -- beta
    = ContState $ \s0 k -> (\a s1 -> runCS (f a) s1 k) x s0
    -- beta
    = ContState $ \s0 k -> runCS (f x) s0 k

and then further inlining of f can take place.

On Mon, Sep 26, 2011 at 4:07 PM, Nicu Ionita <nicu.ionita at acons.at> wrote:

> Hello list,
>
> Starting from this emails (http://web.archiveorange.com/**
> archive/v/nDNOvSM4JT3GJRSjOm9P<http://web.archiveorange.com/archive/v/nDNOvSM4JT3GJRSjOm9P>
> **) I could refactor my code (a UCI chess engine, with complex functions,
> in which the search has a complex monad stack) to run twice as fast as with
> even some hand unroled state transformer! So from 23-24 kilo nodes per
> second it does now 45 to 50 kNps! And it looks like there is still some
> improvement room (I have to play a little bit with strictness annotations
> and so on).
>
> (Previously I tried specializations, then I removed a lot of polimorphism,
> but nothing helped, it was like hitting a wall.)
>
> Even more amazingly is that I could program it although I cannot really
> understand the Cont & ContT, but just taking the code example from Ryan
> Ingram (newtype ContState r s a = ...) and looking a bit at the code from
> ContT (from the transformers library), and after fixing some compilation
> errors, it worked and was so fast.
>
> I wonder why the transformers library does not use this kind of state monad
> definition. Or does it, and what I got is just because of the unrolling? Are
> there monad (transformers) libraries which are faster? I saw the library
> kan-extensions but I did not understand (yet) how to use it.
>
> Nicu
>
> ______________________________**_________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/**mailman/listinfo/haskell-cafe<http://www.haskell.org/mailman/listinfo/haskell-cafe>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110927/36411670/attachment-0001.htm>