arrays - significa - matrices en c ejemplos

El código se vuelve más lento a medida que se asignan más matrices en caja

Question

Edición: Resulta que las cosas en general (no solo las operaciones de matriz / referencia) disminuyen la velocidad a medida que se crearon más matrices, por lo que supongo que esto podría estar midiendo el aumento de los tiempos de GC y podría no ser tan extraño como pensé. Pero realmente me gustaría saber (y aprender cómo averiguar) qué está pasando aquí, sin embargo, y si hay alguna forma de mitigar este efecto en el código que crea muchas matrices pequeñas. La pregunta original sigue.

Al investigar algunos resultados extraños de evaluación comparativa en una biblioteca, me topé con un comportamiento que no entiendo, aunque podría ser muy obvio. Parece que el tiempo requerido para muchas operaciones (crear un nuevo MutableArray , leer o modificar un IORef ) aumenta en proporción al número de arreglos en la memoria.

Aquí está el primer ejemplo:

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

Estamos creando una nueva matriz y agregándola a una pila. A medida que el criterio hace más muestras y la pila crece, la creación de matrices toma más tiempo, y esto parece crecer lineal y regularmente:

Aún más extraño, IORef lecturas y escrituras de IORef se ven afectadas, y podemos ver que atomicModifyIORef'' a medida que más arreglos tienen 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,()))
    ]

Cualquiera de las dos líneas comentadas se deshace de este comportamiento, pero no estoy seguro de por qué (quizás después de forzar la columna vertebral de la lista, los elementos se pueden recolectar).

Preguntas

• ¿Que esta pasando aqui?
• ¿Es el comportamiento esperado?
• ¿Hay alguna manera de evitar esta desaceleración?

Edición : Supongo que esto tiene algo que ver con que GC se demore, pero me gustaría entender con más precisión lo que está sucediendo, especialmente en el primer punto de referencia.

Ejemplo de bonificación

Finalmente, aquí hay un programa de prueba simple que se puede usar para preasignar un cierto número de arreglos y programar un montón de atomicModifyIORef s. Esto parece exhibir el lento comportamiento de 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)

Un perfil de montón con -hy muestra principalmente MUT_ARR_PTRS_CLEAN , que no entiendo completamente.

Si desea reproducir, aquí está el archivo cabal que he estado usando

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

Edición : Aquí hay otro programa de prueba, que puede usarse para comparar la desaceleración con montones del mismo tamaño de arreglos contra [Integer] . Se requieren algunas pruebas y errores de ajuste y observación de perfiles para obtener ejecuciones comparables.

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)

Curiosamente, cuando pruebo esto, encuentro que la misma cantidad de matrices de matrices afecta el rendimiento en mayor grado que [Integer] . P.ej

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

Conclusiones (WIP)

1. Esto es más probable debido al comportamiento de GC

2. Pero las matrices no encajonadas mutables parecen conducir a más desaceleraciones severas (ver arriba). Setting +RTS -A200M hace que el rendimiento de la versión de basura de matriz +RTS -A200M en línea con la versión de lista, lo que admite que esto tiene que ver con GC.

3. La ralentización es proporcional al número de arreglos asignados, no al número de celdas totales en el arreglo. Aquí hay un conjunto de ejecuciones que muestran, para una prueba similar a main4 , los efectos de la cantidad de arreglos asignados tanto en el tiempo que se tarda en asignar, como en una "carga útil" completamente no relacionada. Esto es para 16777216 celdas totales (divididas entre muchas matrices):

      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

   Y al ejecutar esta misma prueba en 16777216*4 celdas, muestra tiempos de carga útil básicamente idénticos a los anteriores, solo se desplazó hacia abajo dos lugares.

4. Por lo que entiendo sobre cómo funciona GHC, y al observar (3), creo que esta sobrecarga puede ser simplemente por tener punteros a todas estas matrices que se quedan en el conjunto recordado (ver también: here ), y cualquier sobrecarga que cause el GC.

Answer 1

Creo que definitivamente estás viendo los efectos de GC. Tuve un problema relacionado con la yuca ( https://github.com/tibbe/cassava/issues/49#issuecomment-34929984 ) donde el tiempo de GC aumentaba linealmente al aumentar el tamaño del montón.

Intente medir cómo aumentan el tiempo del GC y el tiempo del mutador a medida que mantiene cada vez más matrices en la memoria.

Puede reducir el tiempo de GC al jugar con las opciones +RTS . Por ejemplo, intente configurar -A a su tamaño de caché L3.

Answer 2

Usted está pagando gastos generales lineales cada GC menor por arreglo mutable que permanece activo y se promueve a la generación anterior. Esto se debe a que GHC coloca incondicionalmente todas las matrices mutables en la lista mutable y recorre toda la lista en cada GC menor. Consulte https://ghc.haskell.org/trac/ghc/ticket/7662 para obtener más información, así como la respuesta de mi lista de correo a su pregunta: http://www.haskell.org/pipermail/glasgow-haskell-users/2014-May/024976.html