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

Ответ 1

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

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

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

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

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

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

Ответ 2

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

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

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

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

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

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

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

Ответ 3

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

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

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

Ответ 4

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

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

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

Ответ 5

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

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

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

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

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

Ответ 6

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

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

Ответ 7

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

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

Ответ 8

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

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

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

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