随着分配更多盒装数组,代码变得更慢

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 而越来越快.

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需要更长时间有关,但我想更准确地了解发生了什么,特别是在第一个基准测试中.

---

奖金榜样

最后,这是一个简单的测试程序,可用于预先分配一些数组并为一堆atomicModifyIORefs 计时.这似乎表现出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)

1. 这很可能是由于GC行为造成的

2. 但可变的无盒式阵列似乎导致更严重的减速(见上文).设置+RTS -A200M使阵列垃圾版本的性能符合列表版本,支持这与GC有关.

3. 减速与分配的阵列数成比例,而不是阵列中的总单元数.下面是一组运行,显示了对于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单元上运行相同的测试,显示与上面基本相同的有效载荷时间,仅向下移动两个位置.

4. 根据我对GHC如何工作的理解,以及(3),我认为这个开销可能只是指向所有这些数组中的指针,这些数据在记忆集中都存在(参见: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