В общем, если по полной воспользоваться советом Дизера, то можно получить следующее:
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. Но допускаю, что это не критично. Вполне возможно, что Вы и так всю доступную память выделяете.