13

私はいくつかの Criterion ベンチマークを実行して、モナド スタック上でコードを実行することによって失われるパフォーマンスを推定しました。結果はかなり興味深いものでした。おそらく、ベンチマークで怠惰の落とし穴に出くわしたことでしょう。

ベンチマークによると、 を使用していない場合でも、WriterT String IO実行は plain の実行よりも 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 ()

結果

ベンチマークプレーン
平均: 1.938814 ミリ秒、lb 1.846508 ミリ秒、ub 2.052165 ミリ秒、ci 0.950
標準偏差: 519.7248 us、lb 428.4684 us、ub 709.3670 us、ci 0.950

ベンチマークライター
平均: 39.50431 ミリ秒、lb 38.25233 ミリ秒、ub 40.74437 ミリ秒、ci 0.950
標準偏差: 6.378220 ミリ秒、lb 5.738682 ミリ秒、ub 7.155760 ミリ秒、ci 0.950

ベンチマークリーダー
平均: 12.52823 ミリ秒、lb 12.03947 ミリ秒、ub 13.09994 ミリ秒、ci 0.950
標準偏差: 2.706265 ミリ秒、lb 2.324519 ミリ秒、ub 3.462641 ミリ秒、ci 0.950

ベンチマーク 続き
平均: 8.100272 ミリ秒、lb 7.634488 ミリ秒、ub 8.633348 ミリ秒、ci 0.950
標準偏差: 2.562829 ミリ秒、lb 2.281561 ミリ秒、ub 2.878463 ミリ秒、ci 0.950

RWC のベンチマーク
平均: 9.871992 ミリ秒、lb 9.436721 ミリ秒、ub 10.37302 ミリ秒、ci 0.950
標準偏差: 2.387364 ミリ秒、lb 2.136819 ミリ秒、ub 2.721750 ミリ秒、ci 0.950
4

2 に答える 2

17

お気づきのように、レイジー ライター モナドは非常に遅いです。Daniel Fischer が提案するように厳密なバージョンを使用すると非常に役立ちますが、大きなスタックで使用するとなぜそれほど高速になるのでしょうか?

この質問に答えるために、これらのトランスフォーマーの実装を見ていきます。まず、レイジーライターのモナド変換子です。

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')

ご覧のとおり、これは非常に多くのことを行います。基礎となるモナドのアクションを実行し、いくつかのパターンマッチングを行い、書き込まれた値を収集します。あなたが期待するものとほとんど同じです。厳密なバージョンも同様ですが、反駁できない (怠惰な) パターンがありません。

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

リーダー トランスフォーマーは少し無駄がありません。リーダー環境を配布し、基礎となるモナドを呼び出してアクションを実行します。ここで驚きはありません。

では、見てみましょう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)

何か違うことに気づきましたか？基礎となるモナドの関数を実際には使用しません! m実際、モナドである必要さえありません。これは、遅いパターン マッチングや追加がまったく行われていないことを意味します。基礎となるモナドからアクションを実際に持ち上げようとする場合にのみContT、バインド演算子を使用します。

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

したがって、実際にはライター固有のことを行っていないため、ContTからの低速バインド演算子の使用を避けWriterTます。そのContTため、スタックの上にあると非常に高速になり、実行時間がContT () IO ()より深いスタックの実行時間と非常に似ています。

于 2011-11-11T12:59:40.707 に答える
5

の極端な速度低下の一部はWriter、レイジー ライター モナドを使用しているためです。より詳細な説明については、この質問への回答を参照してください (州の場合ですが、ここでも同じ理由です)。これを変更するとControl.Monad.Writer.Strict、ここでの速度低下が 8 倍から 4 倍未満に減少しました。それでもスタックは高速ですが、その理由はまだわかりません。

于 2011-11-11T11:33:36.797 に答える