О выделении памяти

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

p.s. за ошибки в тексте не бить, всё набранно в дикой спешке.

Глава 1

Простое выделение массивов. Идея крайне простая. Там известен тип нашего элемента, и мы знаем что будем выделять память для этого элемента, очень и очень часто. Простейший выход - выделять наши элементы большими массивами и раздавать ячейки этого массива по одному элементу. Ниже представлен исходик, который делает всё что нужно. Память выделяется страницами. Страницы всязываются в односвязанный список. Элементы которые надо удалить, просто занятся в односвязаный списко свободных элементов и отдаются обратно в тот момент когда нужны новые элементы. Есдиственный недостаток этой реализации, заключается в том что страницы которые больше не используются из памяти не удаляются. Зато можно удалить все выделенные элементы и страницы одним разом и часто в программах этого бывает достаточно.

Гарантируется выделение и освобождение памяти для одного элемента за время O(1), не считая затрат на редкое выделение страниц.

[memory1.cpp]

Глава 2

Дальнейшее усовершенствование идеи, которые позволяет вычищать из памяти лишние страницы. Самая главная проблема заключается в том что мы не можем определить адрес нашей страницы, имея только адрес удаляемого элемента. Для решения этой проблемы, рядом в каждым занятым элементом лежит его индекс в массиве (внутри страницы). Это позволяет сразу находить страницу в которой расположен наш элемент. Если элемент свободен, для индекс используется для создания списка свободных элементов. Глобального списка свободных элементов больше нет. Вместо этого каждая страница содержит список своих свободных элементов. Для простоты все страницы связанны в двухсвязанный кольцевой список. В отдельный кольцевой список связанны все страницы имеющие свободные элементы. Таким образом может быстро найти свободный элемент или удалить существующий. А так же удалить саму страницу, если все её элементы освободились. Каждая страница содержит счётчик своих свободных элементов. Небольшой недостаток заключается в том, что элементы кратные размеру, скажем 4 байта, нельзя выровнять в памяти на границу 4 байт. Точнее можно, потеряв немного памяти, сделав размеры индекса по 4 байта. Что в прочем небольшая потеря по сравнению со стандартным механизмом выделения.

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

Распределитель почти всегда выделяет элементы из того банка, в котором меньше всего свободных элементов. Это позволяет быстрее освобождать новые страницы.

Пример:

Распределение элементов. Элементы выделяются и освобождаются случайным образом, но в какой-то момент количетсво занятых элементов начинает падать. И алокатор в таких условиях делает всё, чтобы можно было быстрее освободить часть страниц:

[dump]
01: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx <bank list
02: xxxxxxxxxx.xx...xxxxxxxxxxxxxx.xx..xxx..xxxxxxx
03: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.xxxxxx
04: .xx..xx.x..x..x....x...xx..xxxx.x.xx.xx....x..x
05: ................................x.......x..xx..
06: ...................x...........................
07: xxxxxxxxx.xxxxxxxxxxxxxx.xxxxxxxxxxxxxxxxxxxxxx
08: ........x.......................x.......x......
09: ....x............................x.x...........
10: .xx.x.xxxxxxxxxxxxxxxxxxx.xxxxxxxxxxxxxxxxxxxxx <free list

Гарантируется выделение и освобождение памяти для одного элемента за время O(1), не считая затрат на редкие выделения и удаления страниц.

[memory2.cpp]

Глава 3

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

[memory3.cpp]

Глава 4

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

[memory4.cpp]

Глава 5

В принципе, можно попробовать вообще не хранить дополнительные данные рядом с каждым, а во время освобождения элемента определять его страницу каким-то другим образом. Например повесить все страницы на балансируемое бинарное дерево и по нему определять в адрес какой страницы попадает каждый элемент. В этом случае уже нельзя гарантировать освобождение и удаление элемента за O(1). Удаление элемента будет иметь оценку O(ln(n)), где n - число страниц. А создание новой страницы, может потребовать балансировку страниц.

Глава 6

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

[memory2m1.cpp] - вариант на основе [memory2.cpp] с массивами под одинаковое количество переменных
[memory2m2.cpp] - вариант на основе [memory2.cpp] со страницами фиксированого размера. В этом варианте, можно сделать вместо индексов, смешения и размеры (в этом случае слишком маленькие объекты, выделять будет нельзя).
[memory4m.cpp] - вариант на основе [memory4.cpp]. Фиксированные страницы. Структуры в начале банков. Так же сделаны контрольные сигнатуры, которые позволяют опознавать промахи мимо структур и увеличивают надёжность. Кроме того делать подходящее выравнивание элементов.

Глава 7

Призрачная возможность избавиться от меток около занятых элементов. Всё можно сделать так же как в [memory1.cpp]. Но список свободных элементов соединять в двунаправленный список. Для удаленния лишних страниц, можно делать медленную фоновую сортировку списка. В упорядоченом списке свободный банк будет выглядеть как достаточное количество свободных элементов идущих в памяти подряд. Адрес первого из них будет совпадать с адресом первого из элементов. К сожалению я пока не придумал как сделать такую сортировку достаточно красиво, хорошо и без нагрузки на процессор. При учёте того, что список на ходу изменяется. Пока что в голове крутятся разные сочетания из слияния последовательностей и куч (heap).

Глава 'byte'

Есть один общий недостаток. Если размер элемента меньше чем размер ссылки, то пропадает лишняя память. Но на деле никогда не бывает смысла выделять память для элементов которые меньше чем размер ссылки, так-как такой элемент лучше хранить по значению, а не по ссылке. Пример алокатора, который выделяет память для элементов размером в один байт (применимо и для двух байт):

[memory_byte.cpp]

Глава 'char*'

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

[memory_str.cpp]
[D-tree] - пример живого применения трюка.

Финал

Как и говорил выше, у них схем очень высокая скорость выделения памяти. Но есть мелкие недостатки:

Служебные данные могут влиять на выравнивание элементов в памяти. Хотя с другой стороны, если надо, можно увеличивать размеры индексов до нужных размеров и это не будет большой жертвой.
Они довольно чувствительны к повреждениям, если по время работы какой-то из элементов заезжает за отведённую ему границу. Тут можно надеятся что в мелких элементах будут мелкие вещи и мало места для ваших ошибок.
В конце каждого банка обычно есть неиспользуемые байты. На это есть две причины. Во первых управляющие структуры станицы имеют одну и туже позицию. При использовании правильного компилятора это позволяет делать меньше размноженного кода. Впрочем над оптимизацей на предмет отделения размера и функциональности я тут не думал. Во вторых вместо страниц можно делать массивы с фиксированным количеством элементов. Но я заточил исходники под конкретные размеры страниц, ибо это быстрее! По памяти мы всё равно выигрываем.
Мы не можем использовать объекты из-за обилия 'union' в исходнике. Можно сделать так чтобы объекты допускались, при этом даже 'Clear' будет вызывать деструкторы занятых объектов. Но исходник станет немного сложнее и будет не таким красивым.
Можно выбирать размеры типов индексов. Слишком большие будут неэффективны, слишком малые приводят к ошибке или плохо влияют на выравнивание. Насчёт ошибок, корректность проверяется в конструкторе через assert. Насчёт эффективного выбора, можно написать шаблон, который сам делает этот выбор, но время тратить не охота.

Можно попытаться избавится от дополнительных меток рядом с занятыми элементами, если вешать все элементы в двухсвязанный глобальный спискок. Сам список можно сортировать в фоновом режиме. В таком случае, свободный банк можно найти по наличию определённого числа свободных записей лежащих рядом друг с другом в памяти. Адрес банка совпадает с адресом его первого элемента. По правде я пока не придумал достаточно экономный метод фоновой сортировки. Есть кое какие мысли ввиде гибридов, на основе куч (heap) и слияния последовательностей. Но до реализации они пока не доведены.

Разумеется, абсолютно все недостатки можно устранить! Но работа как всегда отнимает время, так что не сейчас.

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

Но всё это уже другая песня.

[Proteus] lawnmower-man@mail.ru