arrays - 随着分配更多的盒装数组，代码变得更慢

Question

编辑:事实证明，通常情况下(不仅仅是数组/引用操作)会减慢创建更多数组的速度，所以我想这可能只是测量增加的 GC 时间，可能并不像我想象的那么奇怪。但是我真的很想知道(并学习如何找出)这里发生了什么，以及是否有某种方法可以在创建大量小型数组的代码中减轻这种影响。原始问题如下。

在调查库中一些奇怪的基准测试结果时，我偶然发现了一些我不理解的行为，尽管它可能非常明显。许多操作(创建新的 MutableArray ，读取或修改 IORef )所花费的时间似乎与内存中数组的数量成正比。

这是第一个例子:

module Main
    where 

import Control.Monad
import qualified Data.Primitive as P
import Control.Concurrent
import Data.IORef
import Criterion.Main
import Control.Monad.Primitive(PrimState)

main = do 
  let n = 100000
  allTheArrays <- newIORef []
  defaultMain $
    [ bench "array creation" $ do
         newArr <- P.newArray 64 () :: IO (P.MutableArray (PrimState IO) ())
         atomicModifyIORef'  allTheArrays (\l-> (newArr:l,()))
    ]

我们正在创建一个新数组并将其添加到堆栈中。随着标准执行更多样本并且堆栈增长，数组创建需要更多时间，这似乎线性且有规律地增长:



更奇怪的是，IORef读写受到影响，我们可以看到atomicModifyIORef'大概随着更多的阵列被GC'd而变得更快。

main = do 
  let n = 1000000
  arrs <- replicateM (n) $ (P.newArray 64 () :: IO (P.MutableArray (PrimState IO) ()))
  -- print $ length arrs -- THIS WORKS TO MAKE THINGS FASTER
  arrsRef <- newIORef arrs
  defaultMain $
    [ bench "atomic-mods of IORef" $
    -- nfIO $           -- OR THIS ALSO WORKS
        replicateM 1000 $
          atomicModifyIORef' arrsRef (\(a:as)-> (as,()))
    ]

被评论的两行中的任何一行都摆脱了这种行为，但我不确定为什么(也许在我们强制列表的脊椎之后，元素实际上可以被收集)。

问题

这里发生了什么事？

这是预期的行为吗？

有没有办法避免这种减速？

编辑 :我认为这与 GC 需要更长的时间有关，但我想更准确地了解正在发生的事情，尤其是在第一个基准测试中。

奖金示例

最后，这里有一个简单的测试程序，可以用来预先分配一些数组和时间atomicModifyIORef。 s。这似乎表现出缓慢的 IORef 行为。

import Control.Monad
import System.Environment

import qualified Data.Primitive as P
import Control.Concurrent
import Control.Concurrent.Chan
import Control.Concurrent.MVar
import Data.IORef
import Criterion.Main
import Control.Exception(evaluate)
import Control.Monad.Primitive(PrimState)

import qualified Data.Array.IO as IO
import qualified Data.Vector.Mutable as V

import System.CPUTime
import System.Mem(performGC)
import System.Environment
main :: IO ()
main = do
  [n] <- fmap (map read) getArgs
  arrs <- replicateM (n) $ (P.newArray 64 () :: IO (P.MutableArray (PrimState IO) ()))
  arrsRef <- newIORef arrs

  t0 <- getCPUTimeDouble

  cnt <- newIORef (0::Int)
  replicateM_ 1000000 $
    (atomicModifyIORef' cnt (\n-> (n+1,())) >>= evaluate)

  t1 <- getCPUTimeDouble

  -- make sure these stick around
  readIORef cnt >>= print
  readIORef arrsRef >>= (flip P.readArray 0 . head) >>= print

  putStrLn "The time:"
  print (t1 - t0)

带有 -hy 的堆配置文件主要显示MUT_ARR_PTRS_CLEAN ，我不完全理解。

如果你想重现，这里是我一直在使用的 cabal 文件

name:                small-concurrency-benchmarks
version:             0.1.0.0       
build-type:          Simple
cabal-version:       >=1.10

executable small-concurrency-benchmarks
  main-is:             Main.hs 
  build-depends:       base >=4.6
                     , criterion
                     , primitive

  default-language:    Haskell2010
  ghc-options: -O2  -rtsopts

编辑 : 这是另一个测试程序，可用于比较相同大小的数组与 [Integer] 的堆的减速。 .调整 n 需要反复试验并观察分析以获得可比较的运行。

main4 :: IO ()
main4= do
  [n] <- fmap (map read) getArgs
  let ns = [(1::Integer).. n]
  arrsRef <- newIORef ns
  print $ length ns

  t0 <- getCPUTimeDouble
  mapM (evaluate . sum) (tails [1.. 10000])
  t1 <- getCPUTimeDouble

  readIORef arrsRef >>= (print . sum)

  print (t1 - t0)

有趣的是，当我对此进行测试时，我发现相同堆大小的数组对性能的影响程度大于 [Integer]。 .例如。

         Baseline  20M   200M
Lists:   0.7       1.0    4.4
Arrays:  0.7       2.6   20.4

结论 (WIP)

这很可能是由于 GC 行为

但是可变的未装箱数组似乎会导致更多的服务器减速(见上文)。设置+RTS -A200M使数组垃圾版本的性能与列表版本一致，支持这与 GC 有关。

减速与分配的数组数量成正比，而不是与数组中的总单元数成正比。这是一组运行显示，用于与 main4 类似的测试，分配的数组数量对分配时间和完全不相关的“有效负载”的影响。这是 16777216 个总单元格(分为许多阵列):

   Array size   Array create time  Time for "payload":
   8            3.164           14.264
   16           1.532           9.008
   32           1.208           6.668
   64           0.644           3.78
   128          0.528           2.052
   256          0.444           3.08
   512          0.336           4.648
   1024         0.356           0.652

并在 16777216*4 上运行相同的测试单元，显示与上述基本相同的有效载荷时间，仅向下移动了两个位置。

根据我对 GHC 工作原理的了解，并查看 (3)，我认为这种开销可能仅仅是因为在 remembered set 中存在指向所有这些数组的指针。 (另见:here)，以及导致 GC 的任何开销。

Answer 1

您为每个保持活跃并被提升到老一代的可变数组的每个次要 GC 支付线性开销。这是因为 GHC 无条件地将所有可变数组放在可变列表中，并在每次次要 GC 时遍历整个列表。见 https://ghc.haskell.org/trac/ghc/ticket/7662欲了解更多信息，以及我的邮件列表对您的问题的回复:http://www.haskell.org/pipermail/glasgow-haskell-users/2014-May/024976.html