Быстрейший менеджер памяти для двухтиповой системы

[SergeyGubanov]

В системе есть объекты только двух типов: размера $Q$ и размера $2 Q$ байтов ($Q=64$ - размер кеш линии).

Нужен быстрейший менеджер памяти для динамической аллокации/деаллокации таких объектов и желательно, чтобы память как можно экономнее использовалась.

Понятно, что всех быстрее будет всегда аллоцировать по $2 Q$, и фрагментации не будет, но будет оверхед по расходу памяти.

Традиционный алгоритм объединяющий блоки вроде медленный (или нет?).

Есть ли эффективное решение?

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



При деаллокации "крайние" блоки можно возвращать обратно в "общую сырую память". А "некрайние" блоки ставить в список неиспользуемых (связный список организовать разумеется на самих же неиспользуемых блоках).

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

Какие ещё есть варианты?

[Progger]

А исходный блок памяти обязательно один и фиксированного размера? Может можно использовать для $Q$ и $2Q$ разные блоки?

[SergeyGubanov]

Заранее не известно сколько будет нужно аллоцировать блоков $Q$, а сколько $2Q$, их пропорция может изменяться со временем, так что память общая - одна на всех.

[_hum_]

А что если всю память представить как состоящую из "квант-блоков" размером 1Q и связать с каждым таким блоком целое положительное число (ключ) таким образом, чтобы в пределах составного блока (1Q или 2Q) оно было одинаковым, но уникальным за его пределами. И положить для пустых "квант-блоков" в качестве ключа значение 0. То есть, если в какой-то момент времени имеется картина

Q, пустой Q, пустой Q, 2Q, 2Q, пустой Q, Q

то в представлении проиндексированными ключами "квант-блоков" это будет выглядеть наподобие:

[1], [0], [0], [3], [3], [4], [4], [0], [6]

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

[0], [0], [0], [1], [3], [3], [4], [4], [6]

[SergeyGubanov]

_hum_ в сообщении #909121 писал(а):

Тогда можно организовать дефрагментацию

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

Вобщем, я пока склоняюсь к следующему частному компромисному решению...

Заранее небольшое количество памяти нарезается для 64-байтных объектов, вся остальная память нарезается под 128-байтные объекты.
Все объекты помещаются в два односвязных списка свободных элементов (64 и 128 байтных). Списки организуются на памяти самих же свободных объектов.

Когда запрашивается 64 байта, тогда выдаётся элемент из списка 64-байтных, а когда этот список становится пустым, то, скрипя зубами, выдаётся, отрывается от сердца, элемент из списка 128 байтных блоков.

Как то так (число 48Mb взято просто для примера):



Когда указатель на 64 байтный объект возвращается, то одной проверкой if (p < 48Mb) выясняется кто он на самом деле: истинный 64 байтный или 128 байтовый. Соответственно, ставится в список свободных 64 или 128 байтных блоков.

Оптимальный размер памяти отдаваемый под 64 байтные объекты надо будет выяснить экспериментально.

Почему так, а не иначе:
1) Есть жёсткое ограничение на количество обращений к DDR3 памяти (пропускная способность контроллера памяти является "бутылочным горлышком" для нашего программного продукта).
2) Аллокация/деаллокация 64 байтных блоков происходит на порядок чаще чем 128 байтных.
Поэтому приходится отказываться от алгоритмов делающих слияние свободных блоков 64+64=128.

Если кто нибудь придумает как ещё больше сэкономить память не слишком сильно замедляя алгоритм, то это будет круто...

[Skeptic]

Разбить память и записываемые блоки на части равной длины $Q$. Полное использование памяти при допустимом времени размещения и выборки.

[_hum_]

SergeyGubanov, а если бы все блоки были одинакового размера, проблем бы не было?
Если да, то, может, рассмотреть идею, когда 2Q блок разбивается на два 1Q блока, каждый из которых сохраняется отдельно, но в одном из них дополнительно сохраняется ссылка на другой, чтобы можно было при надобности восстановить цельность?

[Sender]

1. Для любого блока размером $Q$ можно выделить первый по порядку свободный участок памяти.
2. Для блока размером $2Q$ можно выделить первый по порядку участок памяти с чётным адресом, свободный от блоков размером $2Q$. Если на выбранном участке оказались блоки размером $Q$, переместить их на свободные места, найденные в соответствии с п.1.
При небольших дополнительных телодвижениях при удалении каждого блока можно всё время поддерживать эту конструкцию в дефрагментированном состоянии.

-- Чт сен 18, 2014 16:31:19 --

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

[SergeyGubanov]

Sender в сообщении #909168 писал(а):

Если на выбранном участке оказались блоки размером $Q$, переместить их на свободные места, найденные в соответствии с п.1.

Что значит переместить блок? Скопировать его содержимое в другой блок, а потом ещё обежать 32 Гигабайта оперативки и каким-то хитрым образом отыскать и заменить значения всех указателей на старый блок на указатели на новый блок??? Ну и шуточки у вас...

[_hum_]

SergeyGubanov
Так все-таки, что мешает свести задачу к размещению одинаковых по размеру блоков? Для этого каждый блок представляем как состоящий из одного (монолитный) или двух (составной) элементарных блоков

struct TELEMENTARY_ВLOCK
{
     uint2     part; // номер части составного блока (если это элемент составного блока, то значения 1 или 2, если монолитный, то 0)
     uint32   complementary_elementary_block_adress; // указатель на комплементарный блок (если монолитный блок, то указатель нулевой)
     uint8     Data[64];
};

Ну, и все. Разбиваем при необходимости сохраняемый блок на две части, сохраняем на свободные места, записывая соответствующую информацию. Как результат - возвращаем указатель на первую часть блока. При необходимости по первой части достаем и вторую, сшиваем и вуаля. Что не так?

[upgrade]

а указатель сколько битный и где хранится?

-- 18.09.2014, 19:12 --

у нас такая же наверно проблема
есть массив данных состоящий из значений от 2-битных до многобитных ( 512 и больше)
не получается объявить массив, в который можно записать как-то так
$a[1]=01$
...
$a[512]=\underbrace{010011...010100001111}_{503\text{ бит}}$

поэтому пока работаем со строками
$a[1]=
...
$a[503]=\underbrace{\text{''010011...01010011z253z''}}_{255\text{ символов}}$
$a[503+1]=\underbrace{\text{''010011...010100111''}}_{253\text{ символа}}$

-- 18.09.2014, 19:42 --

применительно к менеджеру памяти, видимо надо все разбивать на $32$ бита - и $128$-битные и $64$-битные.
и выделять $32$ бита на указатели и биты разбиения.
то есть память будет разделена на парные блоки по $32$ бита (парные потому что рядом расположены - адреса отличаются на единицу)
если в $ 1$ блоке первый бит $0$ то все следующие парного блока биты - это данные
если в $1$ блоке первый бит $1$ то следующие $31$ бит - это указатель на адрес второго парного блока.

[Sender]

SergeyGubanov в сообщении #909184 писал(а):

а потом ещё обежать 32 Гигабайта оперативки и каким-то хитрым образом отыскать и заменить значения всех указателей на старый блок на указатели на новый блок???

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

[Skeptic]

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

[mustitz]

Как вариант, можно всегда выделять по $2Q$. Если надо выделить $Q$, то помещаем второй $Q$ в список свободных блоков.

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

В общем случае для обїединения неиспользуемых блоков $Q$ их надо отсортировать. Еще можно хранить свободные блоки $Q$ в красно-черном дереве (два указателя плюс два бита).

[_hum_]

На всякий случай, если ТС не понимает, о чем я пишу: