Куча заполнена ЗАКРЕПЛЕННЫМИ

Question

У меня есть небольшая программа с разумным максимальным сроком проживания, но распределяется линейно. Сначала я подумал, что это должны быть cons-ячейки или I#, но запуск программы с -p -hc показывает, что куча переполнена PINNED. Кто-нибудь понимает причину и / или может предложить улучшение?

Программа

-- task27.hs
{-# LANGUAGE FlexibleContexts #-}
import Control.Monad
import Control.Monad.ST
import Control.Exception 
import System.Random
import Data.Functor

import qualified Data.Vector.Generic.Mutable as V
import qualified Data.Vector.Unboxed as U

m = 120

task27 :: [Int] -> (Int, Int)
task27 l = runST $ do 
    r <- V.replicate m 0 :: ST s (U.MVector s Int)

    let go []     = return (1,2)
        go (a:as) = do
          let p = a `mod` m
          cur_lead <- r `V.read` p
          when (a > cur_lead) (V.write r p a)
          go as
    go l

randTest :: 
  Int -> -- Length of random testing sequence
  IO ()
randTest n =
  newStdGen <&>
  randoms <&> 
  take n <&> 
  task27 >>=
  print

main = randTest 1000000

My package.yaml:

name: task27
dependencies:
  - base == 4.*
  - vector
  - random

executables:
  task27:
    main: task27.hs
    ghc-options: -O2

My cabal.project.local:

profiling: True

Я делаю cabal -v0 run task27 -- +RTS -p -hc && hp2ps -e8in -c task27.hp и получаю следующее:

Я пытался добавить челку кое-где, но это не помогло кажется, помогает.

Answer 1

Как говорит @WillemVanOnsem, в терминах GH C резидент 35 КБ - это ничтожно мало. Какая бы у вас ни была проблема с производительностью, она не имеет ничего общего с этим крошечным битом закрепленной памяти. Первоначально я сказал, что это, вероятно, Vector s, но это неправильно. Data.Text использует закрепленную память, а Data.Vector - нет. Этот бит ЗАКРЕПЛЕННОЙ памяти выглядит так, как будто он на самом деле из самой системы выполнения, поэтому вы можете игнорировать его (см. Ниже).

В коде GH C «общее выделение» - это мера обработки. Программа GH C - это механизм распределения. Если он не распределяет, он, вероятно, ничего не делает (за редкими исключениями). Итак, если вы ожидаете, что ваш алгоритм будет работать за O (n) time , тогда он также будет O (n) в общем распределении, обычно на уровне гигабайт.

Что касается " редкие исключения », программа GH C может работать с постоянным« общим распределением », но непостоянным временем, если агрессивная оптимизация допускает вычисления с использованием полностью распакованных значений. Так, например:

main = print (sum [1..10000000] :: Int)

выполняется с постоянным общим распределением (например, 50 КБ выделено в куче), потому что Int s можно распаковать. Для сравнения:

main = print (sum [1..10000000] :: Integer)

выполняется с общим объемом выделения O (n) (например, 320 МБ выделено в куче). Кстати, попробуйте профилировать эту последнюю программу (и увеличивайте счет, пока она не проработает достаточно долго, чтобы сгенерировать несколько секунд данных профиля). Вы увидите, что он использует такой же объем ЗАКРЕПЛЕННОЙ памяти, что и ваша программа, и этот объем не меняется с верхним пределом. Итак, это просто накладные расходы системы времени выполнения.

Вернемся к вашему примеру ... Если вас беспокоит производительность, вероятно, виноват System.Random. Это ЧРЕЗВЫЧАЙНО медленный генератор случайных чисел. Если я запустил вашу программу с n = 10000000, это займет 4 секунды. Если я заменю генератор случайных чисел на простой LCG:

randoms :: Word32 -> [Word32]
randoms seed = tail $ iterate lcg seed
  where lcg x = (a * x + c)
        a = 1664525
        c = 1013904223

, он будет работать за 0,2 секунды, то есть в 20 раз быстрее.