Купа (нерозділена пам'ять)

}

Купа (англ. heap) — в інформатиці та програмуванні область зарезервованого адресного простору, умовна назва структури даних, поверх якої реалізована динамічна пам'ять програми.

Купа використовує пам'ять, виділену статично або запитану динамічно у операційної системи. Ця пам'ять використовується для розміщення об'єктів, динамічно створених програмою.

У будь-який момент часу існування купи вся пам'ять, на якій працює купа, розділена на зайняту і вільну. Зайнята пам'ять використана під розміщення об'єктів, вже створених і ще не звільнених до цього моменту часу. З обсягу вільної пам'яті примітиви роботи з купою можуть виділяти пам'ять під нові об'єкти. Для зберігання даних про приналежність пам'яті до зайнятої або вільною зазвичай використовується додаткова область пам'яті.

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

При розміщенні об'єкта реалізація примітиву «створити об'єкт» переглядає доступну купі вільну пам'ять у пошуках можливості розмістити в ній об'єкт необхідного розміру. Багато реалізації примітивів купи можуть у разі браку власної вільної пам'яті запитати додаткову пам'ять у операційної системи. У випадку, якщо з тих чи інших причин розмістити об'єкт неможливо, примітив «створити об'єкт» повідомляє про помилку (наприклад, malloc повертає 0). Обрана область пам'яті відзначається як зайнята. Примітив повертає адресу початку виділеної області. Під час видалення об'єкта реалізація примітиву «видалити об'єкт» зазначає, що область, раніше використана видаляється об'єктом, тепер вільна.

У проміжках між викликами примітивів «створити об'єкт» і «видалити об'єкт» виділена під об'єкт область пам'яті не може бути віддана ні під який інший об'єкт. Тому програма може вільно користуватися виділеної йому областю пам'яті. У той же час, після виклику примітиву «видалити об'єкт» звільнена область може бути використана повторно або віддана операційній системі, тому використання покажчика, отриманого раніше від примітиву «створити об'єкт» буде призводити до збоїв або непередбачуваною роботі програми.

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

Купа є довгий відрізок адрес пам'яті, поділений на підряд йдуть блоки різних розмірів. Блоки бувають вільні і зайняті. Для можливості виділення пам'яті шляхом повторного використання вільного блоку (без дорогого збільшення купи в цілому — вимагає системного виклику) у тому чи іншому вигляді потрібен список вільних блоків.

Для скорочення списку вільних блоків з метою зменшення часу його обходу завжди має сенс зливати 2 або 3 поспіль вільних блоку в один. Якщо вільний наступний блок, то його легко знайти, відступивши вперед на розмір який вивільняється блоку. З попереднім блоком все складніше, і тому має сенс зберігати розмір попереднього блоку (для його пошуку) в заголовку будь-якого блоку.

Список вільних блоків може бути організований по-різному, і від його організації прямо залежить продуктивність купи. Справа в тому, що головний час у операції виділення витрачається саме на пошук в цьому списку.

Дуже гарною реалізацією є кілька списків, кожен для свого розміру. Це дозволяє швидко проігнорувати явно занадто маленькі вільні блоки цілими списками, без перевірки кожного персонально.