Cтраница 4
Если сборщик мусора просматривает мемо-таблицу и если он еще не достиг какой-либо из хранящейся в ней структуры аргументов, он не знает, какие из хранящихся структур результатов стоит сохранить, за исключением тех, которые уже были отмечены как достижимые до обращения к этой мемо-таблице. С другой стороны, некоторые структуры данных, включая аргументы, имеющие свои элементы в мемо-таблице, могут быть доступны только через структуры результатов, хранящиеся в мемо-таблице. Поэтому просто отложить проверку мемо-таблиц до конца сборки мусора было бы недостаточно. Это может привести к тому, что некоторые элементы мемо-таблицы будут удалены, причем их аргументы будут оставаться доступными для мемо-функций через результат, хранящийся в нестертой ячейке, находящейся ниже в таблице. [46]
При полном запоминании не представляется возможным предсказать для данной функции, что она никогда не будет использовать аргумент, равный тому, который уже соответствует некоторому элементу мемо-таблицы; кроме этого, мы показали, что подобное предсказание возможно лишь при локальном запоминании и только для определенного класса вырожденных мультилинейных функций, а также для тех функций, для которых программист может создать соответствующий регулировщик таблиц. Однако в случае ленивого запоминания, если сборщик мусора обнаруживает, что объект, идентичный аргументу элемента мемо-таблицы, может быть удален, поскольку ссылки на него отсутствуют, то и этот элемент больше не нужен и поэтому также может быть удален сборщиком мусора. Однако по определению все аргументы, имеющие соответствующие элементы в доступных мемо-таблицах, также являются доступными, и поэтому стандартный сборщик мусора, сохраняющий все доступные структуры данных, не может обрабатывать их. Вследствие этого он должен игнорировать ссылки элементов мемо-таблиц на хранящиеся аргументы, но, кроме этого, остаются трудности со ссылками от элементов мемо-таблицы на хранящиеся результаты. Если аргумент остается для хранения, то и соответствующий ему результат также должен быть сохранен, так чтобы он мог быть найден, когда мемо-функция будет применена к этому аргументу, и наоборот, если аргумент удаляется, то и ссылка на его результат тоже должна быть устранена. [47]
Видно, что в любом применении, в которое входит запоминание, сравнение указателей должно входить в число примитивных операций. Заметьте, что атомы также проверяются на равенство, поскольку они не имеют ассоциированного адреса; мы можем с тем же успехом считать, что каждый атом имеет уникальный ( неявный) адрес, тогда одинаковые ( равные) атомы будут идентичны согласно данному выше определению. Например, индекс хэширования может быть вычислен исходя из адреса или состояния битов указателя с помощью обычных методов. Кроме этого, подобное применение указателей для представления аргументов в мемо-таблицах облегчает сборку мусора. Мы еще встретимся с этим в разд. [48]
Если не предпринимать никаких действий для удаления неиспользуемых элементов из мемо-таблицы, то ее наращивание будет происходить непрерывно; при применении ассоциированной с ней функции к новому аргументу к ней будет прибавляться новый элемент. Именно эти излишние затраты памяти помешали запоминанию сразу же стать широко используемым видом оптимизации; в последнее время в решении этой проблемы достигнуты некоторые успехи. Существуют два пути контроля роста мемо-таблицы. Первый состоит в расширении функ-ций сборщика мусора для восстановления неиспользуемых элементов мемо-таблицы; мы обсудим это в разд. [49]
Выигрыш пространства, даваемый динамическим регулированием мемо-таблиц, достигается за счет небольшого увеличения стоимости выполнения операции вставки, так как теперь необходимо каждый раз инициировать регулировщик таблиц. Однако для работы регулировщиков таблиц не требуется дополнительных ( инструментальных) средств, поскольку они просто выражены в компилируемом функциональном языке и являются нерекурсивными. При выполнении мемо-функции основные условные выражения проверяются до выполнения просмотра. При истинности данного условия мемо-функция возвращает результат базового случая и не изменяет мемо-таблицу. В противном случае выполняется просмотр для установления того, известен ли данный результат. В связи с тем что элементы, относящиеся к базовому случаю, никогда не заносятся в мемо-таблицу, то для регулировщика таблиц нет необходимости проверять их. [50]
Конечно, эти вспомогательные операции не видны программисту и не будут, как правило, реализовываться как истинные функции во время прогона программы. Мы приведем еще одну, но чисто функциональную версию memoJib, когда будем рассматривать преобразование исходного текста в разд. Jib ( n) fib ( n) для всех п, так что memo-fib имеет ту же семантику, что и fib; очевидно, что это относится ко всем мемо-функциям. В последнем случае ни величины аргументов, ни результаты, хранящиеся в мемо-таблице, не будут вычислены полностью; ленивое запоминание в полном объеме будет обсуждаться в следующем разделе. [51]
При полном запоминании не представляется возможным предсказать для данной функции, что она никогда не будет использовать аргумент, равный тому, который уже соответствует некоторому элементу мемо-таблицы; кроме этого, мы показали, что подобное предсказание возможно лишь при локальном запоминании и только для определенного класса вырожденных мультилинейных функций, а также для тех функций, для которых программист может создать соответствующий регулировщик таблиц. Однако в случае ленивого запоминания, если сборщик мусора обнаруживает, что объект, идентичный аргументу элемента мемо-таблицы, может быть удален, поскольку ссылки на него отсутствуют, то и этот элемент больше не нужен и поэтому также может быть удален сборщиком мусора. Однако по определению все аргументы, имеющие соответствующие элементы в доступных мемо-таблицах, также являются доступными, и поэтому стандартный сборщик мусора, сохраняющий все доступные структуры данных, не может обрабатывать их. Вследствие этого он должен игнорировать ссылки элементов мемо-таблиц на хранящиеся аргументы, но, кроме этого, остаются трудности со ссылками от элементов мемо-таблицы на хранящиеся результаты. Если аргумент остается для хранения, то и соответствующий ему результат также должен быть сохранен, так чтобы он мог быть найден, когда мемо-функция будет применена к этому аргументу, и наоборот, если аргумент удаляется, то и ссылка на его результат тоже должна быть устранена. [52]