Блог

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

Одним из способов, о котором я подумал, была «подкачка», иначе

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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