Нечетные результаты теста монадных трансформаторов. Жук?

Question

Я провел несколько тестов Criterion, чтобы оценить, сколько производительности я теряю, выполняя свой код в стеке монад.Результаты были довольно любопытны, и я, вероятно, наткнулся на ловушку лени в моем тесте.

Тест показывает, что WriterT String IO работает в 20 раз (!) Медленнее, чем обычный IO, даже если не используется tell.Как ни странно, если я сложу 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

Как вы заметили, монада ленивого писателя довольно медленная.Использование строгой версии, как предлагает Даниэль Фишер, очень помогает, но почему она становится намного быстрее при использовании в большом стеке?

Чтобы ответить на этот вопрос, мы рассмотрим реализацию этих трансформаторов.Во-первых, преобразователь монады для ленивого писателя.

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 () так похоже на время выполнения более глубокого стека.

Answer 2

Частью крайнего замедления Writer является то, что вы используете монаду ленивого писателя, поэтому ваш паттерн взрыва там совсем не помогает, ср.ответ на на этот вопрос для более подробного объяснения (хотя для государства, но здесь та же причина).Изменение этого значения на Control.Monad.Writer.Strict уменьшило замедление с восьми до менее чем в четыре раза.Тем не менее, стек быстрее, я еще не понял, почему.