Мемо-таблица

Cтраница 3

Обращение указателя при обнаружении немаркированного аргумента. а - элемент мемо-таблицы с немаркированным аргументом. б - после обращения указателя.| Цепочка аргументов с неразделяемым немаркированным аргументом. [31]

Первый указатель, хранящийся в каждой ячейке, может быть особым образом помечен ( если есть свободный бит), так чтобы можно было избежать косвенных обращений при проверке того, указывает ли данная ячейка на ячейку типа entry. В конце фазы маркирования все достижимые элементы, аргументы и результаты будут промаркированы, а фаза сканирования будет выполняться в нормальном режиме и лишь с тем дополнением, что в списках ( или деревьях) мемо-таблиц будут удаляться все ячейки, указывающие на немаркированные ( удаленные) элементы. Любой такой элемент мемо-таблицы будет некорректен из-за обратимости указателей и, разумеется, не может уже потребоваться. [32]

Когда Г применяется к аргументу, который эквивалентен предыдущему, то unique обеспечивает то, что ленивая мемо-функ-ция f будет применена к соответствующим идентичным аргументам, так что повторных вычислений не произойдет. Разумеется, недостатки этой схемы те же, что и в любой другой схеме, поддерживающей мемо-функции, а именно: полное вычисление аргументов, неэффективность в сравнении величин аргументов ( unique является рекурсивной функцией) и повышенная трудность управления размером мемо-таблицы. [33]

Если сборщик мусора просматривает мемо-таблицу и если он еще не достиг какой-либо из хранящейся в ней структуры аргументов, он не знает, какие из хранящихся структур результатов стоит сохранить, за исключением тех, которые уже были отмечены как достижимые до обращения к этой мемо-таблице. С другой стороны, некоторые структуры данных, включая аргументы, имеющие свои элементы в мемо-таблице, могут быть доступны только через структуры результатов, хранящиеся в мемо-таблице. Поэтому просто отложить проверку мемо-таблиц до конца сборки мусора было бы недостаточно. Это может привести к тому, что некоторые элементы мемо-таблицы будут удалены, причем их аргументы будут оставаться доступными для мемо-функций через результат, хранящийся в нестертой ячейке, находящейся ниже в таблице. [34]

Если не предпринимать никаких действий для удаления неиспользуемых элементов из мемо-таблицы, то ее наращивание будет происходить непрерывно; при применении ассоциированной с ней функции к новому аргументу к ней будет прибавляться новый элемент. Именно эти излишние затраты памяти помешали запоминанию сразу же стать широко используемым видом оптимизации; в последнее время в решении этой проблемы достигнуты некоторые успехи. Существуют два пути контроля роста мемо-таблицы. Первый состоит в расширении функ-ций сборщика мусора для восстановления неиспользуемых элементов мемо-таблицы; мы обсудим это в разд. [37]

В этом аспекте запоминание является более практически пригодной альтернативой, нежели преобразование нелинейных функций. Регулировщик таблиц находит один удаляемый эле мен г для каждого набора предикатных преобразователей, которые имеют максимальный общий множитель, причем каждый совместимый набор будет иметь ровно один член, являющийся одновременно наибольшим общим множителем этого набора и его LCC. Таким образом, один элемент мемо-таблицы будет удален для каждого предиката преобразователя, что вполне желательно с точки зрения контроля за размером таблицы, но фактически является несущественным, так как при этом мемо-функция никогда не сможет быть вновь применена к тому же аргументу. [38]

При полном запоминании не представляется возможным предсказать для данной функции, что она никогда не будет использовать аргумент, равный тому, который уже соответствует некоторому элементу мемо-таблицы; кроме этого, мы показали, что подобное предсказание возможно лишь при локальном запоминании и только для определенного класса вырожденных мультилинейных функций, а также для тех функций, для которых программист может создать соответствующий регулировщик таблиц. Однако в случае ленивого запоминания, если сборщик мусора обнаруживает, что объект, идентичный аргументу элемента мемо-таблицы, может быть удален, поскольку ссылки на него отсутствуют, то и этот элемент больше не нужен и поэтому также может быть удален сборщиком мусора. Однако по определению все аргументы, имеющие соответствующие элементы в доступных мемо-таблицах, также являются доступными, и поэтому стандартный сборщик мусора, сохраняющий все доступные структуры данных, не может обрабатывать их. Вследствие этого он должен игнорировать ссылки элементов мемо-таблиц на хранящиеся аргументы, но, кроме этого, остаются трудности со ссылками от элементов мемо-таблицы на хранящиеся результаты. Если аргумент остается для хранения, то и соответствующий ему результат также должен быть сохранен, так чтобы он мог быть найден, когда мемо-функция будет применена к этому аргументу, и наоборот, если аргумент удаляется, то и ссылка на его результат тоже должна быть устранена. [39]

Описанный выше вид локального запоминания не позволяет осуществлять динамическое управление мемо-таблицами, при котором по мере добавления новых элементов таблицы устаревшие и ненужные элементы удаляются из нее, причем полного разрушения таблицы при этом не происходит. Это позволяет сохранять размер мемо-таблиц в разумных контролируемых пределах; во многих случаях это небольшое фиксированное число элементов. Мы сосредоточим наше внимание главным образом на локальном запоминании, при котором мемо-таблица создается для каждого применения верхнего уровня мемо-функ-ции, а запоминание происходит лишь для применений этих функций, входящих в описывающие ее уравнения, а также в уравнения других функций, вызываемые из них. Некоторая ограниченность подобного подхода проявляется, например, в том, что два применения верхнего уровня функции fib ( 20) будут выполняться за линейное время каждая при локальном запоминании в то время, как второе применение может быть выполнено за постоянное время при простом поиске и нахождении своего результата в мемо-таблице первой функции, если эта таблица не была разрушена. Далее мы увидим, что при этом ограничении компилятор способен во многих случаях автоматически определять стратегию динамического удаления путем простого грамматического анализа выражения, описывающего мемо-функцию. [40]

Ниже в этой главе мы рассмотрим, как эти недостатки могут быть в большой мере исправлены, что позволит осуществить успешную реализацию. Затруднения с составными аргументами можно преодолеть, если воспользоваться ленивыми мемо-функ-циями [48], - с этого мы начнем обсуждение; потом мы рассмотрим способ контроля роста мемо-таблиц. И наконец, мы обсудим некоторые проблемы, возникающие при сборке мусора в мемо-таблицах. [41]

Здесь обеспечивается семантика нормального порядка, поскольку аргументы не вычисляются перед тем, как будут подставлены в тела функций, применяемых к ним, а нормальные формы ( СЗНФ) являются либо лямбда-абстракциями с конструктором lam, либо применением идентификатора с конструктором id к произвольному числу ( включая нуль) аргументов. Хотя выражение в аргументе не вычисляется до тех пор, пока его значение не потребуется в теле примененной лямбда-абстракции, оно будет вычисляться вновь и вновь для каждого его вхождения в тело абстракции. Однако если eval является ленивой мемо-функцией, то адрес и значение вычисленного выражения аргумента будут храниться в мемо-таблице и при необходимости значение просто отыскивается в этой таблице. Таким образом запоминание обеспечивает реализацию вызова по необходимости с помощью функционально определенного интерпретатора с семантикой вызова по имени. [43]

Рассмотрим простую систему, в которой все ячейки, предназначенные для хранения составных данных, содержат поля для двух указателей и метки, указывающие на их тип. Предположим, что мемо-таблица имеет вид списка элементов и что головная ячейка имеет тип memo table. Поскольку ячейки состоят лишь из двух указателей и метки, то список мемо-таб-лицы будет представлен как бтдельная структура, в которой поле первого указателя будет связывать элементы списка, а второго - указывать на ячейку типа entry, представляющую вход мемо-таблицы. На практике более подходящей структурой было бы - двоичное дерево благодаря дополнительному полю ячейки-указателя, так как в противоположном случае для каждой вершины было бы необходимо иметь две связанные ячейки. Эффективность также можно увеличить, если бы элементы мемо-таблицы были объединены в ячейки, образующие список или древовидную структуру мемо-таблицы вместо необходимости осуществлять косвенный доступ к ним, а в практических реализациях использовались бы ячейки переменного размера; в этом случае указателей было бы четыре или для древовидной мемо-таблицы - пять. [45]

Страницы: 1 2 3 4