隨着更多盒裝陣列的分配，代碼變得越來越慢

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，我不完全理解。

如果要複製，這裏是我一直在使用

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），我認爲這方面的開銷可能會從具有指針的所有這些陣列在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

Answer 2

我想你絕對看到GC效應。我在木薯中有一個相關的問題（https://github.com/tibbe/cassava/issues/49#issuecomment-34929984），其中GC時間隨着堆大小的增加而線性增加。

嘗試測量GC時間和增變器時間如何在內存中佔用越來越多的數組時增加。

您可以使用+RTS選項來減少GC時間。例如，嘗試將L334緩存大小設置爲-A。