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

Question

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

---

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

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

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

---

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

---

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

Answer 1

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

Answer 2

Расширяя свою концепцию «Пул» на странице, как насчет того, что если вы сохранили страницы как связанный список ??

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

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

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

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

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

Answer 3

Рассмотрим использование повысить бассейны

Answer 4

Один вопрос, конечно, зачем это беспокоить себя?

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

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

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

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

Для многопоточного распределения, tcmalloc а также jemalloc Используйте два разных подхода:

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

Answer 5

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

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

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

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