Какой алгоритм распределения памяти лучше всего подходит для приложений C++, критичных к производительности и времени?
Я задаю этот вопрос, чтобы определить, какой алгоритм распределения памяти дает лучшие результаты в приложениях, критичных к производительности, таких как игровые движки или встроенные приложения. Результаты на самом деле зависят от процента фрагментированной памяти и времени детерминированности запроса памяти.
В учебниках есть несколько алгоритмов (например, распределение памяти друзей), но есть и другие, такие как TLSF. Поэтому, что касается алгоритмов выделения памяти, какой из них является самым быстрым и вызывает меньше фрагментации. Кстати, сборщики мусора не должны быть включены.
Также обратите внимание, что этот вопрос не о профилировании, он просто нацелен на поиск оптимального алгоритма для данных требований.
5 ответов
Все зависит от приложения. Серверные приложения, которые могут очищать всю память, относящуюся к конкретному запросу, в определенные моменты времени будут иметь другую схему доступа к памяти, чем, например, видеоигры.
Если бы существовал один алгоритм распределения памяти, который всегда был лучшим для производительности и фрагментации, люди бы не реализовали malloc а также new всегда выбирать этот алгоритм?
В настоящее время обычно лучше предположить, что люди, которые написали вашу операционную систему и библиотеки времени выполнения, не были умственно отсталыми; и если у вас нет необычного паттерна доступа к памяти, не пытайтесь побить их.
Вместо этого попытайтесь уменьшить количество выделений (или перераспределений), которые вы делаете. Например, я часто использую std::vector, но если я заранее знаю, сколько у него будет элементов, я могу зарезервировать все это за один раз. Это гораздо эффективнее, чем позволить ему расти "естественным образом" через несколько обращений к push_back(),
Многие люди приходят с языков, где new просто означает "дай мне объект" будет распределять вещи без веской причины. Если вам не нужно положить его в кучу, не звоните new,
Что касается фрагментации: это все еще зависит. К сожалению, сейчас я не могу найти ссылку, но я помню сообщение в блоге от кого-то из Microsoft, который работал над приложением на сервере C++, которое страдало от фрагментации памяти. Команда решила проблему, выделив память из двух регионов. Память для всех запросов будет поступать из области A, пока она не будет заполнена (запросы будут освобождать память как обычно). Когда область A была заполнена, вся память была бы выделена из области B. К тому моменту, когда область B была заполнена, область A снова была полностью пустой. Это решило их проблему фрагментации.
Это решит твоё? Я понятия не имею. Вы работаете над проектом, который обслуживает несколько независимых запросов? Ты работаешь над игрой?
Что касается детерминизма: это все еще зависит. Какой у вас срок? Что происходит, когда вы пропускаете крайний срок (космонавты теряются в космосе? Воспроизводимая музыка начинает звучать как мусор?)? Есть распределители реального времени, но помните: "в реальном времени" означает "дает обещание о соблюдении крайнего срока", а не обязательно "быстро".
Я только что наткнулся на пост, описывающий различные вещи, которые Facebook сделал для ускорения и уменьшения фрагментации в jemalloc. Вы можете найти это обсуждение интересным.
Барыш:
Ваш вопрос очень общий, но вот мой ответ / руководство:
Я не знаю игровые движки, но для встроенных приложений и приложений реального времени. Основные цели алгоритма распределения:
1- Ограниченное время выполнения: вы должны заранее знать время распределения в худшем случае, чтобы вы могли соответственно планировать свои задачи в реальном времени.
2- Быстрое исполнение: чем быстрее, тем лучше
3- Всегда распределять: особенно в режиме реального времени, критически важных приложений, все запросы должны быть удовлетворены. Если вы запрашиваете некоторое пространство памяти и получаете нулевой указатель: проблема!
4- Уменьшение фрагментации. Хотя это зависит от используемого алгоритма, обычно менее фрагментированные выделения обеспечивают лучшую производительность по ряду причин, включая эффекты кэширования.
В большинстве критических систем вам не разрешено динамически выделять память для начала. Вы анализируете свои требования и определяете максимальное использование памяти и выделяете большой кусок памяти, как только ваше приложение запускается. Если вы не можете, то приложение даже не запускается, если оно запускается, новые блоки памяти не выделяются во время выполнения.
Если скорость вызывает беспокойство, я бы рекомендовал следовать аналогичному подходу. Вы можете реализовать пул памяти, который управляет вашей памятью. Пул может инициализировать "достаточный" блок памяти при запуске вашего приложения и обслуживать ваши запросы памяти из этого блока. Если вам требуется больше памяти, пул может выполнить другое, вероятно, большое выделение (в ожидании большего количества запросов памяти), и ваше приложение может начать использовать эту вновь выделенную память. Также существуют различные схемы объединения памяти, и управление этими пулами - еще одна тема.
Что касается некоторых примеров: ОСРВ VxWorks использовала алгоритм распределения по первому размеру, где алгоритм анализировал связанный список, чтобы найти достаточно большой свободный блок. В VxWorks 6 они используют алгоритм наилучшего соответствия, в котором свободное место хранится в дереве, а выделения пересекают дерево для достаточно большого свободного блока. Там есть белая книга под названием Memory Allocation in VxWorks 6.0Золтаном Ласло, который вы можете найти в Google, который имеет больше деталей.
Возвращаясь к вашему вопросу о скорости / фрагментации: это действительно зависит от вашего приложения. Что нужно учитывать:
Собираетесь ли вы делать много очень небольших ассигнований или относительно больших?
Распределения будут приходить пакетами или распределяться равномерно по всему приложению?
Каков срок действия распределений?
Если вы задаете этот вопрос из-за того, что собираетесь реализовать свой собственный распределитель, вам, вероятно, следует разработать его таким образом, чтобы вы могли изменить основной алгоритм выделения / освобождения, потому что если скорость / фрагментация действительно так важна в вашем приложение, вы будете хотеть экспериментировать с различными распределителями. Если бы я рекомендовал что-то, не зная ни одного из ваших требований, я бы начал с TLSF, поскольку он обладает хорошими общими характеристиками.
Лучшая практика - использовать все, что вы можете использовать, чтобы все было сделано вовремя (в вашем случае - распределитель по умолчанию). Если все это очень сложно - напишите тесты и примеры, которые будут подражать частям всего этого. Затем запустите тесты производительности и тесты производительности, чтобы найти узкие места (вероятно, они не будут иметь ничего общего с распределением памяти:). С этого момента вы увидите, что именно замедляет ваш код и почему. Только на основе таких точных знаний вы сможете что-то оптимизировать и выбрать один алгоритм вместо другого. Без тестов это просто пустая трата времени, так как вы даже не можете измерить, насколько ваша оптимизация ускорит ваше приложение (на самом деле такая "преждевременная" оптимизация может реально замедлить его).
Распределение памяти - очень сложная вещь, и она действительно зависит от многих факторов. Например, такой распределитель прост и чертовски быстр, но может использоваться только в ограниченном количестве ситуаций:
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; }
Таким образом, не существует "лучшего алгоритма".
Как уже писали другие, не существует "оптимального алгоритма" для каждого возможного применения. Уже было доказано, что для любого возможного алгоритма вы можете найти последовательность размещения, которая вызовет фрагментацию.
Ниже я напишу несколько советов из моего опыта разработки игр:
Избегайте выделений, если можете
Распространенной практикой в области разработки игр было (и до некоторой степени все еще остается) решение проблем производительности динамического выделения памяти путем исключения выделения памяти, как чумы. Вместо этого довольно часто можно использовать стековую память - даже для динамических массивов вы часто можете прийти с оценкой, которая охватит 99 % случаев для вас, и вам нужно распределять ее только тогда, когда вы выходите за эту границу. Другой часто используемый подход - это "предварительное распределение": оцените, сколько памяти вам потребуется для какой-либо функции или для какого-либо объекта, создайте своего рода небольшую и упрощенную "локальную кучу", которую вы выделяете заранее, и выполняйте отдельные выделения только из этой кучи.
Библиотеки распределителя памяти
Другой вариант - использовать некоторые из библиотек распределения памяти - они обычно создаются специалистами в данной области для соответствия некоторым особым требованиям, и, если у вас есть похожие требования, они могут соответствовать вашим требованиям.
Многопоточность
Есть один конкретный случай, в котором вы найдете "по умолчанию" распределитель OS/CRT, работающий плохо, и это многопоточность. Если вы ориентируетесь на Windows, то, зная, что распределители ОС и CRT, предоставленные Microsoft (включая отличную "Низкую кучу фрагментации"), в настоящее время блокируются. Если вы хотите выполнить значительную многопоточность, вам нужно либо максимально сократить выделение ресурсов, либо использовать некоторые альтернативы. См. Может ли многопоточность ускорить выделение памяти?
Стоит упомянуть одно ограничение, которое еще не упоминалось, это многопоточность: должны быть реализованы стандартные распределители для поддержки нескольких потоков, причем все выделяются / освобождаются одновременно, а объекты передаются из одного потока в другой, так что он освобождается другим нить.
Как вы, возможно, догадались из этого описания, очень сложно реализовать распределитель, который хорошо справляется со всем этим. И это действительно экономически выгодно, поскольку невозможно удовлетворить все эти ограничения без межпотоковой связи (= использование атомарных переменных и блокировок), что довольно дорого.
Таким образом, если вы можете избежать параллелизма в своих распределениях, у вас есть хороший шанс реализовать свой собственный распределитель, который значительно превосходит стандартные распределители: я однажды сделал это сам, и это сэкономило мне примерно 250 циклов ЦП на выделение с довольно простым распределителем это основано на количестве пулов памяти фиксированного размера для небольших объектов, накапливающих свободные объекты с помощью навязчивого связанного списка.
Конечно, избежать параллелизма для вас, скорее всего, не стоит, но если вы все равно его не используете, возможно, стоит подумать об использовании этого факта.