[Haskell-cafe] Re: ANN: contstuff: CPS-based monad transformers

[Ertugrul Soeylemez]

Felipe Lessa <felipe.lessa at gmail.com> wrote:

> Very interesting!  And the API seems very nice, although I haven't
> used the package.
>
> Are there benchmarks for monad transformers?  How big is the
> difference between CPS and non-CPS monad libraries?

I have run some small and probably not that meaningful benchmarks.  For
StateT it doesn't seem to make a lot of difference.  ChoiceT appears to
be considerably faster than [] in all tests I've made.

As a small benchmark consider the following factoring functions, which
return a (very redundant) list of factors of the argument:

  testComp1 :: Integral a => a -> [a]
  testComp1 n = do
    x <- [1..n]
    y <- [x+1..n]
    guard $ n - x /= y
    guard $ mod (x^2 - y^2) n == 0
    return $ gcd n (x-y)

  testComp2 :: Integral a => a -> ChoiceT r i m a
  testComp2 n = do
    x <- choice [1..n]
    y <- choice [x+1..n]
    guard $ n - x /= y
    guard $ mod (x^2 - y^2) n == 0
    return $ gcd n (x-y)

On my machine testComp1 takes 5.6 seconds to finish, and testComp2 takes
3.9 seconds.  The programs I've used to test are:

  main1, main2 :: IO ()

  main1 = do
    hSetBuffering stdout (BlockBuffering Nothing)
    getArgs >>= mapM_ (print . testComp1 . read)

  main2 = do
    hSetBuffering stdout (BlockBuffering Nothing)
    getArgs >>= mapM_ (print . listChoice . testComp2 . read)

To take this further I modified the benchmark to print only the first
result found.  To return a factor of 1237*65537 testComp1 needs 10.2
seconds, while testComp2 needs only 5.1 seconds.  Here is the modified
code (testComp1 and testComp2 remain unchanged):

  main1, main2 :: IO ()

  main1 = getArgs >>= mapM_ (print . head . testComp1 . read)
  main2 = getArgs >>= mapM_ (print . maybeChoice . testComp2 . read)

At least ChoiceT is faster than using regular lists, and it's also a
CPS-based monad transformer, so you get all the goodies of CPS and
combining monads:

  testComp3 :: (Integral a, Monad m, LiftBase m, Base m ~ IO) =>
               a -> ChoiceT r i m a
  testComp3 n = do
    x <- choice [1..n]
    y <- choice [x+1..n]
    guard $ n - x /= y
    guard $ mod (x^2 - y^2) n == 0
    let factor = gcd n (x-y)
    io $ printf "Factor found: %i\n" (toInteger factor)
    return factor

Note that instead of 'listA' I'm using the 'choice' function, which is
slightly faster, but even with 'listA' ChoiceT outperforms regular
lists.


Greets,
Ertugrul


-- 
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/