Сколько памяти использует thunk?

Скажем, у меня очень большое число (миллионы/миллиарды +) этих простых структур данных Foo:

data Foo = Foo
    { a :: {-# UNPACK #-}!Int
    , b :: Int
    }

С таким количеством плавающих вокруг необходимо подумать о том, сколько памяти они потребляют.

На 64-битной машине каждый Int составляет 8 байтов, поэтому a занимает всего 8 байтов (потому что он строгий и распакованный). Но сколько памяти займет b? Я предполагаю, что это изменится в зависимости от того, оценивается ли тон или нет, не так ли?

Я предполагаю, что в общем случае это невозможно сказать, потому что b может зависеть от любого количества позиций памяти, которые остаются только в памяти, в случае, если b необходимо оценить. Но что, если b зависело только от (очень дорогостоящей операции) a? Тогда существует ли детерминированный способ определить, сколько памяти будет использовано?

Ответ 1

В дополнение к user239558s ответьте, и в ответ на ваш комментарий там Id хотел бы указать некоторые инструменты, которые позволяют вам проверять представление кучи вашего значения, найти ответы на такие вопросы, как это самостоятельно, и увидеть эффект оптимизации и различные способы компиляции.

ghc-datasize

указывает размер закрытия. Здесь вы можете увидеть, что (на 64-битной машине) в оценочной форме и после сбора мусора Foo 1 2 требует 24 байта самостоятельно и, в том числе зависимостей, всего 40 байтов:

Prelude GHC.DataSize Test> let x = Foo 1 2
Prelude GHC.DataSize Test> x
Foo {a = 1, b = 2}
Prelude GHC.DataSize Test> System.Mem.performGC
Prelude GHC.DataSize Test> closureSize x
24
Prelude GHC.DataSize Test> recursiveSize x
40

Чтобы воспроизвести это, вам нужно загрузить определение данных в скомпилированной форме с помощью -O, в противном случае прагма {-# UNPACK #-} не имеет эффекта.

Теперь давайте создадим thunk и посмотрим, что размер значительно увеличивается:

Prelude GHC.DataSize Test> let thunk = 2 + 3::Int
Prelude GHC.DataSize Test> let x = Foo 1 thunk
Prelude GHC.DataSize Test> x `seq` return ()
Prelude GHC.DataSize Test> System.Mem.performGC
Prelude GHC.DataSize Test> closureSize x
24
Prelude GHC.DataSize Test> recursiveSize x
400

Теперь это довольно сложно. Причина в том, что этот расчет включает ссылки на статические закрытия, Num словари типа и тому подобное, и, как правило, байт-код GHCi очень неоптимизирован. Поэтому давайте поместим это в правильную программу Haskell. Запуск

main = do
    l <- getArgs
    let n = length l
    n `seq` return ()
    let thunk = trace "I am evaluated" $ n + n
    let x = Foo 1 thunk
    a x `seq` return ()
    performGC
    s1 <- closureSize x
    s2 <- closureSize thunk
    r <- recursiveSize x
    print (s1, s2, r)

дает (24, 24, 48), поэтому теперь значение Foo составлено из Foo и thunk. Почему только thunk, shouldnt также есть ссылка на n, добавив еще 16 байт? Чтобы ответить на этот вопрос, нам нужен лучший инструмент:

ghc-heap-view

Эта библиотека (по мне) может исследовать кучу и точно указать, как ваши данные представлены там. Поэтому добавив эту строку в файл выше:

buildHeapTree 1000 (asBox x) >>= putStrLn . ppHeapTree

получаем (при передаче пяти параметров программе) результат Foo (_thunk 5) 1. Обратите внимание, что порядок аргументов заменяется на кучу, поскольку указатели всегда поступают перед данными. Простой 5 указывает, что закрытие thunk сохраняет аргумент unboxed.

В качестве последнего упражнения мы проверим это, сделав трюк ленивым в n: Теперь

main = do
    l <- getArgs
    let n = length l
    n `seq` return ()
    let thunk = trace "I am evaluated" $ n
    let x = Foo 1 thunk
    a x `seq` return ()
    performGC
    s1 <- closureSize x
    s2 <- closureSize thunk
    s3 <- closureSize n
    r <- recursiveSize x
    buildHeapTree 1000 (asBox x) >>= putStrLn . ppHeapTree
    print (s1, s2, s3, r)

дает кучное представление Foo (_thunk (I# 4)) 1 с отдельным замыканием для n (как указано наличием конструктора I#) и показывает ожидаемые размеры для значений и их общего числа, (24,24,16,64).

О, и если это еще слишком высокий уровень, getClosureRaw дает вам необработанные байты.

Ответ 2

Если оценивается b, это будет указатель на объект Int. Указатель имеет 8 байтов, а объект Int состоит из заголовка, который составляет 8 байтов, а Int# - 8 байтов.

Итак, в этом случае использование памяти - это Foo object (8 header, 8 Int, 8 pointer) + boxed Int (8 header, 8 Int#).

Если b не оценивается, 8-байтовый указатель в Foo будет указывать на Thunk object. Thunk object представляет собой неоценимое выражение. Как и объект Int, этот объект имеет 8-байтовый заголовок, но остальная часть объекта состоит из свободных переменных в неоцениваемом выражении.

Итак, в первую очередь, количество свободных переменных, хранящихся в этом объекте, зависит от выражения, которое создает объект Foo. Различные способы создания Foo будут иметь объекты thunk с потенциально разными размерами.

Затем, во-вторых, свободные переменные - это все переменные, которые упоминаются в неоцениваемом выражении, которое берется извне выражения, называемого среда закрытия. Они являются своего рода параметрами для выражения, и их нужно где-то хранить, и поэтому они хранятся в объекте thunk.

Итак, вы можете посмотреть фактические места, где вызывается конструктор Foo, и посмотреть количество свободных переменных во втором параметре, чтобы оценить размер thunk.

Объект Thunk действительно такой же, как закрытие на большинстве других языков программирования, с одним важным отличием. Когда он оценивается, он может быть перезаписан указателем перенаправления на оцениваемый объект. Таким образом, это закрытие, которое автоматически запоминает его результат.

Указатель перенаправления указывает на объект Int (16 байтов). Однако теперь "мертвый" удар будет устранен в следующей сборке мусора. Когда GC копирует Foo, он заставит Foo b указывать непосредственно на объект Int, делая thunk unreferenced и, таким образом, мусор.