monad变压器基准的奇怪结果.一个bug？

Question

我做了一些Criterion基准测试,通过在monad堆栈上运行我的代码来估计我失去了多少性能.结果很奇怪,我可能在我的基准测试中偶然发现了一些懒惰的陷阱.

基准测试告诉我,即使不使用,WriterT String IO运行速度也比运行简单快20倍(!).古怪的,如果我栈与和它仅仅是5倍速度较慢.这可能是我的基准测试中的一个错误.我在这做错了什么？IOtellWriterTReaderTContT

基准

{-#LANGUAGE BangPatterns#-}
module Main where
import Criterion.Main
import Control.Monad
import Control.Monad.Writer
import Control.Monad.Reader
import Control.Monad.Cont

process :: Monad m => Int -> m Int
process = foldl (>=>) return (replicate 100000 (\(!x) -> return (x+1)))

test n = process n >> return ()

main = defaultMain [
      bench "Plain"  t0
     ,bench "Writer" t1
     ,bench "Reader" t2
     ,bench "Cont"   t3
     ,bench "RWC"    t4
    ]

t0 = test 1 :: IO ()
t1 = (runWriterT  (test 1:: WriterT String IO ()) >> return ()) :: IO ()
t2 = (runReaderT (test 1:: ReaderT String IO ()) "" >> return ()) :: IO ()
t3 = (runContT   (test 1:: ContT () IO ()) (return) >> return ()) :: IO ()
t4 = ((runWriterT . flip runReaderT "" . flip runContT return $
      (test 1 :: ContT () (ReaderT String (WriterT String IO)) ())) >> return ()) :: IO ()

结果

benchmarking Plain
mean: 1.938814 ms, lb 1.846508 ms, ub 2.052165 ms, ci 0.950
std dev: 519.7248 us, lb 428.4684 us, ub 709.3670 us, ci 0.950

benchmarking Writer
mean: 39.50431 ms, lb 38.25233 ms, ub 40.74437 ms, ci 0.950
std dev: 6.378220 ms, lb 5.738682 ms, ub 7.155760 ms, ci 0.950

benchmarking Reader
mean: 12.52823 ms, lb 12.03947 ms, ub 13.09994 ms, ci 0.950
std dev: 2.706265 ms, lb 2.324519 ms, ub 3.462641 ms, ci 0.950

benchmarking Cont
mean: 8.100272 ms, lb 7.634488 ms, ub 8.633348 ms, ci 0.950
std dev: 2.562829 ms, lb 2.281561 ms, ub 2.878463 ms, ci 0.950

benchmarking RWC
mean: 9.871992 ms, lb 9.436721 ms, ub 10.37302 ms, ci 0.950
std dev: 2.387364 ms, lb 2.136819 ms, ub 2.721750 ms, ci 0.950

Answer 1

正如你所注意到的那样,懒惰的作家单子格很慢.使用Daniel Fischer建议的严格版本可以提供很多帮助,但为什么在大堆栈中使用它会变得如此之快？

为了回答这个问题,我们来看看这些变压器的实现.首先,懒惰的作家monad变换器.

newtype WriterT w m a = WriterT { runWriterT :: m (a, w) }

instance (Monoid w, Monad m) => Monad (WriterT w m) where
    return a = WriterT $ return (a, mempty)
    m >>= k  = WriterT $ do
        ~(a, w)  <- runWriterT m
        ~(b, w') <- runWriterT (k a)
        return (b, w `mappend` w')

如你所见,这确实做了很多.它运行底层monad的动作,进行一些模式匹配并收集写入的值.几乎是你所期待的.严格的版本是相似的,只有没有无可辩驳的(懒惰)模式.

newtype ReaderT r m a = ReaderT { runReaderT :: r -> m a }

instance (Monad m) => Monad (ReaderT r m) where
    return   = lift . return
    m >>= k  = ReaderT $ \ r -> do
        a <- runReaderT m r
        runReaderT (k a) r

读卡器变压器有点精简.它分配阅读器环境并调用底层monad来执行操作.这里没有惊喜.

现在,让我们来看看ContT.

newtype ContT r m a = ContT { runContT :: (a -> m r) -> m r }

instance Monad (ContT r m) where
    return a = ContT ($ a)
    m >>= k  = ContT $ \c -> runContT m (\a -> runContT (k a) c)

注意什么不同？它实际上并没有使用底层monad中的任何函数!事实上,它甚至不需要m成为monad.这意味着根本没有进行慢速模式匹配或追加.只有当您实际尝试从底层monad中提取任何操作时才会ContT使用其bind运算符.

instance MonadTrans (ContT r) where
    lift m = ContT (m >>=)

因此,由于您实际上并未执行任何特定ContT于编写器的操作,因此请避免使用慢速绑定运算符WriterT.这就是为什么ContT在堆栈顶部使得速度更快,以及为什么运行时间ContT () IO ()与深层堆栈的运行时间非常相似的原因.

Answer 2

极度放缓的一部分原因Writer是你正在使用懒惰的作家monad,所以你的爆炸模式根本没有帮助,参见 这个问题的答案有更详细的解释(虽然对于State来说,但这也是同样的原因).改变这一点,Control.Monad.Writer.Strict将减速从八倍减少到不到四倍.堆栈还是更快,我还没有理解为什么.