Автор Тема: Менеджер памяти для двухтиповой системы  (Прочитано 14949 раз)

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
В системе есть объекты только двух типов: размера Q и размера 2*Q байтов (могу даже сказать, что Q=64 - размер кеш линии).
Нужен быстрейший менеджер памяти для динамической аллокации/деаллокации таких объектов и желательно, чтобы память как можно экономнее использовалась (проблема фрагментации).
Понятно, что всех быстрее будет всегда аллоцировать по 2*Q, и фрагментации не будет, но будет оверхед по расходу памяти.
Традиционный алгоритм объединяющий блоки вроде медленный.
Есть ли эффективное решение?




Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Менеджер памяти для двухтиповой системы
« Ответ #1 : Сентябрь 16, 2014, 11:40:21 am »
Пока есть идея размещать объекты размером Q с одной стороны имеющегося куска памяти, а размера 2*Q с другой стороны.



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


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

dizer

  • Jr. Member
  • **
  • Сообщений: 80
    • Просмотр профиля
Re: Менеджер памяти для двухтиповой системы
« Ответ #2 : Сентябрь 16, 2014, 12:11:42 pm »
Условия задачи позволяют
1. Использовать битовые массивы для хранения  распределения блоков и эффективного доступа к блокам памяти - номер ячейки отображается на адрес блока, содержимое - бит статуса(заполнена она или нет)
2 Аналогично массив целых чисел подойдет для хранения "мусорной части", здесь содержимое ячейки -номер "свободного" блока
3. В принципе, можно построить отображения этих структур на множества различной упорядоченности.. - аналог индексов в БД, для эффективного поиска больших сплошных участков памяти подлежащих освобождению
4. От переноса данных никуда не денешься

dizer

  • Jr. Member
  • **
  • Сообщений: 80
    • Просмотр профиля
Re: Менеджер памяти для двухтиповой системы
« Ответ #3 : Сентябрь 16, 2014, 03:26:18 pm »
... и есть подозрение, что  специфика задачи... используется не полностью. В этой связи, возможно, более уместно на этом этапе говорить скорее о "рекомендациях" , нежели  о конкретных рецептах. А они сводятся:
1) Использование O(1) структур (фиговая перестройка.. но возможность использования высокоэффективных низкоуровневых операций)
2) Насрать на размер обслуживающего кода - скажем так, выбор связанных списков дает только экономию по памяти, и производительность на вставках, при поиске O(n). Если отказаться "естественного" для программиста  стремления к экономии, то можно перейти на log(n) по вставке и поиску структуры (разновидности деревьев), также стоит рассмотреть возможность работы с индексированными представлениями - конечно, вставка и удаление замедлятся...
3) Возможно, моделирование "регулярного" использования этой структуры по назначению, позволит выявить "эффективный" режим работы механизма управления.. т.е. использовать оптимизированные алгоритмы управления на основе статистики
... НУ и не очень понятно НА СКОЛЬКО (в количественном выражении) плох стандартный подход.. если он эффективен в 90% случаев - может и не стоит напрягаться по поводу его смены.


Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Менеджер памяти для двухтиповой системы
« Ответ #4 : Сентябрь 17, 2014, 08:10:43 pm »
Выделять память для 2Q только с границ 2Qn, а память для Q так, чтобы, если где-то занято половина от 2Q, то дополнить ее до целого 2Q.

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Менеджер памяти для двухтиповой системы
« Ответ #5 : Сентябрь 18, 2014, 09:40:15 am »
В общем, если по полной воспользоваться советом Дизера, то можно получить следующее:

1. Выделять память блоками, кратными 2Q. Например, блок будет содержать 64 элемента 2Q.
2. Завести массив указателей на блоки (из пункта 1) и битовую карту на ячейки массива (в случае 64 элементов будет достаточно одного 64-битного числа).
3. У блока есть структура. Нулевой элемент блока служебный. Остальные используются для выделения памяти.
4. Спецификация служебной части блока:
   4.1. первый элемент - адрес или индекс свободной ячейки в этом блоке.
   4.2. битовая карта занятых ячеек блока.
   4.3. адрес и/или индекс блока в массиве блоков (из пункта 2).
   4.4. адрес битовой карты массива блоков.
   4.5. тип данных (размер Q или 2Q)

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

Допустим, у нас уже есть блок (из пункта 1), и мы хотим выделить память. Назовём этот блок активным. Выделение памяти происходит только в активном блоке. Одновременно активным для данного типа данных может быть только один блок. Мы смотрим в самое начало блока (без какого-либо смещения) и узнаём позицию свободной ячейки. Забираем эту позицию себе и записываем в начало блока увеличенный адрес. Размер блока фиксирован, поэтому момент заполнения блока проследить легко. Что если блок закончился? Когда выделять новый блок: сейчас или отложить до момента, когда придёт запрос на выделение нового объекта? Я бы отложил выделение нового блока, потому что могут оказаться полезными две оптимизации. Одна над текущим активным блоком, а вторая - концепция полупустых блоков. Также, вместе с увеличением адреса свободного блока установим и битик в нашей карте. Карта и адрес свободного блока находятся в одной кеш-линии, поэтому двукратного обращения к ОЗУ для получения двух этих значений быть не должно.

Допустим, нам больше не нужно одно из значений в блоке. Тогда, мы в карте сбрасываем бит соответствующей ячейки. Если битовая карта равна нулю, то блок свободен, и его можно переиспользовать. Отматываем счётчик свободных ячеек к началу. А также, получаем битовую карту массива блоков и сбрасываем битик и там.

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

Вместо массива из пункта 2 можно просто побить большой кусок памяти на блоки и считать всё это массивом блоков. Или вместо списка блоков использовать стек адресов на свободные блоки.

список пустых блоков можно использовать как для Q, так и для 2Q. Но допускаю, что это не критично. Вполне возможно, что Вы и так всю доступную память выделяете.
« Последнее редактирование: Сентябрь 18, 2014, 09:42:00 am от Valery Solovey »

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Менеджер памяти для двухтиповой системы
« Ответ #6 : Сентябрь 18, 2014, 09:45:53 am »
Если количество свободных ячеек удовлетворяет маске, то поместить блок в стек полупустых блоков.
Полупустой блок использовать вместо выделения или захвата нового блока памяти.

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Менеджер памяти для двухтиповой системы
« Ответ #7 : Сентябрь 18, 2014, 11:42:59 am »
Спасибо ответившим!

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

Заранее небольшое количество памяти нарезается для 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.

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

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Менеджер памяти для двухтиповой системы
« Ответ #8 : Сентябрь 18, 2014, 03:12:56 pm »
Если распределяется 128 для 64, то можно адрес на вторую часть от 128 поместить в список свободных 64 таким образом, чтобы эти вторые 64 были отданы первым же запросом на размещение объекта. Минус подхода - усложнение проверки при возврате куска в пул свободных кусков. Если возвращаем первую половинку, то нужно проверить, что вторая половинка не занята, забрать из пула размещённый адрес на вторую половинку и вернуть блок. При возврате второй половинки проверить, не обнулена ли первая, и если обнулена, то вернуть блок.

Цитировать
Списки организуются на памяти самих же свободных объектов.
Если я правильно понял, и имелось в виду, что из 64 байт 8 байт выделяется под адрес на следующий объект, в котором заняты тоже только 8 байт для адреса, то идея не очень, по-моему.

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Менеджер памяти для двухтиповой системы
« Ответ #9 : Сентябрь 18, 2014, 05:28:07 pm »
Цитировать
Списки организуются на памяти самих же свободных объектов.
Если я правильно понял, и имелось в виду, что из 64 байт 8 байт выделяется под адрес на следующий объект, в котором заняты тоже только 8 байт для адреса, то идея не очень, по-моему.
Наверное как-то неправильно поняли. Никакой дополнительной памяти нет. Вся память разбита на 64 и 128 байтные блоки. Организация связного списка свободных блоков возможна только на памяти этих же самых свободных блоков. Это элементарно: интерпретируем первые восемь байтов свободного блока как указатель на другой свободный блок.

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Менеджер памяти для двухтиповой системы
« Ответ #10 : Сентябрь 18, 2014, 09:23:11 pm »
Значит, я правильно понял. И нюанс здесь в том, что сначала мы вычитываем пустой блок, заполняем его и записываем обратно. Хотя ничего не мешает просто записать данные по заранее известному адресу. Со связным списком сразу записывать не получится: по адресу, по которому мы хотим записывать, находится адрес очередного блока.

Я бы адреса свободных блоков хранил отдельно. Например, в стеке. Даже если потребуется этот стек хранить в тех же самых блоках.

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Менеджер памяти для двухтиповой системы
« Ответ #11 : Сентябрь 19, 2014, 10:17:22 am »
Значит, я правильно понял. И нюанс здесь в том, что сначала мы вычитываем пустой блок, заполняем его и записываем обратно. Хотя ничего не мешает просто записать данные по заранее известному адресу. Со связным списком сразу записывать не получится: по адресу, по которому мы хотим записывать, находится адрес очередного блока.

Я бы адреса свободных блоков хранил отдельно. Например, в стеке. Даже если потребуется этот стек хранить в тех же самых блоках.

Ниже простая арена выделяющая память блоками по 64 байта. Список свободных блоков реализован на памяти самих же свободных блоков. В какой строчке происходит лишнее чтение блока?

class Arena
{
    struct Block
    {
        Block* next;
        uint8_t appendix[56];
    };

    Block* first;

public:
    Arena (uint8_t* memory, size_t size)
    {
        // Нарезаем память на куски по sizeof(Block),
        // организуем их в список,
        // указатель на первый - first
    }

    inline void* allocate ()
    {
        if (first != 0)
        {
            void* p = first;
            first = first->next;
            return p;
        }
        return 0;
    }

    inline void free (void* p)
    {
        ((Block*)p)->next = first;
        first = ((Block*)p);
    }
};


Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Менеджер памяти для двухтиповой системы
« Ответ #12 : Сентябрь 19, 2014, 10:40:42 am »
В какой строчке происходит лишнее чтение блока?
Я бы сказал, что это чтение, которого можно избежать, а не "лишнее".first = first->next;Перед этой строчкой мы получаем адрес блока, в который будем писать, а в этой строчке читаем текущий "пустой" блок и достаём из него адрес следующего блока, чтобы положить его в условленное место - переменную first. Чтобы записать восемь блоков, нам потребуется прочитать восемь пустых блоков. Не совсем пустых, конечно: в них хранятся адреса. Но ничто не мешает хранить адреса сгруппированными отдельно (например, в другом блоке). Восемь сгруппированных адресов по восемь байт - это одна строка кэша. И одно вспомогательное чтение ОЗУ на восемь записей.

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

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Менеджер памяти для двухтиповой системы
« Ответ #13 : Сентябрь 19, 2014, 10:56:28 am »
Спасибо. Понял.

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Менеджер памяти для двухтиповой системы
« Ответ #14 : Сентябрь 19, 2014, 12:18:10 pm »
То есть если хранить указатели на свободные блоки в массиве вместо связного списка, то следующий код будет работать до 8 раз быстрее:

for (int j = 0; j < 100; j++)
{
    a[j] = arena.allocate();
}

есть над чем призадуматься.

Можно, например, кэшировать несколько тысяч (2048) указателей в небольшом массиве в arena, а остальные миллионы указателей оставить в списке.

С другой стороны у нас такого кода то, вообще-то, не будет. Мы будем аллоцировать 1 объект, чего-то с ним делать. К моменту когда понадобиться аллоцировать следующий объект в L1/L2 кэше от данных arena скорее всего ничего и не останется. А значит при поштучном аллоцировании выгоды не будет.