Странность использования памяти (утечка памяти?)

У меня есть следующий тип и две соответствующие функции, которые я намереваюсь измерить как часть большого списка:

Тип и функции доступа:

data Aggregate a = Aggregate (Maybe a) (a -> Aggregate a)

get :: Aggregate a -> Maybe a
get (Aggregate get' _) = get'

put :: Aggregate a -> a -> Aggregate a
put (Aggregate _ put') = put'

Первая функция:

updateFirst :: Maybe a -> a -> Aggregate a
updateFirst cur val = Aggregate new (updateFirst new)
  where new = mplus cur (Just val)

first :: Aggregate a
first = Aggregate Nothing (updateFirst Nothing)

Вторая функция:

updateMinimum :: Ord a => Maybe a -> a -> Aggregate a
updateMinimum cur val = Aggregate new (updateMinimum new)
  where new = min <$> (mplus cur (Just val)) <*> Just val

minimum :: Ord a => Aggregate a
minimum = Aggregate Nothing (updateMinimum Nothing)

Функции написаны таким образом, что память должна быть постоянной. Поэтому я решил использовать языковое расширение Strict в GHC, которое принудительно оценивает переходники. Библиотека Weigh использовалась для выполнения измерений распределения:

test :: A.Aggregate Double -> Int -> Maybe Double
test agg len = A.get $ F.foldl' A.put agg (take len $ iterate (+0.3) 2.0)

testGroup :: String -> A.Aggregate Double -> Weigh ()
testGroup name agg = sequence_ $ map (\cnt -> func (str cnt) (test agg) cnt) counts
  where
    counts  = map (10^) [0 .. 6]
    str cnt = name ++ (show cnt)

main :: IO ()
main =
  mainWith
    (do setColumns [Case, Allocated, Max, GCs]
        testGroup "fst" A.first
        testGroup "min" A.minimum
    )

Вывод Weigh выглядит следующим образом:

Case          Allocated          Max  GCs
fst1                304           96    0
fst10             2,248           96    0
fst100           21,688           96    0
fst1000         216,088           96    0
fst10000      2,160,088           96    2
fst100000    21,600,088           96   20
fst1000000  216,000,088           96  207
min1                552           96    0
min10             4,728           96    0
min100           46,488           96    0
min1000         464,088           96    0
min10000      4,967,768           96    4
min100000    49,709,656    6,537,712   44
min1000000  497,226,840  103,345,512  445

Почему GHC внезапно выделяет намного больше памяти для входных данных размером 10^5 и 10^6? Моя версия GHC 8.4.4.


memory-management thunk haskell ghc
person Daniel Lovasko    schedule 28.12.2019    source источник
comment
Подозреваемым здесь является new = ..., который не оценивается до тех пор, пока не понадобится из-за лени. Попробуйте сделать это перед возвратом результата, как в updateFirst cur val = new `seq` Aggregate new (updateFirst new). В качестве альтернативы также может подойти рисунок челки. (Может быть, нужно больше форсирования, но я бы начал с этого.)   -  person chi    schedule 29.12.2019
comment
Модуль, содержащий updateFirst, использует расширение Strict — насколько я понимаю, он автоматически форсирует все переходники — не так ли?   -  person Daniel Lovasko    schedule 29.12.2019
comment
Это может быть так, если это также модуль, определяющий Aggregate. Тем не менее, я бы попробовал его протестировать.   -  person chi    schedule 29.12.2019
comment
@DanielLovasko, насколько я понимаю, он автоматически заставляет все преобразователи. Расширение Strict скромнее этого. Это эквивалентно тому, чтобы сделать поля всех типов данных, определенных в модуле, строгими. И строгость поля просто означает, что всякий раз, когда значение типа данных оценивается как WHNF — скажем, как аккумулятор foldl' — поле также будет оцениваться как WHNF. Обратите внимание, что, в частности, Maybe не становится строгим, как это определено в другом месте. Возможно, это часть проблемы. Попробуйте указать значение внутри Just, а не только во внешнем Maybe.   -  person danidiaz    schedule 29.12.2019
comment
Существуют ли какие-либо инструменты, кроме карандаша и бумаги, которые помогли бы мне определить, какое выражение лица вызывает создание щелчка? Или, скорее, есть ли у GHC способ распечатать все созданные им переходники? Что касается Strict, я думаю, что вы описываете StrictData, который делает типы строгими, но чистое расширение Strict также должно достигать аргументов функции.   -  person Daniel Lovasko    schedule 29.12.2019
comment
@danidiaz - вы были правы - принудительное использование значения в конструкторе Just с помощью BangPatterns действительно было ключом к устранению утечки памяти. Спасибо! Не могли бы вы опубликовать свой комментарий в качестве ответа, чтобы я мог принять его, пожалуйста?   -  person Daniel Lovasko    schedule 29.12.2019

Ответы (1)


arrow_upward
3
arrow_downward

Аннотации строгости в Haskell являются "реляционными", поэтому разговаривать. Они говорят, что что-то должно оцениваться как WHNF (нормальная форма слабой головы), всякий раз, когда что-то еще оценивается как WHNF .

Для аргументов функции это означает, что аргумент функции будет оценен как WHNF до того, как само приложение функции будет оценено как WHNF.

Для строгих полей это означает, что поле будет оцениваться как WHNF всякий раз, когда содержащее его значение оценивается как WHNF. Это полезно для поддержания «цепочки строгости» в типах данных, которые служат накопителями (например, тип данных, работающий в качестве накопителя foldl'). В противном случае преобразователи могут прятаться за ленивыми полями, даже если содержащее значение остается в WHNF, и вызывать утечку пространства. В частности, кортежи не имеют строгих компонентов и являются частым источником утечек пространства в аккумуляторах.

Maybe также не ограничивает значение, содержащееся в конструкторе Just. Собственно, это и было причиной проблемы. Значение внутри Just никогда не форсировалось в течение foldl', и там накапливались переходы.

Почему не Strict предотвратить проблему? Потому что это влияет только на определения функций и типов данных в текущем модуле, а Maybe был определен в другом месте. Решение состоит в том, чтобы вручную задавать значение внутри Just на каждой итерации или, возможно, определить свое собственное "строгий Maybe".

person danidiaz    schedule 29.12.2019
comment
Связанный: stackoverflow.com/questions/23280936/ - person danidiaz; 29.12.2019