Дефрагментация распределителя кучи C ++ и STL

Question

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

Грубая схема будет состоять в том, чтобы распределять блоки, начиная с самого низкого адреса памяти, восходя, и сохраняя информацию бухгалтерского учета, начиная с самого высокого адреса памяти, работая вниз.

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

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

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

Так что мой вопрос: кто-нибудь использовал такую ​​схему распределения в сочетании с STL, если бы я подозревал, что она просто разнесет STL на части? Я вижу, что std :: list работает на уровне intrusive_ptr, но как насчет распределения самих узлов списка stl, так или иначе, есть ли возможность переопределить следующие / prev указатели на сами intrusive_ptr или мне просто нужно стандартный распределитель кучи вдоль этой более динамичной.

Answer 1

Если вы собираетесь перемещать объекты в памяти, то вы не можете сделать это в общем случае. Вы сможете сделать это только с объектами, которые знают , что они могут быть перемещены. Вам также понадобится механизм блокировки. Когда функция вызывается для объекта, ее нельзя перемещать.

Причина в том, что вся модель C ++ опирается на объекты, расположенные в фиксированных точках памяти, поэтому, если поток вызывал метод для объекта, этот поток был приостановлен, а объект перемещен, при возобновлении потока произойдет авария.

Любой объект, который содержит необработанный указатель памяти на другой объект, который может быть перемещен (включая сам подобъект), не будет работать.

Такая схема управления памятью может работать, но вы должны быть очень осторожны. Вы должны быть строгими в реализации дескрипторов и семантики блокировки дескриптора handle-> указателя.

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

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

Answer 2

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

Список - это исключительно плохой пример, который можно поместить в диспетчер дефрагментируемой памяти, поскольку он представляет собой кучу мелких кусочков, как и большинство других структур данных STL. Если вы сделаете это, это будет иметь все виды очевидных плохих последствий - включая снижение производительности вашего дефрагментатора, а также стоимость косвенного обращения и т. Д. Единственные структуры, в которых имеет смысл IMO, являются сомнительными - массив, deque, основной кусок хеш-таблицы Эти вещи, и только за пределами определенного размера, и только после того, как они больше не будут изменены. Подобные вещи, опять же, требуют конкретных решений, а не общих.

Прокомментируйте, как все это получается.

Answer 3

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

Answer 4

Другой хорошо известный альтернативный метод - система друзей . Вы должны взглянуть на это для дополнительного вдохновения.

Answer 5

STL-контейнеры реализованы с использованием голых указателей.

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

Вместо этого вы могли бы рассмотреть возможность реализации подмножества STL самостоятельно: ваши версии контейнеров STL могли бы затем быть реализованы с помощью управляемых указателей.