Cтраница 2
Стоимость таких проверок высока, а выполняться они должны при каждом вызове мемо-функции, возможно, несколько раз по мере роста мемо-таблицы. Проблема усугубляется тем, что применение сложных методов для обработки составных структур затруднительно, например использование хэширования для оптимизации поиска в мемо-таблицах или для формирования этих таблиц в виде упорядоченных деревьев. В любом случае получение необходимой и уникальной характеризации структуры данных требует создания рекурсивной функции. Другим недостатком этого вида запоминания является то, что при проверке на равенство необходимо полное вычисление всех аргументов, и поэтому мы ограничены вычислениями аппликативного порядка. [16]
Запоминание осуществляется путем сохранения результатов, вычисленных функцией для всех тех аргументов, к которым она применялась; при этом пары аргумент-результат заносятся в мемо-таблицу. [17]
В последнем случае, если текущий аргумент заменяется на указатель ptr на ячейку вершины ( дерева), то применение регулировщика таблиц будет указывать, что элементы мемо-таблицы с ключами ( компонентами аргумента), равными ptr. Операция вставки не требует сканирования всей таблицы для удаления элементов, указанных регулировщиком таблиц. Достаточно лишь осуществить просмотр таблицы для обнаружения всех удаляемых элементов, применив методы хэширования или реорганизации дерева таблицы. [18]
При полном запоминании не представляется возможным предсказать для данной функции, что она никогда не будет использовать аргумент, равный тому, который уже соответствует некоторому элементу мемо-таблицы; кроме этого, мы показали, что подобное предсказание возможно лишь при локальном запоминании и только для определенного класса вырожденных мультилинейных функций, а также для тех функций, для которых программист может создать соответствующий регулировщик таблиц. Однако в случае ленивого запоминания, если сборщик мусора обнаруживает, что объект, идентичный аргументу элемента мемо-таблицы, может быть удален, поскольку ссылки на него отсутствуют, то и этот элемент больше не нужен и поэтому также может быть удален сборщиком мусора. Однако по определению все аргументы, имеющие соответствующие элементы в доступных мемо-таблицах, также являются доступными, и поэтому стандартный сборщик мусора, сохраняющий все доступные структуры данных, не может обрабатывать их. Вследствие этого он должен игнорировать ссылки элементов мемо-таблиц на хранящиеся аргументы, но, кроме этого, остаются трудности со ссылками от элементов мемо-таблицы на хранящиеся результаты. Если аргумент остается для хранения, то и соответствующий ему результат также должен быть сохранен, так чтобы он мог быть найден, когда мемо-функция будет применена к этому аргументу, и наоборот, если аргумент удаляется, то и ссылка на его результат тоже должна быть устранена. [19]
В фазе маркирования, когда сборщик мусора находит ячейку типа memo table ( головная ячейка списка или корневая - для дерева), он маркирует ее, а затем сканирует мемо-таблицу. Для каждой ячейки мемо-таблицы он извлекает связанный с нею элемент ( представленный ячейкой типа entry, указываемой этой ячейкой) и исследует его аргумент. Если аргумент является атомом или уже маркирован, то и этот элемент, и его результат маркируются. [20]
Рассмотрим простую систему, в которой все ячейки, предназначенные для хранения составных данных, содержат поля для двух указателей и метки, указывающие на их тип. Предположим, что мемо-таблица имеет вид списка элементов и что головная ячейка имеет тип memo table. Поскольку ячейки состоят лишь из двух указателей и метки, то список мемо-таб-лицы будет представлен как бтдельная структура, в которой поле первого указателя будет связывать элементы списка, а второго - указывать на ячейку типа entry, представляющую вход мемо-таблицы. На практике более подходящей структурой было бы - двоичное дерево благодаря дополнительному полю ячейки-указателя, так как в противоположном случае для каждой вершины было бы необходимо иметь две связанные ячейки. Эффективность также можно увеличить, если бы элементы мемо-таблицы были объединены в ячейки, образующие список или древовидную структуру мемо-таблицы вместо необходимости осуществлять косвенный доступ к ним, а в практических реализациях использовались бы ячейки переменного размера; в этом случае указателей было бы четыре или для древовидной мемо-таблицы - пять. [21]
В фазе маркирования, когда сборщик мусора находит ячейку типа memo table ( головная ячейка списка или корневая - для дерева), он маркирует ее, а затем сканирует мемо-таблицу. Для каждой ячейки мемо-таблицы он извлекает связанный с нею элемент ( представленный ячейкой типа entry, указываемой этой ячейкой) и исследует его аргумент. Если аргумент является атомом или уже маркирован, то и этот элемент, и его результат маркируются. [22]
Описанный выше вид локального запоминания не позволяет осуществлять динамическое управление мемо-таблицами, при котором по мере добавления новых элементов таблицы устаревшие и ненужные элементы удаляются из нее, причем полного разрушения таблицы при этом не происходит. Это позволяет сохранять размер мемо-таблиц в разумных контролируемых пределах; во многих случаях это небольшое фиксированное число элементов. Мы сосредоточим наше внимание главным образом на локальном запоминании, при котором мемо-таблица создается для каждого применения верхнего уровня мемо-функ-ции, а запоминание происходит лишь для применений этих функций, входящих в описывающие ее уравнения, а также в уравнения других функций, вызываемые из них. Некоторая ограниченность подобного подхода проявляется, например, в том, что два применения верхнего уровня функции fib ( 20) будут выполняться за линейное время каждая при локальном запоминании в то время, как второе применение может быть выполнено за постоянное время при простом поиске и нахождении своего результата в мемо-таблице первой функции, если эта таблица не была разрушена. Далее мы увидим, что при этом ограничении компилятор способен во многих случаях автоматически определять стратегию динамического удаления путем простого грамматического анализа выражения, описывающего мемо-функцию. [23]
Если сборщик мусора просматривает мемо-таблицу и если он еще не достиг какой-либо из хранящейся в ней структуры аргументов, он не знает, какие из хранящихся структур результатов стоит сохранить, за исключением тех, которые уже были отмечены как достижимые до обращения к этой мемо-таблице. С другой стороны, некоторые структуры данных, включая аргументы, имеющие свои элементы в мемо-таблице, могут быть доступны только через структуры результатов, хранящиеся в мемо-таблице. Поэтому просто отложить проверку мемо-таблиц до конца сборки мусора было бы недостаточно. Это может привести к тому, что некоторые элементы мемо-таблицы будут удалены, причем их аргументы будут оставаться доступными для мемо-функций через результат, хранящийся в нестертой ячейке, находящейся ниже в таблице. [24]
Помимо положительных сторон, использование мемо-функ-ций приводит к серьезным трудностям при их реализации. Во-первых, сопоставление аргументов с элементами мемо-таблицы является неэффективным, если данный аргумент является составной структурой данных, например деревом. Мемо-функция проверяет аргументы и каждый элемент на равенство, используя рекурсивную процедуру тестирования каждой подструктуры объекта с рекурсивно определенным типом данных. [25]
При полном запоминании не представляется возможным предсказать для данной функции, что она никогда не будет использовать аргумент, равный тому, который уже соответствует некоторому элементу мемо-таблицы; кроме этого, мы показали, что подобное предсказание возможно лишь при локальном запоминании и только для определенного класса вырожденных мультилинейных функций, а также для тех функций, для которых программист может создать соответствующий регулировщик таблиц. Однако в случае ленивого запоминания, если сборщик мусора обнаруживает, что объект, идентичный аргументу элемента мемо-таблицы, может быть удален, поскольку ссылки на него отсутствуют, то и этот элемент больше не нужен и поэтому также может быть удален сборщиком мусора. Однако по определению все аргументы, имеющие соответствующие элементы в доступных мемо-таблицах, также являются доступными, и поэтому стандартный сборщик мусора, сохраняющий все доступные структуры данных, не может обрабатывать их. Вследствие этого он должен игнорировать ссылки элементов мемо-таблиц на хранящиеся аргументы, но, кроме этого, остаются трудности со ссылками от элементов мемо-таблицы на хранящиеся результаты. Если аргумент остается для хранения, то и соответствующий ему результат также должен быть сохранен, так чтобы он мог быть найден, когда мемо-функция будет применена к этому аргументу, и наоборот, если аргумент удаляется, то и ссылка на его результат тоже должна быть устранена. [26]
Стоимость таких проверок высока, а выполняться они должны при каждом вызове мемо-функции, возможно, несколько раз по мере роста мемо-таблицы. Проблема усугубляется тем, что применение сложных методов для обработки составных структур затруднительно, например использование хэширования для оптимизации поиска в мемо-таблицах или для формирования этих таблиц в виде упорядоченных деревьев. В любом случае получение необходимой и уникальной характеризации структуры данных требует создания рекурсивной функции. Другим недостатком этого вида запоминания является то, что при проверке на равенство необходимо полное вычисление всех аргументов, и поэтому мы ограничены вычислениями аппликативного порядка. [27]
Если же, однако, power будет мемо-функцией, то второй ее вызов сведется к простому поиску только что полученного результата в мемо-таблице, а последующие вызовы будут не нужны. Таким образом будет сделано лишь 1 п вызовов. [28]
Ниже в этой главе мы рассмотрим, как эти недостатки могут быть в большой мере исправлены, что позволит осуществить успешную реализацию. Затруднения с составными аргументами можно преодолеть, если воспользоваться ленивыми мемо-функ-циями [48], - с этого мы начнем обсуждение; потом мы рассмотрим способ контроля роста мемо-таблиц. И наконец, мы обсудим некоторые проблемы, возникающие при сборке мусора в мемо-таблицах. [29]
Часто программист способен дать такую информацию, которую компилятор без труда соответственным образом закодирует. Более того, в отличие от других оптимизаций, осуществляемых программистом, любая ошибочная стратегия удаления может повлиять не на корректность программы, а только на ее эффективность, поскольку при необоснованном удалении элементов мемо-таблицы может возникнуть необходимость в их повторном пересчете. [30]