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

Я сделал некоторые критерии 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

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

Ответ 2

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