Может ли Haskell оценивать, а не мусор, собирать случайные индексы в списке?

Как я понимаю, Haskell только мусор собирает, когда что-то выходит за рамки, поэтому привязка верхнего уровня будет оцениваться только один раз и никогда не выходит за рамки. Поэтому, если я запустил этот код в GHCI, первые 50 элементов будут оценены и сохранены.

let xs = map f [0..]
take 50 xs

Мои вопросы - это то, что происходит, когда я выполняю следующий фрагмент: xs !! 99. Что спасает сборщик мусора? Это

  • Сохранять результаты для индексов 0 - 49, thunk для индексов 50 - 98, результат для индекса 99, thunk для индексов 100 +
  • Сохранять результаты для индексов 0 - 49, thunk для индексов 50 +
  • Сохранять результаты для индексов 0 - 99, thunk для индексов 100 +

Ответы

Ответ 1

Списки Haskell представляют собой связанные списки, состоящие из ячеек (:) ( "cons" ) и заканчивающиеся значением [] ( "nil" ). Я нарисую такие ячейки, как это.

 [x] -> (tail - remainder of list)
  |
  v
(head - a value)

Поэтому, размышляя о том, что оценивается, есть две части, которые следует учитывать. Сначала - позвоночник, то есть структура cons cons, а во-вторых - значения, которые содержит список. Вместо 50 и 99, используйте 2 и 4 соответственно.

ghci> take 2 xs
[0,1]

Печать этого списка заставляет оценивать первые две ячейки cons, а также значения внутри них. Таким образом, ваш список выглядит следующим образом:

[x] -> [x] -> (thunk)
 |      |
 v      v
 0      1

Теперь, когда мы

ghci> xs !! 4
3

мы не потребовали 2-го или 3-го значения, но нам нужно оценить эти ячейки cons, чтобы перейти к 4-му элементу. Таким образом, мы вынудили позвоночник до 4-го элемента, но мы оценили только 4-е значение, поэтому список теперь выглядит следующим образом:

[x] -> [x] -> [x] -> [x] -> [x] -> (thunk)
 |      |      |      |      |
 v      v      v      v      v
 0      1   (thunk) (thunk)  4

Ничто в этой картине не будет собрано в мусор. Однако иногда эти трюки могут занимать много места или ссылаться на что-то большое, и оценка их на равное значение позволит освободить эти ресурсы. См. этот ответ для небольшого обсуждения этих тонкостей.

Ответ 2

Позвольте спросить профайлер.

Мы скомпилируем следующую примерную программу, которая должна сделать примерно то, что сделала ваша сессия GHCI. Важно, чтобы мы print приводили результаты, подобные GHCI, поскольку это заставляет вычисления.

f x = (-x)

xs = map f [0..]

main = do
    print (take 50 xs)
    print (xs !! 99)

Я сохранил мой как example.hs. Мы скомпилируем его с параметрами, чтобы включить профилирование

ghc -prof -fprof-auto -rtsopts example.hs

Профиль времени

Мы можем узнать, сколько раз f было применено с профилем времени.

profile +RTS -p

Это создает выходной файл с именем example.prof, интересная часть:

COST CENTRE MODULE                     no.     entries
...
   f        Main                        78          51

Мы можем видеть, что f оценивалось 51 раз, 50 раз для print (take 50 xs) и один раз для print (xs !! 99). Поэтому мы можем исключить вашу третью возможность, поскольку f оценивалась только 51 раз, не может быть результатов для всех индексов 0-99

  1. Сохранять результаты для индексов 0 - 99, thunk для индексов 100 +

Профиль кучи результатов

Профилирование памяти в куче немного сложнее. Профайлер кучи принимает образцы, по умолчанию один раз каждые 0,1 секунды. Наша программа будет работать так быстро, что профилировщик кучи не будет брать какие-либо образцы во время работы. Мы добавим спин к нашей программе, чтобы у кучного профилировщика появилась возможность взять образец. Следующие секунды будут вращаться в течение нескольких секунд.

import Data.Time.Clock

spin :: Real a => a -> IO ()
spin seconds =
    do
        startTime <- getCurrentTime 
        let endTime = addUTCTime (fromRational (toRational seconds)) startTime
        let go = do
            now <- getCurrentTime
            if now < endTime then go else return ()
        go

Мы не хотим, чтобы сборщик мусора собирал данные во время работы программы, поэтому мы добавим еще одно использование xs после вращения.

main = do
    print (take 50 xs)
    print (xs !! 99)
    spin 1
    print (xs !! 0)

Мы запустим это с опцией профилирования кучи по умолчанию, которая группирует использование памяти по МВЗ.

example +RTS -h

Создает файл example.hp. Мы вытаскиваем образец из середины файла, где номера стабильны (пока он был в spin).

BEGIN_SAMPLE 0.57
(42)PINNED  32720
(48)Data.Time.Clock.POSIX.CAF   48
(85)spin.endTime/spin/mai...    56
(84)spin.go/spin/main/Mai...    64
(81)xs/Main.CAF 4848
(82)f/xs/Main.CAF   816
(80)main/Main.CAF   160
(64)GHC.IO.Encoding.CAF 72
(68)GHC.IO.Encoding.CodeP...    136
(57)GHC.IO.Handle.FD.CAF    712
(47)Main.CAF    96
END_SAMPLE 0.57

Мы видим, что f произвело 816 байт памяти. Для "small" Integer s, Integer потребляет 2 слова памяти. В моей системе слово составляет 8 байт памяти, поэтому "маленький" Integer принимает 16 байтов. Поэтому 816/16 = 51 из Integer, созданных f, вероятно, все еще находятся в памяти.

Мы можем проверить, что вся эта память на самом деле используется для "малого" Integer, прося описание профиля путем закрытия с помощью -hd. Мы не можем обеим использовать память памяти по закрытию дескриптонов и МВЗ, но мы можем ограничить профилирование единым МВЗ с помощью -hc, в этом случае нас интересует центр затрат f

example +RTS -hd -hcf

Это говорит о том, что все 816 байтов из-за f используются S#, конструктор для "small" Integer s

BEGIN_SAMPLE 0.57
S#  816
END_SAMPLE 0.57

Мы можем, конечно, удалить следующее, поскольку результаты 51 Integer сохраняются, и он ожидает, что останется только 50 Integer s

  1. Сохранять результаты для индексов 0 - 49, thunk для индексов 50 +

Профиль кучи структуры и thunks

Это оставляет нам опцию

  • Сохранять результаты для индексов 0 - 49, thunks для индексов 50 - 98, результат для индекса 99, thunk для индексов 100 +

Угадайте, сколько памяти эта ситуация будет потреблять.

В общем случае типы Haskell data требуют 1 слово памяти для конструктора и 1 слово для каждого поля. Конструктор [] type : имеет два поля, поэтому он должен принимать 3 слова памяти или 24 байта. 100 : будет занимать 2400 байт памяти. Мы увидим, что это точно верно, когда мы спрашиваем о описании замыкания для xs.

Трудно рассуждать о размерах трюков, но мы попробуем. Для значений индексов было бы 49 thunks [50, 98]. Каждый из этих трюков, вероятно, удерживает Integer от генератора [0..]. Он также должен содержать структуру thunk, которая, к сожалению, изменяется при профилировании. В остальном список также будет использоваться. Ему понадобится Integer, из которого будет сформирована остальная часть списка, и структура thunk.

Запрос на разбиение памяти по описанию замыкания для центра затрат xs

example +RTS -hd -hcxs

Дает нам следующий пример

BEGIN_SAMPLE 0.60
<base:GHC.Enum.sat_s34b>    32
<base:GHC.Base.sat_s1be>    32
<main:Main.sat_s1w0>    16
S#  800
<base:GHC.Base.sat_s1bd>    1568
:   2400
END_SAMPLE 0.60

Мы были точно уверены, что существует 100 :, требующих 2400 байт памяти. Есть 49 + 1 = 50 "small" Integer S#, занимающий 800 байт для thunks для 49 нерасчетных значений и thunk для остальной части списков. Есть 1568 байт, которые, вероятно, являются 49 thunks для нерасчетных значений, каждый из которых будет 32 байта или 4 слова. Есть еще 80 байт, которые мы не можем точно объяснить, оставшиеся для thunk для оставшейся части списка.

Оба профиля памяти и времени соответствуют нашему убеждению, что программа будет

  • Сохранять результаты для индексов 0 - 49, thunks для индексов 50 - 98, результат для индекса 99, thunk для индексов 100 +