Ваш комп’ютер має не просто оперативну пам’ять (RAM). Це хаотичний, фрагментований і постійно мінливий ландшафт пам’яті, який процесор (CPU) вдає нескінченним. Це і є реальність динамічних структур даних, що працюють на сучасному обладнанні.
Типова робоча станція оснащена 16–64 мегабайтами фізичної оперативної пам’яті. Але не дайте цим невеликим цифрам обдурити себе. Завдяки технології, яка називається віртуальною пам’яттю, система здійснює обмін даними між цією оперативною пам’яттю та жорстким диском. Процесор бачить ілюзію. Йому здається, що він має 200-500 мегабайт безперервного простору. Ця ілюзія працює. Код виконується. Але коли операційній системі доводиться звертатися до жорсткого диска для завантаження сторінки пам’яті, все сповільнюється. Ви відчуваєте це у вигляді затримок. Ви відчуваєте це у підвищенні обертів вентилятора. Незважаючи на зниження продуктивності, віртуальна пам’ять – це недорогий спосіб “розширити” обсяг вашої оперативної пам’яті. Це необхідний компромісний захід.
Припустимо, ми маємо чистий лист. Загальний обсяг пам’яті складає 50 мегабайт. Чи не більше. Чи не менше. Це наш бюджет.
Операційна система володіє цим 50-мегабайтним блоком. Вона поділяє цей пиріг. Нерівномірно. Ніколи не поступово.
Спочатку йде код. Інструкції, що виконуються для всіх запущених додатків, а також ядро самої операційної системи. Цей розділ статичний. Він не змінюється, поки програма працює. Далі йдуть глобальні змінні. Це загальні константи та прапори стану, до яких може звертатися будь-яка частина програми. Вони знаходяться в пам’яті з моменту запуску програми до завершення.
Потім йде стек.
Стек жорстко структурований. Він зростає та зменшується синхронно з викликами функцій. Коли ви викликаєте функцію, її локальні змінні та параметри розміщуються у стек. Коли функція завершує роботу, вони витягуються зі стека. Стек запам’ятовує порядок дзвінків. Він гарантує, що ви повернетеся до потрібного місця. Але він має максимальний розмір. Ви не можете попросити стек виділити більше пам’яті у процесі виконання. Якщо ви спробуєте це зробити, відбудеться переповнення стеку. Програма аварійно завершить роботу.
Коли програма завершує роботу, операційна система вивантажує її. Код, глобальні змінні, простір стека – все це стирається. Ця пам’ять переробляється. Вона готова до наступної програми.
Але ось у чому проблема. У будь-який момент приблизно 50 відсотків цього 50-мегабайтного простору може бути невикористовуваним. Чому? Тому що стек містить лише те, що виконується на даний момент. Код містить лише інструкції. Неперероблені фрагменти пам’яті розкидані. Це дірки.
Операційна система збирає ці дірки разом. Вона називає цей об’єднаний пул “купою (heap)”.
Саме тут відбувається динамічне виділення пам’яті. Купа – це єдине місце в пам’яті, де програма може запросити точний обсяг простору рівно в той момент, коли він потрібний. Ви не оголошуєте масив із 1000 цілих чисел під час компіляції. Ви не знаєте, чи вам знадобиться 1000 або 100 000 елементів. Ви чекаєте. Ви запускаєте код. Ви вирішуєте, що вам потрібний цей простір. Потім ви викликаєте malloc.
malloc означає memory allocate (виділення пам’яті). Вона захоплює блок із купи. Вона повертає покажчик. Ви використовуєте цей покажчик. Коли ви закінчите, ви викликаєте free. Блок повертається у пул.
Це фундаментальна різниця між статичною та динамічною пам’яттю. Стек автоматичний. Він прив’язаний до сфери видимості. Купа – ручна. Вона прив’язана до наміру.
Чому це має значення для вас? Тому що більшість помилок у складному програмному забезпеченні виникають не через погану логіку. Вони виникають через погане управління пам’яттю. Якщо ви виділяєте пам’ять у купі і забуваєте звільнити її, відбувається витік пам’яті. Об’єм доступної купи зменшується. Зрештою, система вичерпує простір. Програми зависають. Операційна система примусово завершує процеси. Ви втрачаєте незбережені дані.
І навпаки, якщо ви спробуєте виділити занадто багато пам’яті в стеку, ви перевищите ліміт стека. Програма аварійно завершує роботу.
Купа забезпечує гнучкість. Вона дозволяє створювати структури даних, які можуть зростати. Зв’язкові списки. Дерева. Графи. Жодну з цих структур не можна визначити під час компіляції із фіксованим розміром. Вони мають створюватися на льоту. Вони мають жити у купі.
Чи ідеальна купа? Ні. Вона фрагментується. У міру виділення та звільнення блоків різного розміру купа перетворюється на головоломку з відсутніми шматочками. Пошук безперервного блоку вільної пам’яті може бути повільним. Саме тому malloc іноді може займати помітний час. Їй доводиться шукати. Їй доводиться поєднувати фрагменти. Їй доводиться керувати цим хаосом.
Але без купи сучасна обчислювальна техніка впаде.
