[Haskell-cafe] Re: ANN: contstuff: CPS-based monad transformers
Ertugrul Soeylemez
es at ertes.de
Fri Oct 1 00:14:19 EDT 2010
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/
More information about the Haskell-Cafe
mailing list