Огляд механізмів збирання сміття, записки програміста
Жодна досить складна сучасна програма не обходиться без складання сміття, ручний або автоматичною. Тут вже нічого не поробиш - оперативна пам'ять до сих пір залишається дорогим ресурсом і ми не можемо не звільняти її в міру можливості. Так які ж існують підходи до складання сміття?
Ручне управління пам'яттю
Ручне управління пам'яттю просто до неподобства. Коли з додатком потрібно скільки-то пам'яті, воно говорить malloc або new, а коли пам'ять перестає бути потрібною - free або delete. Життя прекрасне і дивовижне, питання закрите ... чи ні?
На практиці виявляється, що покладання відповідальності з управління пам'яттю на програміста часто призводить до помилок витоку пам'яті і висячих посилань. Я вже не кажу про такі дрібниці, що підтримка коду стає складніше, ніж у випадку використання автоматичного управління пам'яттю.
Однак ручне управління пам'яттю до сих пір широко застосовується в Сі, C ++ та інших мовах. Хоча б з тієї причини, що не у всякій задачі ми можемо дозволити собі використання збирача сміття. Як приклад таких завдань на думку спадає розробка драйверів, компіляторів, кодеків / архиваторов, вимогливих до продуктивності серверних додатків і тривимірних комп'ютерних ігор.
Ручне управління пам'яттю вимагає від програміста певної дисципліни. По можливості дані бажано поміщати в стек. Якщо дані потрібно зберігати в купі, бажано звільняти виділену пам'ять в тій же процедурі або тому ж методі, де вона була виділена. Там, де можна обійтися без використання посилань, дані слід зберігати за значенням. І так далі.
Лічильники посилань
Найпростіший механізм автоматичного управління пам'яттю полягає в використанні лічильників посилань. Ідея наступна. Крім самих даних в виділеній ділянці пам'яті також зберігається лічильник посилань на ці дані. При створенні нового покажчика лічильник збільшується на одиницю, а при знищенні - зменшується. Якщо після чергового зменшення на одиницю лічильник став дорівнює нулю, значить дані більше ніким не використовуються і пам'ять слід звільнити.
Цей метод практично не поступається по продуктивності ручного управління пам'яттю, але при цьому дозволяє істотно скоротити кількість властивих йому помилок. Підтримка коду також спрощується. Істотна проблема даного підходу полягають в тому, що при наявності циклічних посилань деякі лічильники ніколи не звернуться в нуль і пам'ять витече. Для боротьби з цим застосовують слабкі покажчики (weakptr), які не беруть участі в підрахунку посилань.
Лічильники посилань цілком успішно використовується в C ++ (так звані «розумні покажчики») і Perl.
Трасуючий збирач сміття
Наскільки мені відомо, сьогодні в чистому вигляді трасуючий збирач сміття не використовується ніде. У більшості мов з автоматичним управлінням пам'яттю цей метод застосовується з різними модифікаціями, які будуть розглянуті трохи нижче.
Копіює збирач сміття
Для зберігання даних використовується дві купи. Одна з них використовується в даний момент, а друга зарезервована на майбутнє. Нові дані кладуться в першу купу.
Коли в першій купі закінчується місце, ми обходимо всі дані і копіюємо їх в другу купу. При цьому дані природним чином ущільнюються, а посилання на дані модифікуються. По завершенні обходу купи міняються місцями, друга купа стає активною, а перша - зарезервованої.
Тут має місце маса переваг перед трассирующим складальником сміття. По-перше, нам не потрібно зберігати будь-яку додаткову інформацію про всі ділянках виділеної пам'яті (питання про деструкторами-фіналізатор тимчасово залишимо осторонь). По-друге, завдяки ущільненню даних кеш процесора і пам'ять використовуються більш ефективно.
Але є і ряд недоліків. Перше, що кидається в очі - 50% виділеної пам'яті більшу частину часу не використовується. Але з іншого боку, в результаті фрагментації пам'яті невживаних може виявитися куди більший відсоток, так що, можливо, про це якраз особливо і не варто турбуватися. А ось що насправді викликає занепокоєння, це те, що багато довгоживучі дані будуть постійно копіюватися з однієї купи в іншу.
Також слід звернути увагу на накладні витрати, пов'язані з необхідністю модифікації покажчиків. І так, виконання програми на час збирання сміття все ще доводиться припиняти.
Якщо не помиляюся, підхід з використанням двох куп або використовується, або колись використовувався в Java.
Трасуючий і ущільнює збирач сміття
В результаті довгоживучі дані накопичуються на початку купи і не переміщаються при кожній збірці сміття. Пам'ять використовується більш ефективно, ніж в разі використання двох куп. Однак алгоритм роботи збирача сміття ускладнюється. Для того, щоб уникнути зайвого копіювання даних, по всій видимості, буде потрібно введення безлічі оптимізацій на зразок «не ущільнювати дані, якщо рівень фрагментації в цій частині купи не перевищує 25%» і тп.
Складальник сміття за їхніми
В основу збирача сміття по поколінням (generational garbage collector) покладено ідею про те, що більшість об'єктів (тут буде зручно запозичити термінологію з ООП) перестають використовуватися незабаром після створення. У зв'язку з цим всі об'єкти об'єднуються в різні покоління.
Нові об'єкти вважаються об'єктами першого покоління. Якщо такий об'єкт переживає першу (або в загальному випадку N-ую) збірку сміття, він поміщається в безліч об'єктів другого покоління, що перевіряються рідше. Якщо об'єкти з цієї множини також переживають збірку сміття (або кілька збірок), вони переміщаються в безліч об'єктів третього покоління, що перевіряється ще рідше, і так далі.
Правило при обході графа об'єктів просте - якщо нам зустрівся об'єкт з більш старшого покоління, ніж перевіряється в даний момент, далі в цьому напрямку не йдемо. Однак тут є тонкий момент. Оскільки об'єкти в загальному випадку можуть змінюватися, вони також можуть містити посилання на об'єкти більш молодого покоління. Тому під час виконання програми необхідно відстежувати ситуацію. коли більш старий об'єкт починає посилатися на більш молодий і додавати в цьому випадку молодий об'єкт в «кореневе безліч» об'єктів відповідного покоління. Інакше збирач сміття помилково видалить його, як недосяжний.
Прибирання сміття по поколінням істотно прискорює роботу трасуючого збирача сміття і тому набула широкого поширення. Зокрема, такий підхід використовується в Python.
гібридні рішення
На практиці описані вище підходи часто комбінують і модифікують, в результаті чого виходить, наприклад, що ущільнює трасуючий збирач сміття по поколінням. У деяких мовах надається кілька збирачів сміття на вибір. Скажімо, один з них може більш економно використовувати пам'ять, а інший - швидше проводити збірку сміття. Нарешті, бувають ще й паралельні збирачі сміття, але це питання вже виходить за рамки поста.