Monad Transformer 基准测试的奇怪结果。一个错误？

Question

我做了一些 Criterion 基准测试来估计在 monad 堆栈上运行代码会损失多少性能。结果相当奇怪，我可能在我的基准测试中偶然发现了一些惰性陷阱。

基准测试告诉我，即使不使用 tell，运行 WriterT String IO 也比运行普通 IO 慢 20 倍（！）。奇怪的是，如果我将 WriterT 与 ReaderT 和 ContT 堆叠起来，速度只会慢 5 倍。这可能是我的基准测试中的一个错误。我在这里做错了什么？

基准测试

{-#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

正如您所注意到的，惰性写入器 monad 非常慢。正如丹尼尔·费舍尔（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 才会使用其绑定运算符。

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

因此，由于您实际上并未执行任何特定于编写器的操作，因此 ContT 避免使用 WriterT 中的慢速绑定运算符。这就是为什么将 ContT 放在堆栈顶部会使其速度更快，以及为什么 ContT () IO () 的运行时间与更深层次的运行时间如此相似。堆。

Answer 2

Writer 极度减慢的部分原因是您使用了惰性编写器 monad，因此您的 bang-pattern 在那里根本没有帮助，参见。 这个问题的答案< /a> 以获得更详细的解释（虽然是针对 State，但这里是同样的原因）。将其更改为 Control.Monad.Writer.Strict 可以将速度减慢从八倍减少到不到四倍。堆栈仍然更快，我还不明白为什么。