Как вырастить буфер без аннулирования указателей на него?

Question

_{^{Термины «пул» и «буфер» могут использоваться здесь взаимозаменяемо.}}
Предположим, у меня есть пул, который я хочу выделить в начале программы, так какне всегда вызывать new все время.
Теперь я не хочу искусственно ограничивать себя размером пула, но если я перераспределю больший пул, все указатели на старый будут аннулированы,что, конечно, не очень круто.

---

Один из способов, о котором я подумал, это «подкачка страниц», или 1011 *

const int NUM_PAGES = 5;
char* pool[NUM_PAGES];

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

---

Другим способом было отображение из указателей, которые моя функция распределения возвращает указателямв реальное пространство памяти.Это позволило бы всем старым указателям оставаться действительными, но потребовало бы больше памяти, и мне нужно было бы написать умный указатель для возврата из моей функции выделения, которая выполняет сопоставление.

---

Какие другие возможные способыдостичь того, что я хочу, есть?Какие (не) преимущества я упустил в приведенных выше примерах реализации?

Answer 1

В продолжение вашей постраничной концепции "пула", что если вы сохранили страницы в виде связанного списка ??

Чтобы выделить новые данные из пула, вам необходим только доступ к верхней «странице», которая будет во главе списка, так что это O (1). Если вам нужно увеличить общий размер пула, выделите новую страницу и поместите ее в начало списка, также O (1).

Я использую в основном ту же идею для распределенных распределителей, но также и со «свободным списком» недавно освобожденных элементов ...

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

Стандартные менеджеры памяти часто уже делают что-то подобное, поэтому такой подход не всегда будет лучше . В частности, я обычно использую этот тип пользовательского распределителя, только когда выделенные элементы имеют одинаковый размер (так что обход свободного списка равен O (1)!). Пользовательский распределитель для std :: list мог бы быть одним примером.

Надеюсь, это поможет.

Answer 2

Вы говорите о чем-то, что напоминает мне о std::deque. Я не совсем уверен, можете ли вы использовать std::deque как есть, или вам просто нужно использовать его базовый дизайн для реализации какого-то рода распределителя.

Answer 3

Один вопрос, конечно, почему вы так беспокоитесь?

Вы говорите, что хотите избежать накладных расходов new, но почему бы вместо этого не выбрать лучшую реализацию new?tcmalloc и jemalloc, как правило, являются очень хорошими претендентами для многопоточных приложений, например.

То, что вы пытаетесь создать, на самом деле очень похоже на написание настраиваемого malloc / newреализация.Поэтому вы, если вы действительно не хотите использовать проверенную реализацию, извлекли бы пользу из идей тех, кто это сделал.

Мой личный интерес связан со стратегией BiBOP (Big Bag of Pages) для борьбы с фрагментацией.Идея состоит в том, чтобы иметь выделенный пул на размер распределения, и, таким образом, достаточно простого свободного списка (чередующегося с распределениями) (слияние не требуется).Обычно это делается до тех пор, пока запрошенный размер меньше размера страницы (я видел использование 4 КБ), а все, что больше, выделяется само по себе (на нескольких страницах).Отброшенные страницы перерабатываются.

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

Для многопоточного размещения tcmalloc и jemalloc используют два разных подхода:

• jemalloc использовать пул для каждого потока: хорошо с фиксированным числом потоков / пулов потоков, но сделать процесс создания потока более дорогостоящим
• tcmalloc использовать глобальный многопоточный пул,с технологией без блокировок, и попытайтесь сбалансировать нагрузку на потоки в доступных пулах, чтобы ограничить конкуренцию, заставляя поток искать новый пул, если тот, который он использует, «заблокирован» (а не ожидает), и каждый поток кэшируетпоследний использованный пул в локальной переменной потока.Потоки поэтому легковесны, но могут возникнуть некоторые споры, если число пулов слишком мало по сравнению с количеством активных потоков.

Answer 4

Рассмотрите возможность использования пулов повышения

Answer 5

Несколько мыслей:

• Если у вас есть std::vector<T*>, добавление элементов и запуск изменения размера делает недействительными ссылки / указатели / итераторы в этот контейнер, но не ссылки / указатели, которые непосредственно обращаются к указанным объектам. Таким образом, слой косвенности может решить вашу проблему, в зависимости от того, что вы действительно пытаетесь делать с этими ссылками / указателями / итераторами.

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

• Другие контейнеры - std::map<> и std::list<> - не перемещают свои существующие элементы при добавлении новых, поэтому итераторы / указатели / ссылки остаются действительными.