Минимизация количества вызовов malloc () повышает производительность?

Question

Рассмотрим два приложения: одно (число 1), которое вызывает malloc () много раз, а другое (число 2), которое вызывает malloc () несколько раз. Оба приложения выделяют одинаковый объем памяти (предположим, 100 МБ).
Для какого приложения следующий вызов malloc () будет быстрее, # 1 или # 2?
Другими словами: имеет ли malloc () индекс выделенных мест в памяти?

Answer 1

Вы задали 2 вопроса:

• для какого приложения следующий вызов malloc () будет быстрее, # 1 или # 2?
• Другими словами: имеет ли malloc () индекс выделенных мест в памяти?

---

Вы подразумевали, что это один и тот же вопрос, но это не так. Ответ на последний вопрос - ДА.

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

Однако ваша идея обоснована: вам следует подумать о том, как использование malloc повлияет на производительность. Однажды я написал приложение, которое использовало много маленьких пятен памяти, каждое из которых было выделено функцией malloc (). Это работало правильно, но было медленно. Я заменил множество вызовов malloc одним, а затем разделил этот большой блок в своем приложении. Это было намного быстрее.

Я не рекомендую этот подход; это всего лишь иллюстрация того, что использование malloc может существенно повлиять на производительность.

Мой совет - измерить .

Answer 2

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

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

Это предполагает, что память, выделенная для кучи, достаточно велика в обоих случаях. В случае # 1 вам будет выделено больше общего объема памяти, так как каждое выделение включает в себя накладные расходы памяти для хранения метаданных, в результате вам может потребоваться вызов sbrk () или эквивалентного ему для увеличения кучи в случае # 1, что добавить дополнительные накладные расходы.

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

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

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

Answer 3

Маллок должен пройти через связанный список свободных блоков, чтобы найти один для выделения. Это требует времени. Итак, # 1 обычно будет медленнее:

• Чем чаще вы будете вызывать malloc, тем больше времени это займет - поэтому сокращение количества вызовов даст вам повышение скорости (хотя то, насколько это важно, будет зависеть от ваших конкретных обстоятельств).

• Кроме того, если вы неправильно распределите много маленьких блоков, то когда вы освободите эти блоки, вы фрагментируете кучу гораздо больше, чем если бы вы только выделяли и освобождали несколько больших блоков. Таким образом, вы, скорее всего, в конечном итоге будете иметь много маленьких свободных блоков в куче, а не несколько больших блоков, и поэтому вашим mallocs, возможно, придется искать дальше в списках свободного пространства, чтобы найти подходящий блок для выделения. Что снова сделает их медленнее.

Answer 4

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

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

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

Answer 5

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

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

Answer 6

Ответ заключается в том, что это зависит от того, что большая часть потенциальной медлительности скорее исходит из сочетаний malloc () и free (), и обычно # 1 и # 2 будут иметь одинаковую скорость.

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

Большая часть медлительности malloc происходит из двух источников

• поиск подходящего свободного блока среди ранее освобожденных (блоков)
• многопроцессорные проблемы с блокировкой

Написание моего собственного, почти совместимого со стандартами инструмента для замены malloc () malloc () && free () раз от 35% до 3-4%, и это серьезно оптимизировало эти два фактора. Вероятно, было бы схожей скоростью использовать какой-нибудь другой высокопроизводительный malloc, но наличие нашего собственного было более переносимым для эзотерических устройств и, конечно, позволяло в некоторых местах свободно использоваться.

Answer 7

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

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

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

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

Answer 8

Вы не определяете относительную разницу между «многими» и «немногими», но я подозреваю, что большинство malloc будут работать почти одинаково в обоих сценариях. Этот вопрос подразумевает, что каждый вызов malloc требует столько же ресурсов, сколько системный вызов и обновление таблицы страниц. Когда вы делаете вызов malloc, например, malloc (14) в среде, где нет мертвых мозгов, malloc фактически выделит больше памяти, чем вы просите, часто в несколько раз больше размера страницы системного MMU. Вы получаете свои 14 байтов, а malloc отслеживает вновь выделенную область, чтобы последующие вызовы могли просто вернуть часть уже выделенной памяти до тех пор, пока ОС не запросит больше памяти.

Другими словами, если я вызову malloc (14) 100 раз или malloc (1400) один раз, издержки будут примерно одинаковыми. Мне просто придется самостоятельно управлять большим выделенным блоком памяти.