Код становится медленнее, так как выделяется больше штучных массивов

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)

Это наиболее вероятно из-за поведения 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), я думаю, что эти издержки могут быть просто из-за наличия указателей на все эти массивы, торчащие в запоминаемом наборе (см. Также: здесь), и любых накладных расходов, которые вызывают для GC.

24

arrays performance haskell garbage-collection ghc

Источник

user176841 04 май '14 в 21:52

2 ответа

Решение

Я думаю, что вы определенно видите эффекты GC. У меня была связанная проблема в кассаве ( https://github.com/tibbe/cassava/issues/49), где время GC линейно увеличивалось с увеличением размера кучи.

Попытайтесь измерить, как увеличивается время GC и время мутатора, когда вы держите все больше и больше массивов в памяти.

Вы можете сократить время GC, играя с +RTS опции. Например, попробуйте установить -A к вашему размеру кэша L3.

4

Источник

user298847 06 май '14 в 14:02

Другие вопросы по тегам arrays performance haskell garbage-collection ghc

user23845 09 май '14 в 06:08 2014-05-09 06:08 · Accepted Answer · 2014-05-09 06:08

Вы платите линейные издержки за каждый второстепенный сборщик мусора за каждый изменяемый массив, который остается живым и получает повышение до старого поколения. Это потому, что GHC безоговорочно помещает все изменяемые массивы в изменяемый список и пересекает весь список каждый второстепенный сборщик мусора. См. https://ghc.haskell.org/trac/ghc/ticket/7662 для получения дополнительной информации, а также мой список рассылки, ответ на ваш вопрос: http://www.haskell.org/pipermail/glasgow-haskell-users/2014-May/024976.html