Доброго времени суток, уважаемые подписчики.
Сегодняшний выпуск будет посвящён созданию алгоритма рационального использования памяти. Тема эта напрямую связана с нашим проектом: игрой. Но, несмотря на это такой шаг (поиск наилучшего алгоритма работы с памятью) должен иметь место в каждом достаточно большом проекте. В нашем проекте нам нужно будет постоянно загружать и выгружать объекты. Информация об одном объекте может занимать от 8 до нескольких тысяч байт. Но если мы будем распределять объекты в памяти хаотично (нужен объект - выделяем нужную ему память), то дефрагментация памяти может обернуться огромной проблемой. Дело в том, что Windows всегда выделяет кусок, кратный 64 килобайтам, то есть даже если нам нужно 3 байта, то мы получаем в распоряжение 64 Кб, но не используем их... Я считаю, что если нам нужно вместить как можно больше информации в наименьшее кол-во памяти, то такие потери нам не по карману. Выход из этой проблемы я вижу в создании менеджера памяти, функции которого должны вызываться вместо API системы. Он же будет выделать по 64 КБ памяти и распределять её кусочки на нужды програмы. Единственная проблема это то, что 64 Кбайтные куски памяти не всегда будут идти друг за другом, поэтому для выделения блоков памяти больше 64 Кб всё равно придётся использовать системные функции, но в нашем проекте, я думаю, мы не встретимся с подобными проблемами. Менеджер памяти должен быть "настроен" на работу с определённым проектом, так как во многих ситуациях это даст прирост производительности и уменьшит используемую память.
Приступим к "настройке" менеджера памяти под 3D мотор (3D engine). Стоит заметить, что так как мы будем иметь дело с объектами, нам не нужно будет сохранять размер кусков памяти.
1. Если объекты будут разбросаны хаотично, то, при выводе некоторой их части на экран, нам надо будет указывать процедуре вывода указатели на все выводимые объекты. А если объектов будет 500, то указатели на объекты займут столько же места, что и сами объекты, причём если надо будет удалить объект, то надо будет кучу адресов сдвигать в этой очереди объектов... Я вижу два выхода из этой ситуации, либо поставить объекты в "комнатах" в рад в памяти(подразумевается определённое пространство, где эти объекты находятся, так же объекты разбиты на "предметы" - подразумевается несколько объектов, вместе образующих какой-то предмет, эти понятия просто придуманы мной для экономии времени и понятности объяснения комната>предмет>примитивы), но тогда пропадает возможность убрать какой-либо предмет из поля вывода и повышается риск фрагметированности памяти. Второй выход кажется мне более приемлемым, в каждом объекте имеется указатель на следующий объект и программа обрабатывает объект за объектом, кроме объектов-"примитивов" (объект содержащий простую фигуру) надо создать объекты комнат и предметов. Они, помимо указателя на следующий элемент цепочки, будут содержать указатель на цепочку объектов. Зачем всё это? Приведу простой пример, у нас есть объект комнаты, содержащий указатель на цепочку предметов, в цепочке два предмета, предмет1 имеет указатель на следующий предмет и на цепь примитивов. Предмет2 содержит указатель на другую цепь примитивов. Что делает процедура вывода объектов на экран? Она получает указатель только на комнату, от комнаты она получает указатель на предмет1, от него она получает указатель на цепь примитивов, и выводит их, далее она возвращается к предмету1, получает указатель на предмет2 и выводит его примитивы. Допустим нам надо запретить вывод предмета1. Мы просто записываем в комнату указатель на предмет2. Теперь предмет1 не выполняется! Надеюсь понятно.
2.Дефрагментация. Даже если мы поступим так, как было описано в первом пункте мы может столкнуться с проблемой фрагментации. Приведу пример:
0 - пустое место, 1 - примитивы первого предмета(5), 2 - примитивы второго предмета(5), 3 - примитивы третьего предмета(6).
Начальное состаяние:
-000000000000-
-************-
Добавляем примитивы первого и второго предметов:
-111112222200-
-----------**-
Убираем примитивы первого предмета:
-000002222200-
-*****------**-
Добавляем третий предмет:
-333302222233-
-----*--------
И это мы получим при достаточно совершенной системе. Первым решением должно стать решение о выравнивании: все объекты, вне зависимости от их типа, должны занимать 128 байт (далее будет описано, почему так много). Это во-первых систематизирует загрузку объекта в память, во-вторых даёт богатые возможности к дефрагментации памяти, так как из-за одинакового размера блоков на освободившееся место всегда может быть записан любой другой блок!
3.Почему же именно 128 байт? для оптимальности работы размер должен быть степенью двойки, а 64 слишком мало, 256 - много. Структура должна содержать следующие пункты:
| смещение | длинна | имя | описание |
| 00h | 04h | type | Тип объекта |
| 04h | 08h | flags | Аттрибуты объекта |
| 0Ch | 08h | name | Имя объекта |
| 14h | 04h | next | указатель на следующий объект |
| 18h | 04h | last | указатель на объект-родитель или предидущий объект |
| 1Ch | 04h | ???? | пока не знаю, на всякий пожарный |
| 20h | 60h | ???? | дальнейшая информация зависит от типа объекта(вершины, координаты текстур...) |
Думаю, к следующему выпуску будет готова основа менеджера памяти, тогда можно будет обсудить и построение менеджера, а пока жду от вас критику моего представления менеджера памяти..
Другой очень важный вопрос в связи с программированием 3D ядра (мотора) это хранение объектов на винчестере (или где угодно). В нашем случае есть две возможности:
- Делаем свой формат
- Используем имеющийся формат
Думаю, подойдёт нам только второй вариант. Нам нужно найти такой формат, с которым работают 3D редакторы (надо же нам как-то делать объекты, которые будет выводить мотор). Я лично знаком только с форматом 3DS и жду ваших предложений. Следует иметь ввиду, что нам нужно описание формата, чтоб суметь с ним работать!
На сегодня это всё. Если есть какие вопросы, пишите. Пишите на Dark_Lord@RusFAQ.ru или Dark_Lord@land.ru.
Или свяжитесь со мной по ICQ, мой номер 126222874!