Какой алгоритм распределения памяти лучше всего подходит для приложений c ++, критичных к производительности и времени?

Question

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

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

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

Answer 1

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

Если был один алгоритм распределения памяти, который всегда был лучшим для производительности ифрагментация, разве люди, реализующие malloc и new, не всегда выберут этот алгоритм?

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

Вместо этого попытайтесь уменьшить количество выделений (или перераспределений), которые вы делаете.Например, я часто использую std::vector, но если я заранее знаю, сколько у него будет элементов, я могу зарезервировать все это за один раз.Это гораздо эффективнее, чем позволить ему «расти» естественным путем посредством нескольких вызовов push_back().

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

Что касается фрагментации: это все еще зависит.К сожалению, сейчас я не могу найти ссылку, но я помню сообщение в блоге от кого-то из Microsoft, который работал над приложением на сервере C ++, которое страдало от фрагментации памяти.Команда решила проблему, выделив память из двух регионов.Память для всех запросов будет поступать из области A, пока она не будет заполнена (запросы будут освобождать память как обычно).Когда область A была заполнена, вся память была бы выделена из области B. К тому моменту, когда область B была заполнена, область A снова была полностью пустой.Это решило их проблему фрагментации.

Это решит вашу?Я понятия не имею.Вы работаете над проектом, который обслуживает несколько независимых запросов? Вы работаете над игрой ?

Что касается детерминизма: он все еще зависит.Какой у вас срок?Что происходит, когда вы пропускаете крайний срок (космонавты теряются в космосе? Воспроизводимая музыка начинает звучать как мусор?)?Есть распределителей реального времени , но помните: «в реальном времени» означает «дает обещание о соблюдении крайнего срока», не обязательно «быстро».

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

Answer 2

Барыш:

Ваш вопрос очень общий, но вот мой ответ / руководство:

Я не знаю об игровых движках, но для встроенных приложений и приложений реального времени. Основные цели алгоритма распределения:

1- Ограниченное время выполнения: вам нужно заранее знать время распределения в худшем случае, чтобы вы могли соответствующим образом планировать свои задачи в реальном времени.

2- Быстрое выполнение: чем быстрее, тем лучше, очевидно

3- Всегда выделять: особенно для приложений, критичных для безопасности в режиме реального времени, все запросы должны быть удовлетворены. Если вы запрашиваете место в памяти и получаете нулевой указатель: проблема!

4- Уменьшение фрагментации. Хотя это зависит от используемого алгоритма, обычно менее фрагментированные выделения обеспечивают лучшую производительность по ряду причин, включая эффекты кэширования.

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

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

Как и в некоторых примерах: ОСРВ VxWorks использовала алгоритм распределения по первому размеру, где алгоритм анализировал связанный список, чтобы найти достаточно большой свободный блок. В VxWorks 6 они используют алгоритм наилучшего соответствия, в котором свободное место хранится в дереве, а выделения пересекают дерево для достаточно большого свободного блока. Есть белая бумага под названием Memory Allocation in VxWorks 6.0, написанная Золтаном Ласло, которую вы можете найти в Google, которая содержит более подробную информацию.

Возвращаясь к вашему вопросу о скорости / фрагментации: это действительно зависит от вашего приложения. Что нужно учитывать:

• Собираетесь ли вы делать много очень небольших или относительно больших ассигнований?

• Будут ли ассигнования распределяться пакетами или распределяться равномерно по приложению?

• Каков срок службы распределений?

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

Answer 3

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

Ниже я напишу несколько советов из моего опыта разработки игр:

Избегайте выделений, если можете

Распространенной практикой в ​​области разработки игр было (и до некоторой степени все еще остается) решение проблем производительности динамического выделения памяти путем избежания выделения памяти, как чумы.Вместо этого довольно часто можно использовать стековую память - даже для динамических массивов вы часто можете прийти с оценкой, которая охватит 99% случаев для вас, и вам нужно выделять только тогда, когда вы выходите за эту границу.Другой часто используемый подход - это «предварительное распределение»: оцените, сколько памяти вам потребуется для какой-либо функции или для какого-либо объекта, создайте своего рода небольшую и упрощенную «локальную кучу», которую вы выделяете заранее, и выполняйте отдельные выделения только из этой кучи.1007 *

Библиотеки выделения памяти

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

Многопоточность

Существует один конкретный случай, в котором вы обнаружите, что «по умолчанию» распределитель ОС / CRT работает плохо, и это многопоточность.Если вы ориентируетесь на Windows, то, зная, что распределители ОС и CRT, предоставленные Microsoft (включая отличную «Низкую кучу фрагментации»), в настоящее время блокируются.Если вы хотите выполнить значительную многопоточность, вам нужно либо максимально сократить выделение ресурсов, либо использовать некоторые альтернативы.См. Может ли многопоточность ускорить выделение памяти?

Answer 4

Лучшая практика - использовать все, что вы можете использовать, чтобы все было сделано вовремя (в вашем случае - распределитель по умолчанию).Если все это очень сложно - напишите тесты и примеры, которые будут подражать частям всего этого.Затем запустите тесты производительности и тесты производительности, чтобы найти узкие места (вероятно, они не будут иметь ничего общего с распределением памяти :).С этого момента вы увидите, что именно замедляет ваш код и почему .Только на основе таких точных знаний вы сможете что-то оптимизировать и выбрать один алгоритм вместо другого.Без тестов это просто пустая трата времени, поскольку вы даже не можете измерить, насколько ваша оптимизация ускорит ваше приложение (на самом деле такие «преждевременные» оптимизации могут реально замедлить его).и это действительно зависит от многих факторов.Например, такой распределитель прост и чертовски быстр, но может использоваться только в ограниченном числе ситуаций:

char pool[MAX_MEMORY_REQUIRED_TO_RENDER_FRAME];
char *poolHead = pool;

void *alloc(size_t sz) { char *p = poolHead; poolHead += sz; return p; }
void free() { poolHead  = pool; }

Так что «лучшего алгоритма из когда-либо существовавших» не существует.

Answer 5

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

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

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

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