Вычисление STG | 161
f • a 1 . . . an;
s;
H[ f > F U N ( x 1 . . . xn > e)]
? e[ a 1/ x 1 . . . an/ xn]; s; H
f k a 1 . . . am;
s;
H[ f > F U N ( x 1 . . . xn > e)]
? e[ a 1/ x 1 . . . an/ xn]; ( • an+1 . . . am) : s; H
при m ? n
? p; s; H[ p > P AP ( f a 1 . . . am)]
при m < n, p – новый адрес
f • a 1 . . . am;
s;
H[ f > T HU N K e]
? f; ( • a 1 . . . am) : s; H
f k an+1 . . . am;
s;
H[ f > P AP ( g a 1 . . . an)]
? g• a 1 . . . an an+1 . . . am; s; H
f ;
( • a 1 . . . an) : s;
H
? f• a 1 . . . an; s; H
H[ f ] является F U N или P AP
Рис. 10.9: Синтаксис STG
Правила для стратегии вычисление-применение
Разберёмся с первыми двумя правилами. В первом правиле статическая арность f неизвестна, но зна-
чение f уже вычислено, и мы можем узнать арность по объекту F UN, далее возможны три случая. Число
аргументов переданных в функцию совпадает с арностью F UN, тогда мы применяем аргументы к правой
части F UN. Если в функцию передано больше аргументов чем нужно, мы сохраняем лишние на стеке. Если
же аргументов меньше, то мы создаём объект P AP . Третье правило говорит о том, что нам делать, если зна-
чение f ещё не вычислено. Оно является T HUNK. Тогда мы сохраним аргументы на стеке и вычислим его.
В следующем правиле мы раскрываем частичное применение. Мы просто организуем вызов функции со все-
ми аргументами (и со стека и из частичного применения). Последнее правило срабатывает после третьего.
Когда мы вычислим T HUNK и увидим там F UN или P AP . Тогда мы составляем применение функции.
Сложность применения стратегии вставка-вход связана с плохо предсказуемым изменением стека. Если в
стратегии вычисление-выполнение мы добавляем и снимаем все аргументы, то в стратегии вставка-вход мы
добавляем их по одному и неизвестно сколько снимем в следующий раз. Кроме того стратегия вычисление-
применение позволяет проводить оптимизацию перемещения аргументов. Вместо стека мы можем хранить
аргументы в регистрах. Тогда скорость обращения к аргументам резко возрастёт.
10.4 Представление значений в памяти. Оценка занимаемой памяти
Ранее мы говорили, что полностью вычисленное значение – это дерево, в узлах которого находятся одни
лишь конструкторы. Процесс вычисления похож на очистку дерева выражения от синонимов. Мы начинаем с
самого верха и идём к листьям. Потом мы выяснили, что для предотвращения дублирования вычислений мы
подставляем в функции не сами значения, а ссылки на значения. Теперь нам понятно, что ссылки указывают
на объекты в куче. Ссылки – это атомарные переменные. Полностью вычисленное значение является сетью
(или графом) объектов кучи типа CON.
Поговорим о том сколько места в памяти занимает то или иное значение. Как мы говорили память ком-
пьютера состоит из ячеек, в которых хранятся значения. У каждой ячейки есть адрес. Ячейки памяти неде-
лимы, их также принято называть словами. Мы будем оценивать размер значения в словах.
Каждый конструктор требует столько слов сколько у него полей плюс ещё одно слово для ссылки на
служебную информацию (она нужна вычислителю). Посмотрим на примеры:
data Int = I# Int#
— 2 слова
data Pair a b = Pair a b
— 3 слова
У этого правила есть исключение. Если у конструктора нет полей, то есть он является константой или
примитивным конструктором, то в процессе вычисления значение этого конструктора представлено ссылкой.
Это означает, что внутри программы все значения ссылаются на одну область памяти. У нас действительно
есть лишь один пустой список или одно значение True или False.
Посчитаем число слов в значении [Pair 1 2]. Для этого для начала перепишем его в STG
nil = []
— глобальный объект (не в счёт)
162 | Глава 10: Реализация Haskell в GHC
let x1
= I# 1
— 2 слова
x2
= I# 2
— 2 слова
p
= Pair x1 x2
— 3 слова
val = Cons p nil
— 3 слова
in
val
————
— 10 слов
Поскольку объект кучи CON может хранить только ссылки, нам пришлось введением дополнительных
переменных “развернуть” значение. Примитивный конструктор не считается, поскольку он сохранён гло-
бально, в итоге получилось 10 слов. Посмотрим на ещё один пример, распишем значение [Just True, Just
True, Nothing]:
nil
= []
true
= True
nothing = Nothing
let x1 = Just true
— 2 слова
x2 = Just true
— 2 слова
p1 = Cons nothing nil
— 3 слова
p2 = Cons x2 p1
— 3 слова
p3 = Cons x1 p2
— 3 слова
in
p3
———-
— 13 слов
Обычно одно слово соответствует 16, 32 или 64 битам. Эта цифра зависит от процессора. Мы считали,
что любое значение можно поместить в одно слово, но это не так. Возьмём к примеру действительные чис-
ла с двойной точностью, они не поместятся в одно слово. Это необходимо учитывать при оценке объёма
занимаемой памяти.
10.5 Управление памятью. Сборщик мусора
В прошлом разделе для простоты мы считали, что объекты только добавляются в кучу. На самом деле это
не так. Допустим во время вычисления функции нам нужно было вычислить какие-то промежуточные дан-
ные, например объявленные в локальных переменных, тогда после вычисления результата все эти значения
больше не нужны. При этом в куче висит много-много объектов, которые уже не нужны. Нам нужно как-то от
них избавится. Этой задачей занимается отдельный блок вычислителя, который называется сборщиком му-
сора (garbage collector), соответственно процесс автоматического освобождения памяти называется сборкой
мусора (garbage collection или GC).
На данный момент в GHC используется копирующий последовательный сборщик мусора, который рабо-
тает по алгоритму Чейни (Cheney). Для начала рассмотрим простой алгоритм сборки мусора. Мы выделяем
небольшой объём памяти и начинаем наполнять его объектами. Как только место кончится мы найдём все
“живые” объекты, а остальное пространство памяти будем считать свободным. Как только после очередной
очистки оказалось, что нам всё же не хватает места. Мы найдём все живые объекты, подсчитаем сколько ме-
ста они занимают и запросим у системы этот объём памяти. Скопируем все живые объекты на новое место, а
старую память будем считать свободной. Так например, если у нас было выделено 30 Мб памяти и оказалось,
что живые объекты занимают 10 Мб, мы выделим ещё 10 Мб, скопируем туда все живые объекты и общий
объём памяти станет равным 40 Мб.
Мы можем оптимизировать сборку мусора. Есть такая гипотеза, что большинство объектов имеют очень
короткую жизнь. Это промежуточные данные, локальные переменные. Нам нужен лишь результат функции,
но на подходе к результату мы сгенерируем много разовой информации. Ускорить очистку можно так. Мы
выделим совсем небольшой участок памяти внутри нашей кучи, его принято называть яслями (nursery area),
и будем выделять и собирать новые объекты только в нём, как только этот участок заполнится мы скопируем
все живые объекты из яслей в остальную память и снова будем наполнять ясли. Как только вся память закон-
чится мы поступим так же как и в предыдущем сценарии. Когда заканчивается место в яслях, мы проводим
поверхностную очистку (minor GC), а когда заканчивается вся память в текущей куче, мы проводим глубокую
очистку (major GC). Эта схема соответствует сборке с двумя поколениями.
10.6 Статистика выполнения программы
Процесс управления памятью скрыт от программиста. Но при этом в GHC есть развитые средства косвен-
