Куча (память)

У этого термина существуют и другие значения, см. Куча (значения).

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

Организация

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

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

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

Принцип работы

Для размещения и удаления динамических объектов используются примитивы «создать объект» (например, malloc) и «удалить объект» (например, free). Кроме того, перед началом работы программы выполняется инициализация кучи, в ходе которой вся изначально выделенная под кучу память отмечается как свободная.

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

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

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

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

Алгоритмы кучи и производительность

Куча — длинный отрезок адресов памяти, поделенный на подряд идущие блоки различных размеров.

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

Для сокращения списка свободных блоков с целью уменьшения времени его обхода всегда имеет смысл сливать 2 или 3 подряд идущих свободных блока в один. Если свободен последующий блок, то его легко найти, отступив вперед на размер освобождаемого блока. С предыдущим блоком все сложнее, и потому имеет смысл хранить размер предыдущего блока (для его поиска) в заголовке любого блока.

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

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

См. также

• Динамическая память
• malloc
• free

Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Проставив сноски, внести более точные указания на источники. Добавить иллюстрации.