А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 113

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 113)

Чаще всего по внешнему виду кода невозможно сказать, будет ли он активно использоваться при некоторых конкретных входных данных. Но даже если известен наиболее активно используемый код, размера наиболее быстрого кэша часто недостаточно для того, чтобы полностью разместить этот код. Поэтому приходится динамически обновлять содержимое кэша и использовать его только для хранения тех команд, активная работа которых наиболее вероятна в ближайшее время. Оптимизация с использованием иерархии памяти Стратегия хранения последних использованных команд в кэше обычно неплохо работает; другими словами, в общем случае прошлое — неплохой предсказатель будущего использования памяти.

При выполнении новой команды весьма высока 561 7.4. Управление кучей вероятность, что следующая за ней команда также будет выполнена. Это явление — пример пространственной локальности. Один эффективный метод повышения пространственной локальности состоит в том, что компилятор размещает базовые блоки гпоследовательностн команд, всегда выполняющихся одна за другой), которые, скорее всего, будут выполняться последовательно один за другим так, чтобы они оказывались в одной странице или по возможности даже в одной строке нэша.

Команды из одного цикла или одной функции также имеют высокую вероятность совместного выполнения.т Можно повысить временную и пространственную локальность обращения к данным в программе путем изменения схемы размещения данных или порядка вычислений. Например, программа, которая многократно обходит большие количества данных, выполняя каждый раз небольшие вычисления, неэффективна. Было бы лучше, если бы можно было перенести некоторые данные из медленного уровня иерархии памяти в быстрый (например, с диска в оперативную память) однократно и выполнить над ними все необходимые действия, пока они находятся на более высоком уровне.

Эта концепция рекурснвно применима к использованию данных на всех уровнях — в физической памяти, кэшах и регистрах. 7.4.4 Снижение фрагментации Когда программа начинает выполняться, куча представляет собой один непрерывный блок свободной памяти. Когда программа запрашивает и освобождает память, весь объем кучи разбивается на свободные и используемые блоки памяти, причем свободные блоки вовсе не образуют одной непрерывной области в куче. При каждом запросе на выделение памяти диспетчер должен поместить запрошенный блок памяти в свободный блок достаточно большого размера.

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

В таком случае легко может оказаться, что для очередного запроса на выделение памяти не найдется свободного блока достаточного размера, хотя суммарное количество свободной памяти может при этом во много раз превышать запрашиваемое. г Когда машина осуществляет выборку слова из памяти, можно относительно недорого осуществить одновременно лредвыборку нескольких последовательно идущих слов. Поэтому распространенной особенностью иерархии памяти является выборка блоков слов из каждого уровня памяти при обращении к нему. 562 Глава 7. Среды времени выполнения Методы наилучшего подходящего и следующего подходящего Мы снижаем фрагментацию, управляя методом размещения объектов в куче диспетчером памяти. Эмпирически было обнаружено, что хорошей стратегией минимизации фрагментации в реальных программах является выделение запрошенной памяти в наименьшем из блоков, размеры которых достаточно велики для такого выделения.

Такой алгоритм наилучшего подходян1его (Ьеи-61) стремится к сохранению больших свободных блоков для удовлетворения могущих последовать запросов на выделение большого количества памяти. Альтернативный метод первого подходян1его (бгзнб[) помещает объект в первый (с наименьшим адресом) свободный блок достаточного размера, тратя, таким образом, меньше времени на выделение памяти, но проигрывая в суммарной эффективности методу наилучшего подходящего. Дпя более эффективной реализации размещения методом наилучшего подходящего можно разделить блоки свободной памяти на кариамы (Ь1п) в соответствии с их размерами.

Одна из применяющихся на практике идей состоит в том, чтобы иметь побольше карманов малых размеров, поскольку обычно в программах создается гораздо больше мелких объектов, чем больших. Например, диспетчер памяти Ееа, использующийся в компиляторе ОХ1) С дсс, выравнивает все блоки на 8-байтовые границы. Имеется по одному карману для блоков каждого кратного 8 байт размера в пределах от 16 до 512 байт. Карманы больших размеров имеют логарифмические промежутки, т.е. минимальный размер каждого кармана вдвое больше предыдущего, а внутри каждого из этих карманов блоки упорядочены в соответствии с их размерами.

Всегда существует блок свободной памяти, который может быть расширен путем запроса у операционной системы дополнительных страниц. Этот блок — так называемый "пустынный" (и1дегпезз)— рассматривается 1.еа как карман наибольшего размера в силу его расширяемости. Такая схема позволяет легко найти наиболее подходящий блок. ° Если у диспетчера запрошен блок памяти малого размера и существует карман с блоками только этого размера, можно выделить в ответ на запрос любой блок из этого кармана. ° Если для данного размера кармана не существует, мы ищем карман, который включает блоки требуемого размера.

Внутри такого кармана можно использовать стратегию первого подходящего или наилучшего подходящего; т.е. мы либо ищем и выбираем первый достаточно большой блок, либо тратим немного больше времени и находим среди блоков достаточного размера наименьший. Заметим, что, если размер блока не совпадает с размером выделенной памяти, остаток блока, вообще говоря, следует поместить в карман с блоками меньшего размера. 563 7.4. Управление кучей ° Однако может оказаться, что целевой карман пуст или все блоки в таком кармане слишком малы для удовлетворения запроса. В этом случае поиск повторяется в кармане для следующего большего размера (или размеров). В конце концов мы либо находим блок, который можем использовать, либо достигаем "пустынного" блока, из которого можем получить требуемую память, возможно, воспользовавшись услугами операционной системы для получения дополнительных страниц памяти для кучи.

Хотя стратегия наилучшего подходя1цего и повышает степень использования памяти, она может оказаться не лучшей с точки зрения пространственной локальности. Обычно выделенные примерно в одно и то же время блоки имеют примерно одно время жизни и одинаковую схему обращений к ним. Их размещение рядом друг с другом в памяти повышает пространственную локальность программы.

Алгоритм наилучшего подходящего можно слегка модифицировать с учетом сказанного для ситуации, когда блок в точности совпадающего с запросом размера не найден. В этом случае используется стратегия следующего подходящего (пехьбг), которая пытается выделить память сначала в том блоке, который только что был разделен, если, конечно, в оставшейся свободной части блока достаточно памяти для удовлетворения запроса. Такая стратегия одновременно имеет тенденцию к повышению скорости выделения памяти. Управление свободной памятью и ее слияние Когда память, выделенная объекту, освобождается вручную, диспетчер памяти должен сделать соответствующий блок памяти свободным, чтобы он мог быть выделен снова.

В ряде случаев оказывается возможным объединить (слить) этот блок с соседним блоком в куче, чтобы получить блок большего размера. Преимущество такого подхода заключается в том, что всегда можно использовать большой блок для выделения малого количества памяти, но много малых блоков не могут хранить большой объект.

При наличии кармана для блоков одного фиксированного размера (как в диспетчере Ееа для малых размеров) может не иметь смысла объединять соседние свободныс блоки в блок удвоенного размера. В этом случае схема выделения и освобождения памяти предельно проста: достаточно иметь битовую карту, в которой каждому блоку кармана соответствует один бит. 1 указывает, что блок занят; Π— что блок свободен. При освобождении блока достаточно просто установить соответствующий бит равным О.

При выделении памяти выполняется поиск блока с нулевым битом, бит изменяется на 1 и данный блок возвращается в качестве выделенного. Если свободных блоков нет, можно запросить у операционной системы новую страницу памяти, разделить ее на блоки соответствующего размера и расширить битовый вектор. 564 Глава 7. Среды времени выполнения Ситуация усложняется при управлении кучей в целом, без разбивки на корзины, или при слиянии смежных блоков с переносом при необходимости получившегося блока в другую корзину.

Имеются две структуры данных, поддерживающих слияние смежных свободных блоков. ° Дескрипторы границ. С обоих концов каждого блока, как свободного, так и выделенного, хранится важная информация. На каждом конце блока имеется бит, указывающий, свободен ли данный блок. Рядом с этим битом указывается размер блока в байтах. ° Двухсвязньш встроенный список свободных блоков. Свободные (но не выделенные!) блоки связываются в дважды связанный список. Указатели этого списка хранятся в самих блоках, например, по соседству с дескрипторами границ с любой стороны.

Характеристики

Список файлов книги