[Урок] Организация кучи (динамической памяти) на основе одномерного статического массива

Kailo

Участник
Сообщения
168
Реакции
755
В этой статье речь пойдет о организации динамически выделяемой памяти на основе глобального одномерного статического массива реализуемой в виде проекции на массив самодробящегося двусвязного списка, кэшируемого не сбалансированным двоичным деревом поиска, узлы которого находятся в той же памяти в виде реверсивно расположенного от конца памяти динамически расширяемого массива с предвыделением памяти.
Ну что же, ничего не понятно? Давайте разбираться!

Память
Первым шагом для организации кучи, нам надо откуда-от взять память. С этой задачей нам успешно помогают справиться массивы.
Сначала нам для понимания процесса стоит вспомнить организацию виртуальный памяти плагинов.
Глобальные массивы и переменные располагаются в блоке данных, размер которого определяется кол-вом и размером объявленных переменных и массивов.
Аргументы, локальные переменные и массивы располагаются в блоке стека. Динамические локальные массивы, и временные переменные располагаются в блоке кучи (той что у виртуальной памяти плагинов).
То свойство, что памяти под глобальные массивы увеличивается с увеличением размера массива позволяем нам создать массив почти неограниченного размера в разумных пределах, хоть размером пару тысяч, хоть пару миллионов.
Таким образом основой нашей кучи будет являться память выделенная в блоке данных под наш одномерный большой размер. И в то же время массив статичный,
т.к. его размер определяется при компиляции и не может быть изменен во время работы плагина. Так что нужно будет заранее выделить достаточно памяти.
PHP:
any heap_space[2000000];
Я предпочитаю выделять память в степенях 2: 16384, 65536, 131072, 524288 и т.д.

Адресация
Адресами нашей кучи будут являться как очевидно индексы ячеек нашего массива. Т.е. для массива размером N, адреса от 0 до N-1.
Функция выделения памяти будет возвращать адрес начала блока памяти A. Соответственно для доступа к ячейкам выделенной памяти нужно будет использовать адреса A+0, A+1, A+2 и т.д.
Т.к. наш массив имеет тип данных any, размер каждой ячейки 4 байта, и адресация соответственно не байтовая, а в ячейках (англ. cell).

Разделение памяти, проекция двусвязного списка
Первым делом стоит узнать или вспомнить о базовой структуре данных используемой в программировании - (связных) списках (англ. list) Википедия:Связный список.
А в частности о Двусвязном списке (двунаправленный связный список) Випипедия:Двусвязный список.
В классическом представлении мы можем иметь N распределенных в памяти объектов, которые связанны указателями друг с другом в определенной последовательности.
Каждый элемент двусвязного списка будет иметь следующие свойства:
PHP:
prev; // ссылка на предшествующий элемент списка
next; // ссылка на следующий элемент списка
data; // ссылка на данные или сами данные как часть элемента
"Что такое двусвязный список я понял, но зачем он нам?"
Двусвязный список будет использоваться для разделения цельного блока памяти на блоки поменьше, разной длины.

О том как это будет делаться, давайте лучше разберемся на следующем примере.
Во-первых определим полную структуру элемента списка.
Нам надо хранить две ссылки на элементы-соседи. Данные будем считать частью самого блока.
В качестве данных нам нужно хранить следующее свойства блока:
Размер блока, информация о том занятый или свободный блок (его статус).
Получим следующую структуру элемента списка:
PHP:
int prev;
int next;
int status;
int size;
// А далее идет массив переменных размера size, после которого будет следующий блок списка, ссылка на который указана в next.
int data[size];
Возьмем простой пример. Блок памяти в 100 ячеек разделим на два элемента двусвязного списка.
PHP:
any heap[100];
// Первый элемент списка будет начинаться от 0
// Скажем, что размер памяти (size) первого блока будет 20, а остальное оставим второму элементу списка
// Т.к. адреса начинаются от 0, в качестве "нулевого адреса", который указывает в никуда, используем -1.
// В качестве статусов, используем 0 для свободного элемента и 1 для занятого.
// Тогда если записывать проекцию содержимого нашего массива, получим:
// (комментарием перед значением обозначим индекс ячейки массива, наши адреса)
heap = {
/* 0 */ -1, // prev
/* 1 */ 24, // next
/* 2 */ 0, // status
/* 3 */ 20, // size
/* 4 */ ?, // data[0]
/* 5 */ ?, // data[1]
/* 6 */ ?, // data[2]
...
/* 23 */ ?, // data[19]
// Здесь заканчивается первый элемент и начинается второй
/* 24 */ 0, // prev
/* 25 */ -1, // next
/* 26 */ 0, // status
/* 27 */ 72, // size, первый элемент занял 24 ячейки, и еще 4 занято на заголовок второго элемента, тогда из 100 нам остается 72.
/* 28 */ ?, // data[0]
/* 29 */ ?, // data[1]
...
/* 99 */ ?, // data[71]
}
В тоже время мы можем объединить два соседних свободных блока в один блок побольше
PHP:
heap = {
/* 0 */ -1, // prev
/* 1 */ -1, // next
/* 2 */ 0, // status
/* 3 */ 96, // size
/* 4 */ ?, // data[0]
/* 5 */ ?, // data[1]
...
/* 99 */ ?, // data[95]
}
Как мы видим в первом примере у первого блока нет предшествующего элемента, а в второго последующего за ним.
Для того, чтобы в будущем облегчить себе написание алгоритмов, сделаем по краям два блока нулевого размера имеющих только заголовок, которые будут считаться всегда занятыми.
PHP:
heap = {
/* 0 */ -1, // prev
/* 1 */ 4, // next
/* 2 */ 1, // status
/* 3 */ 0, // size
// ----------------------
/* 4 */ 0, // prev
/* 5 */ 96, // next
/* 6 */ 0, // status
/* 7 */ 88, // size
/* 8 */ ?, // data[0]
/* 9 */ ?, // data[1]
...
/* 95 */ ?, // data[87]
// ----------------------
/* 96 */ 4, // prev
/* 97 */ -1, // next
/* 98 */ 1, // status
/* 99 */ 0, // size
}
Теперь мы знаем что элементы 0 и 96 будут граничными в нашей памяти, а изначально между ними будет один большой свободный блок (далее элементы двусвязного списка будет называть блоками памяти).
Так же мы можем организовать циклы по всем блокам памяти в прямом или обратно порядке.
Область допустимых адресов, учитывая заголовки блоков и начальный и конечный блоки теперь становится от 8 до 95 в случае массива на 100, или при размере массива N, а размера заголовка блока в BHS,
начало будет BHS * 2, а конец N - BHS.
Т.к. теперь 0 не может быть адресом памяти, переданным пользователю в качестве блока выделенной памяти, он может быть использован им для обозначения нулевого адреса памяти.
В результате такой организации блоков памяти, мы получаем не полноценной двусвязный список (т.к. адреса блоков не распределены в памяти, а строго упорядочены друг за другом без пробелов между ними),
а проекцию двусвязного списка на нашу память.

Управления памятью
Как говорилось чуть ранее, изначально мы будем иметь 3 блока памяти, два краевых нулевого размера и один блок между ними включающий в себя всю свободную память.
Важной частью организации блоков памяти является их свойство дробления и соединения с поддержанием целостности двусвязного списка.
Будет две основных операции над блоками памяти: выделение памяти (дробление) и освобождение памяти (соединение).
Выделение памяти (дробление)
Изначально у нас один большой свободный блок памяти, и возникает ситуация, что нам нужно выделить память.
В зависимости от выделяемого размера может произойти 3 разных ситуации:
Пусть Sz размер выделяемой памяти, а Sp размер доступной свободной памяти в блоке.
1. Sz > Sp
У нас свободного места, меньше чем требуется. И к сожалению тут нам нечего поделать, массив у нас статичный,
и нам придется вызвать экстренную остановку работы плагина с соответствующей ошибке о нехватке места в нашей куче.
2. Sz = Sp
Запрашиваемое место точно по размеру блока, поэтому нам достаточно поменять статус у блока и вернуть адрес его памяти.
3. Sz < Sp
Запрашиваемое место меньше доступного. Вот тут может возникнуть пара исключающий моментов, о которых станет сейчас понятнее.
Сначала рассмотрим случай, когда выделяемое место значительно меньше доступного, к примеру доступно 88, а нужно выделить 10.
В этот момент реализуется свойство возможности дробления свободных блоков нашего списка на большее кол-во блоков.
Наш текущий свободный блок меняет статус на занятый и размер с 88 на 10, и после самого блока у нас остается еще 78 свободных ячеек памяти.
К ним на начале добавляется заголовок элемента списка в 4 байта, и остается еще 74 свободных ячеек памяти.
Остается лишь отредактировать ссылки соседних блоков, чтобы сохранить корректность связи в двусвязном списке.
Но, есть одна исключающая ситуация, когда оставшееся свободное место будет слишком мало, чтобы создать новый элемент списка.
Нам нужно 4 ячейки на заголовок и хотя бы одну еще как память. Если нас будет доступно менее 5 свободных ячеек, то мы должны
поступать как в предыдущем случае (2. Sz = Sp). К примеру, хоть и запрашивалось 10 блоков, было выделено 13.
В заголовке списка будет записано что ячеек памяти в блоке 13, хоть и по факту программой будет использоваться всего 10.
Это вынужденная и малая жертва памятью.
Так же в моей реализации памяти я сделал этот фактор настраиваемым. Можно установить необходимый минимальный размер у оставшегося куска свободной памяти,
потому что наличие кучи свободных кусочков памяти размером по 1-3 может негативно сказаться на скорости работы памяти, я поставил по умолчанию,
чтобы было свободно хотя бы 8 ячеек памяти, но можно в любой момент или вернуть на 1 или увеличить на желаемое кол-во.
Освобождение памяти (соединение)
Первым делом, когда игрок решил освободить блок памяти, его можно просто пометить свободным.
Но тогда в какой-то момент система не сможет найти достаточно большой свободный блок, поэтому нам надо соединять свободные блоки в более большие.
1. Если предыдущий и последующий блоки заняты.
В таком случае ничего уж не сделаешь, просто помечаем текущий блок свободным.
2. Если предыдущий блок свободен, а последующий занят.
В таком случае мы "удаляем" освободивший блок, а память его данных и заголовка приплюсовываем к памяти предыдущего блока.
3. Если предыдущий блок занят, а последующий свободен.
В таком случае мы "удаляем" последующий блок, и считаем его частью памяти освободившегося.
4. Если предыдущий и последующий блоки свободны.
В таком случае мы "удаляем" освободившейся и последующий блоки, присоединяя их память к предыдущему.
При этим действиях надо не забывать соответственно изменять ссылки между элементами списка, для сохранения его целостности.
В том числе, благодаря решению сделать по краям всегда занятые блоки, можно не тратить время на проверку существования блоков соседей,
т.к. их может не быть только у блоков с краю, а они никогда не будут освобождаться.

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

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

Двоичное дерево поиска
Для кэширования мы используем двоичное дерево поиска. Википедия:Двоичное дерево поиска
Элементы связываются таким образом, что операции вставки и удаления замедляются, а поиск ускоряется до логарифмической скорости от числа элементов дерева.
В дерево будут добавляться в качестве элементов (узлов) дерева, адреса только свободных блоков, что уже уменьшает кол-во элементов и ускоряет время выполнения алгоритма.
Давайте решать соответственно возникающие проблемы.
Где взять память под двоичное дерево?
Т.к. наша куча работать без двоичного дерева еще не может, нужно сделать особый алгоритм для работы памяти дерева.
Память двоичного дерева будет располагаться в конце памяти в краевом блоке который был ранее пустым.
Для этого мы задаем шаг выделения памяти, к примеру 100 ячеек памяти за раз.
Когда память инициализируется (создаются начальные элементы двусвязного списка на пустом массиве), мы изначально выделим 100 памяти.
Когда эти 100 памяти заполнятся, то мы опросим предшествующий нашему краевому блоку элемент, и если он представляет собой свободную память, отделим от него часть
в пользу нашего краевого блока, перемещая только лишь заголовок краевого блока на новую позицию. Если соседний блок не будет свободным,
к сожалению тут нам придется вызвать ошибку недостатка памяти.
Узлы бинарного дерева имеют связь ссылками между собой, поэтому их можно без проблем перемещать в памяти, обновляя нужны ссылки для сохранения работы дерева.
Поэтому, когда из дерева удаляется узел, который в памяти узлов находился не с левого края, то для того, чтобы памяти дерева выделялась справа налево без "дырок",
мы перемещаем крайний левые элемент на место удаленного, таким образом массив будет планомерно расти справа налево.
В какой-то момент, может оказаться так, что ранее выросший блок памяти под элементы дерева более не нужен такой большой, поэтому используется алгоритм уменьшения размера,
при условии освобождения 1,5 шагов свободной памяти.
К примеру, был размер 100, вырос до 200, а потом до 300. В какой-то момент кол-во узлов дерево начало уменьшатся и когда свободных элементов станет равное 1,5 шага выделения,
то мы уменьшим выделенное место на 100. Т.е. как только мы снизимся до 150, память сожмется с 300 до 200, а когда меньше 50, то вернется к начальным 100.

Узлы при вставке в дерево сразу сортируются по порядку размера, одинаковые по размеру сортируются по возрастанию адреса.
Таким образом при выделении памяти используется минимальный по размеру подходящий блок находящийся наиболее левее в памяти.
Узел дерева представляет собой следующую структуру:
Адреса узлов так же даются относительно всей памяти
PHP:
int value; // адрес блока памяти
int left; // адрес левого узла или 0
int right; // адрес правого узла или 0
int parent; // адрес родительского узла, или 0 у корневого узла
И теперь, для того, чтобы мы могли быстро перейти от свободного блока к узлу, мы добавляем в заголовок блока памяти свойство ref с адресом представляющего его узла в дереве.
А когда блок свободный, это переменная или не используется, или работает магическим числом. Т.е. мы записываем туда специальное значение, к примеру 0xAAAAAAAA, и когда происходит
освобождение занятого блока памяти, мы проверяем, что число равно нашему заданному, это повышает надежность работы памяти, чтобы случайно не был обработан свободный блок как занятый,
или вовсе память, которая не является блоком памяти, если таковой адрес по ошибке будет передан.

Что же, вот так это и работает.
 
Последнее редактирование:
Сверху