Bearbeiten: Es stellt sich heraus, dass die Dinge im Allgemeinen (nicht nur Array / Ref-Operationen) langsamer ablaufen, je mehr Arrays erstellt wurden. Ich schätze, dies ist nur eine Messung der erhöhten GC-Zeiten und ist möglicherweise nicht so seltsam, wie ich dachte. Aber ich würde wirklich gerne wissen (und lernen, wie man herausfindet), was hier vor sich geht und ob es eine Möglichkeit gibt, diesen Effekt in Code, der viele kleinere Arrays erzeugt, abzuschwächen. Die ursprüngliche Frage folgt.

Bei der Untersuchung einiger seltsamer Benchmarking-Ergebnisse in einer Bibliothek bin ich auf ein Verhalten gestoßen, das ich nicht verstehe, obwohl es möglicherweise wirklich offensichtlich ist. Es scheint, dass die Zeit, die für viele Operationen benötigt wird (Erstellen eines neuenMutableArray, Lesen oder Ändern vonIORef) nimmt proportional zur Anzahl der Arrays im Speicher zu.

Hier ist das erste Beispiel:

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,()))
    ]

Wir erstellen ein neues Array und fügen es einem Stapel hinzu. Da das Kriterium mehr Samples ausführt und der Stack wächst, nimmt die Array-Erstellung mehr Zeit in Anspruch, und dies scheint linear und regelmäßig zu wachsen:

Noch seltsamer,IORef liest und schreibt sind betroffen, und wir können das sehenatomicModifyIORef' wahrscheinlich wird es schneller, wenn mehr Arrays gecodet werden.

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,()))
    ]

Eine der beiden kommentierten Zeilen beseitigt dieses Verhalten, aber ich bin mir nicht sicher, warum (vielleicht können die Elemente tatsächlich gesammelt werden, nachdem wir das Rückgrat der Liste erzwungen haben).

FragenWas passiert hier?Ist es erwartetes Verhalten?Gibt es eine Möglichkeit, diese Verlangsamung zu vermeiden?

Bearbeiten: Ich nehme an, das hat etwas damit zu tun, dass die GC länger dauert, aber ich möchte genauer verstehen, was gerade im ersten Benchmark passiert.

Bonus Beispiel

Schließlich ist hier ein einfaches Testprogramm, mit dem Sie eine bestimmte Anzahl von Arrays vorbelegen und einige Zeit darauf verwenden könnenatomicModifyIORefs. Dies scheint das langsame IORef-Verhalten aufzuweisen.

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)

Ein Haufenprofil mit-hy zeigt meistensMUT_ARR_PTRS_CLEAN, was ich nicht ganz verstehe.

Wenn Sie reproduzieren möchten, finden Sie hier die von mir verwendete Cabal-Datei

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

Bearbeiten: Hier ist ein weiteres Testprogramm, das verwendet werden kann, um die Verlangsamung mit Heaps gleicher Größe von Arrays zu vergleichen[Integer]. Es erfordert einige Anpassungen durch Ausprobierenn und Beobachtung der Profilerstellung, um vergleichbare Läufe zu erhalten.

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)

Interessanterweise stelle ich beim Testen fest, dass Arrays mit derselben Heap-Größe die Leistung in höherem Maße beeinträchtigen als[Integer]. Z.B.

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

Schlussfolgerungen (WIP)

Dies ist höchstwahrscheinlich auf das GC-Verhalten zurückzuführen

Mutable Unboxed Arrays scheinen jedoch zu einer stärkeren Verlangsamung zu führen (siehe oben). Rahmen+RTS -A200M Bringt die Leistung der Array-Garbage-Version in Einklang mit der Listenversion und unterstützt, dass dies mit GC zu tun hat.

Die Verlangsamung ist proportional zur Anzahl der zugewiesenen Arrays und nicht zur Anzahl der Gesamtzellen im Array. Hier ist eine Reihe von Läufen zu sehen, für einen ähnlichen Test wiemain4, die Auswirkungen der Anzahl der zugewiesenen Arrays sowohl auf die für die Zuordnung benötigte Zeit als auch auf eine völlig unabhängige "Nutzlast". Dies ist für 16777216 Gesamtzellen (aufgeteilt auf jedoch viele Arrays):

   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

Und diesen gleichen Test laufen auf16777216*4 Zellen, zeigt im Grunde identische Nutzlastzeiten wie oben, nur um zwei Stellen nach unten verschoben.

Nach dem, was ich über die Funktionsweise von GHC und über (3) verstehe, könnte dieser Overhead einfach daran liegen, dass Zeiger auf all diese Arrays in der Datenbank steckenErinnerter Satz (siehe auch:Hier), und welcher Aufwand auch immer für den GC verursacht wird.