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

[SergeyGubanov]

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

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

Что не так?

Не вдаваясь в детали, не так то, что размер элементарного блока должен быть равен $Q=64$ байта. Это размер кэш линии - квант операции чтения.

Представьте, что есть $256$ Мб памяти. Она состоит из $2^{28} = 4\,194\,304$ кэш линий. То есть чтобы прочитать эту память нужно выполнить $4\,194\,304$ запросов чтения. Далее, в системе есть объекты двух размеров: в одну кэш линию $Q$ и в две кэш линии $2 Q$. Требуется придумать менеджер памяти, который бы обслуживал эту систему максимально быстро, а фактически, выполнял бы минимальное количество операций чтения памяти. При этом желательно память экономить, в частности не допускать её фрагментации.

[_hum_]

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

Не вдаваясь в детали, не так то, что размер элементарного блока должен быть равен $Q=64$ байта. Это размер кэш линии - квант операции чтения.

Кхм... А в приведенном примере он какой? Или вы имеете в виду, что дополнительная служебная информация типа указателей все портит? Ну, так можно же тогда вынести в отдельный список (как вы делаете в своем варианте). В общем, да, наверное там какие-то специфические детали, которые мне сложно понять.

[Skeptic]

Самый быстрый - самый простой. Просмотр всегда начинается с начала памяти. Запись производится в первое свободное место. Чтение - первая найденная запись.

[_hum_]

Skeptic в сообщении #910497 писал(а):

Самый быстрый - самый простой. Просмотр всегда начинается с начала памяти. Запись производится в первое свободное место. Чтение - первая найденная запись.

Это не самый быстрый. Время поиска свободного места получается пропорционально размеру массива данных. В моем же варианте оно постоянно :)

[Skeptic]

А перестроение списков не требует дополнительных операций (времени) и памяти?

[SergeyGubanov]

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

Или вы имеете в виду, что дополнительная служебная информация типа указателей все портит? Ну, так можно же тогда вынести в отдельный список (как вы делаете в своем варианте). В общем, да, наверное там какие-то специфические детали, которые мне сложно понять.

Да, все 64 байта кэш линии, то есть все 64 байта одного блока $Q$ должны быть отданы пользователю целиком, никакой служебной информации туда всунуть нельзя. А пользователь, в свою очередь, тоже должен так ужаться, чтобы уместить свои данные (из своей предметной области) в эти самые "жалкие" 64 байта (ну, или, в 128 байтов, но тогда нужно будет два запроса к памяти). В моём варианте нет отдельно стоящих списков. Связные списки свободных элементов у меня организуются на самих же свободных блоках, то есть в тех же самых 256 Мб.

[upgrade]

а как пользователь запрашивает?
"дайте мне любые 64 байта"
или
"дайте мне 64 байта по адресу"
или
"дайте мне каких-нибудь данных"
?

[_hum_]

Skeptic в сообщении #910788 писал(а):

А перестроение списков не требует дополнительных операций (времени) и памяти?

Требует. Но постоянного, порядка нескольких единиц времени (вместо вашего варианта с порядком нескольких миллионов). А про задействование доп. памяти - так это естественно - давно известно негласное правило (закон подлости):

$$\text{быстродействие } \times \text{ память} \, \simeq \,\mathrm{const}.$$

Потому иногда и называют инженерию (в том числе программную) наукой компромиссов :)

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

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

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

[Skeptic]

Рассмотрим блоки постоянной длины, потом результаты не трудно обобщить для блоков разной длины.
Входящая запись размещается на любом свободном месте. Заранее эти места не известны, надо найти одно из них. Для памяти объёмом $M$ при длине записи $Q$ мест для размещении будет $n=M/Q$. Задача свелась к поиску элемента в массиве размерностью $n$. Предположим, что искомый элемент с равной вероятностью может находится в любом месте массива.

1. Для поиска в массиве нужного элемента простым перебором с начала массива в среднем потребуется $n/2$ просмотров, состоящих из трёх операций: чтение элемента массива, проверка, переход к следующему элементу массива.
2. Можно освободившиеся места сдвигать в началу массива. Это потребует перемещения в массиве в среднем тоже $n/2$ элементов. Этот вариант более затратен по операциям и времени, чем предыдуший.
3. Если использовать, списки свободных и занятых мест, то это вызовет перемещение поиска из исходного массива размерностью $n$ в дополнительные два массива той же размерностьи $n$ каждый, что не только не ускорит процесс, а вызовет дополнительный расход памяти и времени на реорганизацию списков.

Использовать дополнительные списки имеет смысл, если размерность списков значительно меньше размерности $n$ исходного массива.

Один из возможный вариантов.
Создадим бинарную строку длиной $n$. Припишем $i$-тому элементу строки "1", если $i$-тый элемент в исходном массиве занят, и "0", если свободен. Поиск свободного места осуществляем поиском в строке места первого вхождения подстроки "0". В языках программирования есть такая функция. Время поиска при такой организации сократится больше, чем на порядок.