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

Question

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

---

Один из способов, которым я придумал, был "пейджинг", иначе

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

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

---

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

---

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

Answer 1

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

Answer 2

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

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

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

РЕДАКТИРОВАТЬ: Согласно вашему комментарию, если вы хотите также использовать освобожденные данные, вы также можете сохранить свободный список, возможно, также в виде связанного списка. Поэтому, когда вы освобождаете данные, вы помещаете указатель и маркер размера в свободный список. Когда вы выделяете данные из пула, вы сначала проверяете, можно ли использовать какие-либо элементы в свободном списке, если вы не выделяете их из пула.

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

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

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