В наше время при разработке мало-мальски сложных проектов просто необходимо использовать динамическую память под переменные – уместиться в рамки предопределённых массивов и переменных стало просто невозможно, а динамические структуры, будь то связанные списки или деревья, являются сейчас неотъемлемой частью любой программы. В то же время стандартные средства выделения памяти в C/C++ отличаются некоторой медлительностью. Известно, что функции malloc / free очень плохо работают на большом количестве мелких переменных, а функция realloc вообще является ужасом для более-менее опытного программиста.
По этой причине зачастую приходится разрабатывать какой-либо собственный контроллер памяти, который бы удовлетворял запросам скорости, и не использовал слишком много памяти под собственные нужды.
Определим круг задач и требований, которые мы предъявляем к менеджеру памяти:
1. Интерфейс менеджера должен содержать две основных функции – выделение памяти и освобождение памяти.
2. Функция выделения памяти mc_alloc () должна получать на вход размер переменной, под которую необходимо распределить место.
3. Функция освобождения памяти mc_delete () должна освобождать память по указанному адресу.
4. Менеджер памяти должен обладать универсальностью – не должно существовать ограничений на объём выделяемой памяти.
5. Объём памяти, нужный для работы самого менеджера, должен быть минимален – желательно не более 10% от размера выделяемой памяти.
6. Необходимо достигнуть производительности минимум в два раза выше, чем контроллер памяти malloc/free в C/C++.
Существует множество подходов к распределению памяти системы. Мы не будем рассматривать их все – Интернет и так кишит информацией на эту тему. Лучше перейдём напрямую к самому алгоритму менеджера памяти MC Heappie.
Базовый подход
В основу положен алгоритм распределения памяти с битовыми картами. В данном случае вся область памяти разбивается на блоки фиксированного размера, и каждому блоку соответствует определённый бит карты, указывающий на состояние занятости блока. Разумеется, само применение битовых карт и вообще битовых полей в C является крайне нежелательным, поэтому используется массив байт – это позволяет организовать более удобное распределение памяти.
Удобство самих битовых карт состоит в том, что они очень хорошо оптимизируются под определённый размер переменной. В зависимости от размера одного блока памяти, можно подстроить битовую карту под работу с любым размером переменной. С другой стороны, запись слишком крупного значения в битовую карту потребует значительно больше времени, а запись небольшой переменной в крупный блок вызовет нежелательные потери памяти. Поэтому битовые карты в чистом виде редко применяются для универсальных менеджеров памяти.
Принцип работы
Вся память процесса (heap – англ. «куча») распределяется между небольшими битовыми блоками памяти – heappie (от англ. heap, «кучка», в дальнейшем, «хиппи»). Основу распределителя памяти составляет таблица корневых «хиппи». В данной таблице содержится список «хиппи», используемых для выделения памяти, алгоритм их работы и размер переменной, который может храниться в данном «хиппи». Кроме того, таблица содержит данные о размере каждого блока и количестве блоков, на которые разбита память.
В данной версии менеджера памяти таблица состоит из пяти корневых элементов. Конфигурация корневых «хиппи» приведена в таблице ниже.
Таблица корневых «хиппи»
| Мин. | Макс. | Блок | Размер | Поиск | Очистка |
|---|---|---|---|---|---|
| 0 | 4 | 4 | 32768 | Случайный | Нет |
| 4 | 256 | 8 | 32768 | Случайный | Нет |
| 256 | 4096 | 128 | 16384 | Случайный | Да |
| 4096 | 65536 | 1024 | 2048 | Последовательный | Да |
| 65536 | 524288 | 4096 | 1024 | Последовательный | Да |
Каждый корневой «хиппи» может ссылаться на дочерний блок, в целом формируя кольцо, либо быть одиночным блоком.
Принцип работы менеджера памяти
Каждый блок состоит из трёх основных частей. Вершина блока – это описание, содержащее ссылки на следующий блок и битовую карту, и поле free space, в котором указан размер свободного места в данном блоке. Центром блока является битовая карта памяти. Как уже говорилось ранее, она представляет собой массив байт, каждый из которых соответствует определённому блоку памяти «хиппи». Последним, и самым крупным элементом является собственно память, которая выделяется под переменные.
Алгоритм
Распределение памяти проходит по простому, но эффективному алгоритму.
После поступления запроса, функция последовательно просматривает таблицу корневых «хиппи», находя подходящий по размеру для данной переменной. Если таковой «хиппи» не был найден, то есть размер переменной больше размера самого крупного из них, вызывается встроенная функция Windows — HeapAlloc (GetProcessHeap (), 0, size) – которая выделяет место под крупную переменную средствами операционной системы. Мы вполне можем позволить себе использовать эту функцию в данном случае, так как выделение слишком крупного объёма памяти является редкой операцией. Если же подходящий «хиппи» найден, то вызывается функция выделения места в его пределах.
Прежде всего, проверяется свободное место, имеющееся в данном «хиппи». Если места недостаточно для этой переменной, то осуществляется переход в дочерний блок памяти, который создаётся на лету при необходимости.
Существует два способа поиска свободного места – последовательный и случайный. В первом случае поиск осуществляется с первого байта карты, во втором – со случайного места. Первый случай удобнее для распределения больших переменных, занимающих несколько блоков памяти, когда как второй гораздо лучше применим для выделения места под малые переменные, требующие один-три блока.
Поиск свободного места проходит скачками, соответствующими размеру переменной в блоках. Это вполне логично – если свободный участок не найден в пределах этого количества блоков, значит в этом промежутке недостаточно места под размещение переменной.
Как только при поиске попадается свободный участок, начинается «разрастание». Сначала указатель начала перемещается назад, до достижения первого занятого участка, затем указатель конца сдвигается вперёд, пока размер переменной не будет полностью распределён, или не будет достигнут конец свободной области.
Поиск проходит по алгоритму «first fit», то есть как только первое же свободное место под переменную найдено, цикл поиска прекращается.
Функция возвращает указатель на свободное место. Перед этим в битовой карте это место помечается как занятое. При этом соответствующие ячейки карты заполняются цифрой 2, в последнем блоке указывается 1. Это требуется для более удобного удаления переменной. Указатель корневого «хиппи» кольца после нахождения переменной устанавливается в текущий «хиппи», что помогает увеличить скорость поиска свободного места.
Этот алгоритм позволяет достигнуть скорости распределения памяти вдвое более высокой, нежели функция malloc.
Другая функция отвечает за очистку блока памяти.
При получении адреса переменной, просматривается вся таблица корневых «хиппи», и все кольца целиком, на предмет попадания адреса переменной в пространство данных «хиппи». Если поиск не дал результатов, предполагается, что переменная была выделена стандартной функцией HeapAlloc, и должна быть освобождена так же стандартной функцией HeapFree (GetProcessHeap (), 0, address).
Как только при поиске найден подходящий «хиппи», вычисляется смещение адреса переменной относительно начала блока, и данная память освобождается.
При освобождении памяти, цикл проходит по всем ячейкам начиная с данного смещения, и обнуляет их значения. Последней ячейкой при проходе всегда будет ячейка со значением, равным единице.
Если после освобождения памяти под переменную «хиппи» становится пустым, то он может быть удалён. Это зависит от выбранного алгоритма минимизации памяти для данного кольца. Пустые блока удобно удалять только в том случае, если они являются достаточно крупными. Значит, для мелких блоков процедура удаления не требуется.
Дополнительно
- Исходные коды менеджера памяти
- Демонстрационная программа (прилагается исходник)
Автор
Авторством данного алгоритма является Антон Резниченко aka AlterVision, altervision13@gmail.com , me@av13.ru , www.av13.ru . При публикации данного материала ссылка на автора обязательна.
© Антон /AlterVision/ Резниченко