Какова производительность кучи для выделения памяти?
Динамически выделяемая память поступает из стека или кучи. Я слышал, как некоторые люди говорят, что куча — это связанный список, хотя, если бы это было так, казалось бы, это было бы невероятно неэффективно. Например, если вы хотите выделить большой блок памяти, возможно, вам придется просмотреть большую часть списка, прежде чем найти что-то со свободным пространством. Кроме того, со временем количество блоков с небольшим объемом свободной памяти может становиться все больше и больше. В результате заявленное время выполнения некоторых алгоритмов в нотации big-O может не соответствовать действительности, поскольку они часто полагаются на выделение постоянного времени. Может ли кто-нибудь объяснить, как они реализованы и насколько они эффективны?
Ответы 1
Кучи управляются по-разному. В Интернете можно найти сотни различных реализаций malloc. Затем вы можете выбрать тот, который обеспечивает наилучшую производительность в вашем приложении.
Один из способов сделать кучу — выделить блоки только фиксированного размера. Например, ваш диспетчер кучи будет поддерживать списки блоков, скажем, 16, 32, 64, ...... байт. Диспетчер кучи просто извлекает следующий доступный блок, размер которого больше запрошенного.
Как обращаться с кучей, зависит от конкретной среды выполнения. Производительность не является абсолютной характеристикой системы, нет ничего универсально быстрого или медленного.