Размещение в памяти небольших объектов

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

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

Для работы с динамической памятью в языке С++ есть два основных инструмента- операторы new и delete. Проблема заключается в том, что эти операторы универсальны и неэффективно работают при динамическом размешении маленьких объектов. Чтобы проиллюстрировать, насколько плохо они работают с маленькими объектами, заметим, что некоторые стандартные распределители динамической памяти иногда работают на порядок медленнее и занимают в два раза больше памяти, чем распределители, описанные в этой главе.

"Источник всех бед - ранняя оптимизация", - заявил Дональд Кнут (Donald Knith). С другой стороны. Лен Латганци (Len Lattanzi) утверждает, что "поздняя пессимизация не приводит ни к чему хорошему". Пессимизация только на один порядок во время выполнения профаммы таких основных объектов, как функторы, интеллектуальные указатели или сфоки, легко может уфобить весь проект. ("Пессимизация" - генерирование профаммы, которая заведомо хуже ее оптимизированного варианта. - Прим. ред.) Выгоды, которые приносит дешевое и бысфое динамическое распределение памяти для маленьких объектов, могут быть огромными, поскольку она позволяет применять совершенные технологии, не опасаясь значительных потерь производительности. Эти рассуждения являются достаточно сильным побудительным мотивом для разработки способов оптимального размещения маленьких объектов в динамической памяти.

Авторы многих книг, посвященных языку С++, например, Саттер (Sutter, 2000) и Мейерс (Meyers, 1998а), упоминают о полезности разработки своих собственных специализированных средств распределения памяти. Мейерс, описав какую-либо реализацию, оставляет некоторые детали "в виде упражнения для самостоятельной работы", а Сатгер отсылает читателей к "учебникам по С++ или профаммированию вообще". Издание, которое вы держите в руках, не претендует на то, чтобы стать вашей настольной книгой. Однако в

этой главе мы опустимся на уровень "железа" и реализуем свой собственный распределитель памяти в соответствии со стандартом языка С++ в мельчайших деталях.

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

4.1. Стандартный механизм распределения динамической памяти

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

Кроме этого, универсальность механизма распределения памяти в языке С++ стала причиной крайней неэффективности использования памяти, выделяемой для маленьких объектов. Стандартный распределитель управляет кучей, что часто вынуждает его занимать дополнительную память. Обычно вспомогательная память занимает от 4 до 32 байт для каждого блока, выделенного с помощью оператора new. При выделении блоков памяти размером 1024 байт дополнительные затраты незначительны (от 0,4 % до 3 %). Однако, если возникает необходимость разместить в памяти объекты размером 8 байт, дополнительные затраты памяти составят от 50 % до 400 %. Эти числа достаточно велики, чтобы заставить профаммиста задуматься о том, как ему разместить в памяти большое количество маленьких объектов.

В языке С++ динамическое распределение памяти имеет большое значение. Динамический полиморфизм часто ассоциируется именно с динамическим распределением памяти. Такие стратегии, как "идиома Pimple" (the pimple idiom) (Smter, 2000), изначально ориентируются на распределение динамической, а не статической памяти. (Название идиомы представляет собой аббревиатуру выражения "а Pointer to the IMPLEmentation class" - "указатель на класс реализации". - Прим. ред.)

Следовательно, низкая производительность стандартного механизма распределения памяти делает его камнем преткновения на пути создания эффективных профамм на языке С++. Бывалые профаммисты на С++ инстинктивно избегают конструкций, ориентированных на использование динамической памяти, поскольку они по опыту знают о связанных с этим дополнительных затратах. Таким образом, у профаммистов возникает некий психологический барьер.

4.2. Как работает стандартный механизм распределения динамической памяти

Изучать тенденции, связанные с использованием памяти, как показал Кнут (Knuth, 1998), очень интересно. Он разработал много основных стратегий распределения памяти, а после опубликования его работы их появилось еще больше.

Как работает стандартный механизм распределения памяти? Он управляет пулом байтов и может выделять из него участки памяти любого размера. В качестве вспомогательной структуры может применяться простой блок управления.

struct MemControlBlock {

std::size t size ; bool available ;

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

Во время запуска программы в начале пула располагается только одна структура MemControl Block, которая управляет всей памятью как одним большим участком. Это - корневой блок управления, который никогда никуда не перемешается. На рис. 4.1 показана схема распределения памяти для пула, имеющего объем 1 Мбайт, в момент запуска программы.

available :true size: 1048571

-1байт-

-4байт-

-1048571 байт-

-1048576 байт (1 Мбайт)-

Рис. 4.1. Карта распределения памяти в момент запуска программы

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

Каждое удаление объекта из памяти влечет за собой новый линейный поиск блока, предшествующего удаляемому, и последующее выравнивание его размера.

Как видим, эта стратегия не слишком эффективна с точки зрения затрат времени, однако дополнительные затраты памяти довольно малы - в каждом блоке нужно разместить две переменные типа size t и bool соответственно. Иногда можно даже сэкономить один бит на каждой переменной типа size t, использовав его для размещения переменной avail аЬ1е . Сжатая структура MemControl Block имеет следующий вид.

код, зависящий от платформы и компилятора

struct MemControlslock

std::size t size : 31; bool available : 1;

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