haskell - 为什么在此示例中StateT更快？

Question

我正在尝试对非monadic a->函数，StateT和IORef之间更新字段的性能差异进行基准测试。我的基准代码如下：

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE BangPatterns #-}

module Main where

import Control.Monad.State.Strict
import Criterion.Main
import Data.IORef
import Data.List

newtype MyStateT s m a = MyStateT { unMyStateT :: StateT s m a }
    deriving (Functor, Applicative, Monad, MonadState s)

runMyStateT = runStateT . unMyStateT

data Record = Record
    { ra :: Int
    , rb :: String
    , rc :: Int
    , rd :: Int
    } deriving (Show)

newRecord :: IO (IORef Record)
newRecord = newIORef Record
    { ra = 0
    , rb = "string"
    , rc = 20
    , rd = 30
    }

updateRecordPure :: Record -> Record
updateRecordPure !r = r { ra = ra r + 1 }

updateRecord :: IORef Record -> IO ()
updateRecord ref = do
    r <- readIORef ref
    writeIORef ref $ r { ra = ra r + 1 }

modifyRecord :: IORef Record -> IO ()
modifyRecord ref = modifyIORef' ref (\r -> r { ra = ra r + 1 })

updateRecordM :: (MonadState Record m) => m ()
updateRecordM = modify' $ \r -> r { ra = ra r + 1 }

numCycles :: [Int]
numCycles = [1..10000]

runUpdateRecordPure :: Record -> Record
runUpdateRecordPure rec = foldl' update rec numCycles
  where
    update !r _ = updateRecordPure r

runUpdateRecord :: IO ()
runUpdateRecord = do
    r <- newRecord
    mapM_ (\_ -> updateRecord r) numCycles

runModifyRecord :: IO ()
runModifyRecord = do
    r <- newRecord
    mapM_ (\_ -> modifyRecord r) numCycles

runModifyRecordStateM :: (MonadState Record m) => m ()
runModifyRecordStateM = mapM_ (const updateRecordM) numCycles

main = defaultMain
    [ bgroup "Pure"
        [ bench "update" $ whnf runUpdateRecordPure rec
        ]
    , bgroup "IORef record"
        [ bench "update" $ whnfIO runUpdateRecord
        , bench "modify" $ whnfIO runModifyRecord
        ]
    , bgroup "MyStateT"
        [ bench "modify" $ whnfIO (snd <$> runMyStateT runModifyRecordStateM rec)
        ]
    ]
  where
    rec = Record
        { ra = 0
        , rb = "string"
        , rc = 20
        , rd = 30
        }

基准结果是：

benchmarking Pure/update
time                 124.9 μs   (123.6 μs .. 126.2 μs)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 124.5 μs   (123.0 μs .. 126.1 μs)
std dev              5.039 μs   (4.054 μs .. 6.350 μs)
variance introduced by outliers: 40% (moderately inflated)

benchmarking IORef record/update
time                 70.14 μs   (69.48 μs .. 70.99 μs)
                     0.998 R²   (0.998 R² .. 0.999 R²)
mean                 70.40 μs   (69.53 μs .. 71.51 μs)
std dev              3.141 μs   (2.634 μs .. 3.866 μs)
variance introduced by outliers: 47% (moderately inflated)

benchmarking IORef record/modify
time                 131.9 μs   (130.1 μs .. 133.4 μs)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 131.0 μs   (129.5 μs .. 132.8 μs)
std dev              5.712 μs   (4.667 μs .. 7.476 μs)
variance introduced by outliers: 44% (moderately inflated)

benchmarking MyStateT/modify
time                 31.95 μs   (31.65 μs .. 32.28 μs)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 32.06 μs   (31.72 μs .. 32.49 μs)
std dev              1.243 μs   (985.4 ns .. 1.564 μs)
variance introduced by outliers: 44% (moderately inflated)

从结果看来，StateT版本几乎比非monadic版本快四倍，比IORef版本快两倍。

该代码是使用-O2，-threaded和-fno-full-laziness编译的（添加-fno-full-laziness的结果没有太大变化）。我尝试从 whnf / whnfIO切换到 nf / nfIO，但唯一改变的是非一元版本变得更慢。

有人可以解释为什么此示例中的StateT版本比其他版本具有更高的性能吗？

Answer 1

基准测试除了“可以多快地更新变量”之外，还测试了很多其他东西。这里的主要问题是Haskell的懒惰。像updateRecordPure这样简单的行为并没有达到预期的效果：

updateRecordPure :: Record -> Record
updateRecordPure !r = r { ra = ra r + 1 }

当然，它会强制 r转换为弱头正常形式。但是没有评估 ra字段，我们可以很容易地证明这一点：

-- This just evaluates to (), it doesn't diverge.
updateRecordPure Record {} `seq` ()

因此，这里发生的是 updateRecordPure正在创建带有重击的 Record。通常，此问题（累积重击）是优化Haskell程序时的常见问题，其他基准测试也遭受该问题的困扰。

有一个简单的实验，我们可以运行以查看除递增变量外是否还有其他事情发生。所有这些更新都应占用恒定的时间和恒定的空间，除非它们在内存中累积了重击。尝试将10000调整为100000 ...您会发现运行时间增加了10倍以上！

我在 Gist中制作了基准的修改和清理版本，该版本将迭代次数作为命令行参数。它进行了其他一些更改，例如删除列表和使用 replicateM_，这有点惯用了。在我的系统上，从10000迭代到100000迭代具有以下效果：


纯粹/更新需要80倍的时间，
IORef记录/更新的时间是原来的30倍，
IORef记录/修改的时间是23倍，
MyStateT / identity需要1倍的时间，并且
MyStateT / io需要13倍的时间。


MyStateT/identity基准只是应用于 MyStateT monad的 Identity。无论如何，GHC都能完全优化这种情况，并且这种情况的运行时间为14 ns……无论您使用多少次迭代！

但是对于其他情况，由于将迭代次数增加10倍会使运行时间增加10倍以上，因此我们知道这里发生的事情不仅仅是增加整数并分配记录。

确定基准

固定基准的懒惰方法是使记录字段严格。

data Record = Record
    { ra :: !Int
    , rb :: String
    , rc :: Int
    , rd :: Int
    } deriving (Show)

进行此更改后，从10000次迭代到100000次迭代，Pure / update，IORef记录/修改和MyStateT / io的运行时间将增加大约10倍。 IORef记录/更新仍然像预期的那样慢，因为它正在堆上构造10000或100000块链，然后在最后对其进行评估（此行为众所周知，并记录在 modifyIORef文档中，尽管它仍然捕获了很多Haskell程序员感到惊讶）。

在我的贫乏VPS上，具有严格 ra字段的新版本在以下情况下具有10000次迭代，从最快到最慢排名为：


MyStateT /身份：13.67 ns
纯/更新：72.72μs
IORef记录/修改：664.2μs
MyStateT / io：1.170毫秒
IORef记录/更新：16.84 ms


通过这些更改， MyStateT/identity基准仍然以某种方式触发了GHC优化，从而消除了循环。从其他实现中，纯实现是最快的，这是可以预期的，并且增加了其他复杂性（使用IORef，然后使用IO + StateT）会使基准测试变慢。最后， readIORef + writeIORef是最慢的，因为它会产生大量的重击。

请注意，纯实现每次迭代仅花费7 ns。

不使用 -threads进行编译会大大减少运行时间，从而使Pure / update，IORef记录/修改和MyStateT / io相互之间保持25％的比例。因此，我们可以得出这样的结论：差异是由于在多线程程序中使用IO所必需的某种同步，或者是由于多线程程序的代码生成有所不同，导致某些类型的优化无法优化基准。