Менеджер памяти (Allocator) для С++

Исходный текст аллокатора можно взять тут: allocator.zip

Стандартный аллокатор из C++ runtime library - не очень эффективная штука. Он унаследован из мира plain C и поэтому расчитан на несколько другой стиль использования, нежели принят в С++. Он расчитан на отностительно редкий захват крупных блоков. В то время как в С++ принято создавать и убивать тысячи мелких объектов в секунду. Поэтому стандартный аллокатор имеет две существенные проблемы: 

• он медленный,
• он сильно фрагментирует память.

Попробуем это исправить. :-)




Стандартный аллокатор хранит список блоков - свободных и выделенных, и при выделении памяти этот список приходится просматривать в поисках подходящего блока. Отсюда тормоза. 

Фрагментация памяти также имеет простое объяснение: если освобождается блок в середине хипа, дырка часто занимается блоками меньшего размера:

В данном примере после удаления блока B, образовавшееся свободное место было занято при следующей аллокацией блоком D меньшего размера. В результате при следующей попытке аллокации, свободного блока не окажется, и будет использовано свободное место в конце хипа. 

Предлагаемая библиотека призвана решить обе проблемы встроенного аллокатора CRTL (stands for "C runtime library"). 

Наш аллокатор будет вклиниваться между приложением и стандартным аллокатором CRTL. При этом запросы на выделение больших (более 8 килобайт) блоков будут передаваться непосредственно в malloc(), поскольку такие аллокации редки и их можно доверить стандартному аллокатору. 

Запросы на меньшие блоки (от килобайта до 8 килобайт) будут также удовлетворяться из хипа crtl, но при освобождении такого блока мы не будем возвращать его системе. Вместо этого мы будем связывать эти блоки в несколько пулов, организованных под блоки определенных размеров. Это позволит ускорить повторное выделение памяти, так как блок будет просто возвращаться из первого элемента связанного списка. Такая аллокация так же быстра, как new в Java. 

Кроме того, пулированный аллокатор не создает фрагментацию памяти, поскольку резервирует освобожденную память и использует ее только для выделения похожих по размеру блоков. 

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

Для выделения совсем маленьких блоков памяти (менее килобайта) используется страничный пулированный аллокатор, который захватывает память постранично – в одной странице хранятся от четырех до 256 блоков. Это значительно сокращает количество обращений к внешнему менеджеру памяти и ускоряет работу приложения. 

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

Но есть целый ряд приложений, которые от применения этого аллокатора выиграют не только по скорости но и по памяти. 

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

Ресурсоемкие приложения с очень длинным циклом – демоны и сервисы. Поскольку все необходимые ресурсы будут ими захвачены в самом начале работы и в дальнейшем динамика аллокации стабилизируется. 

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

Частично к этому виду приложений можно отнести интерактивные GUI-приложения. Но в них, как правило, время активности и неактивности строго детерменировано. Можно считать что приложение неактивно, кода пользователь переключается на другое приложение. 

Для этих проблемных приложений существует техника сброса пулов. При переходе в неактивное состояние приложение заставляет менеджер памяти освободить все пулы и страницы, целиком состоящие из неиспользуемх блоков. 

Реализация менеджера памяти

Менеджер памяти описан в пространстве имен Memory. Приложению доступны три функции 

void *Memory::allocate (size_t size);
void Memory::deallocate(void* ptr);
void Memory::flush();

Кроме того операторы new, new[], delete, delete[] переключаются на использование Memory::allocate и Memory::deallocate. 

Запрос на выделение памяти попадает в аллокатор одного из трех видов 

• блоки больше восьми килобайт выделяются в хипе crt,
• блоки от одного килобайта до восьми выделяются одним из пуллированных аллокаторов,
• блоки менее килобайта выделяются страничными аллокаторами.

Тип аллокатора	покрывает диапазон от	до (байт)	с шагом (байт)
Страничный пул	0	192	16
Страничный пул	256	1024	64
Пул	1280	3072	256
Пул	4096	8192	1024

Естественно, аллокатором поддерживается new_handler, bad_alloc exception и nothrow. 

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

В случае, если единственным сбрасываемым ресурсом являются пулы аллокатора, в приложении можно сделать: 

std::set_new_handler(Memory::flush);

Каждый аллоцированный блок имеет четырехбайтный заголовок, из которого аллокатор использует только один байт. Остальные три байта доступны приложению для хранения произвольных пользовательстких атрибутов блока. Например, для отладки, или для тэгов типизации, или для управлением времени жизни объектов - для счетчиков или флагов сборщика мусора. Для доступа к этим пользовательским данным существует две функции: 

size_t getUserData (void* ptr);
void   setUserData (void* ptr, size_t value);

где ptr - адрес полученный из new, а value - 24-битное число.