что такое сборка мусора в программировании
Что такое сборщик мусора в программировании
Чисто и там, где метут, и там, где не мусорят.
В этой статье — важное понятие из компьютерной теории. Читайте, если хотите разбираться в устройстве компьютеров и памяти. Особенно полезно для бэкенда и разработки высоконагруженных систем.
Ситуация
Когда мы пишем программы, мы обычно действуем по такому принципу:
В итоге наши программы могут обрабатывать сотни, тысячи и миллионы переменных с числами и текстом, и для нас это в порядке вещей. Компьютер, собственно, и создан для того, чтобы обрабатывать за нас эти массивы данных.
Проблема
Когда мы объявляем новую переменную, под неё выделяется кусок памяти, где она будет храниться. Часто бывает такое, что даже если эта переменная потом нигде не используется, то она всё равно занимает место в памяти.
Если таких переменных будет много, то программа может занять много памяти. Когда память забивается, компьютер начнёт тормозить. Вся занятая память освободится только тогда, когда программу закроют, а до того времени всё будет тормозить.
👉 Особенно это опасно на контроллерах или носимых устройствах: там обычно мало памяти и её легко заполнить. А контроллеры управляют не только умным домом, но и, например, самолётами или промышленными станками. Если не подумать о памяти в контроллере двигателя самолёта, то у тебя на третьем часу полёта откажет двигатель.
Решение — очистка мусора и управление памятью
Кто-то в программе должен озаботиться тем, чтобы ненужные переменные умирали и высвобождали занятую ранее память. В этом деле есть два подхода: ручной и автоматический.
В ручном режиме программист сам следит за каждой переменной, объектом и сущностью. Когда объект или переменная больше не нужны, он прямо в коде пишет: «Этот готов, уносите». Для этого он использует специальные команды-деструкторы, которые удаляют переменную и освобождают память. Теперь эту область памяти может взять себе другая программа или переменная, тогда ресурсы расходуются максимально экономно.
Автоматический режим называется сборкой мусора. Это такая отдельная мини-программа внутри основной программы, которая периодически пробегает по объектам и переменным в коде и смотрит, нужны они или нет. Если нет — сборщик мусора сам удаляет переменную и освобождает память.
Особенности ручного управления
При ручной работе с памятью программист получает полный контроль над ресурсами и может в любой момент освободить уже ненужную память. Это значит, что можно написать такую программу, когда в сумме переменным нужно 500 мегабайт памяти, но за счёт своевременного удаления всегда заняты только 100 мегабайт.
Ручное управление идеально для систем со слабыми ресурсами и систем реального времени — там, где программа не имеет права тормозить.
Вместе с тем такой подход требует высокой квалификации программиста. Нужно точно знать, какая переменная тебе нужна и когда; как устроены циклы твоей программы; как работает процессор и куда он может посмотреть в тот или иной момент.
Особенности автоматического сборщика
Автоматический сборщик сам ходит по программе во время исполнения и аккуратно подчищает память, как только находит мусор.
Вроде хорошо, но нет. Сборщик мусора тоже работает неидеально:
❌ Сборщик удаляет только те переменные, в которых он уверен стопроцентно. Если есть один шанс, что переменная может когда-нибудь понадобиться, — её оставляют в памяти. То есть эффективность не стопроцентная.
❌ Сборщик — это отдельная программа, которая работает вместе с основной. И ей тоже нужны ресурсы и процессорное время. Это замедляет работу основной программы. Как если бы уборщик приходил в отделение Сбербанка посреди рабочего дня и заставлял всех на два часа покинуть рабочие места, чтобы он тут провёл влажную уборку.
❌ Если рабочей памяти очень мало, то сборщик будет работать постоянно. Но ему тоже нужна своя память для работы. И может получиться, что сборщик, например, занимает 100 МБ, а освобождает 10 МБ. Может оказаться так, что без сборщика программа будет работать эффективнее.
Автоматические сборщики — добро или зло?
Тут у разработчиков мнения разделяются.
С точки зрения быстродействия сборщики — однозначно зло, потому что они всегда замедляют работу. Есть ситуации, когда замедление незаметно, а бывает, когда оно критично.
С точки зрения удобства сборщики — однозначно добро. Пишешь полезный код, а умная машина сама за тобой прибирается. Программы выходят быстрее, для их поддержки нужно меньше людей, которые могут быть менее компетентными.
Что выбрать?
С выбором интересная ситуация.
Если вы пишете приложения для iOS или OSX, вам нельзя использовать сборщики мусора из соображений быстродействия.
Языки типа JavaScript и Ruby собирают мусор сами, вы об этом можете даже никогда не узнать.
В некоторые языки можно подключить сбор мусора, пожертвовав производительностью — например, в Java, C или C++.
Путь самурая — вручную управлять памятью и делать суперпроизводительные приложения, которые летают даже на процессоре от карманного калькулятора. Но жизнь сложна и разнообразна, и однажды за всеми нами тоже придут наши собственные… сборщики.
Избавляемся от мусора в Java
Что такое сборка мусора, зачем она нужна и как работает
Для работы любого приложения требуется память. Однако память компьютера ограничена. Поэтому важно ее очищать от старых неиспользуемых данных, чтобы освободить место для новых.
Кто занимается этой очисткой? Как и когда очищается память? Как выглядит структура памяти? Давайте разберем с этим подробнее.
Структура памяти Java
Память в Java состоит из следующих областей:
Структура памяти Java
Native Memory — вся доступная системная память.
Stack (стек) — используется для хранения локальных переменных и стека вызовов метода. Для каждого потока выделяется свой стек.
Metaspace (метаданные) — в этой памяти хранятся метаданные классов и статические переменные. Это пространство также является общими для всех. Так как metaspace является частью native memory, то его размер зависит от платформы. Верхний предел объема памяти, используемой для metaspace, можно настроить с помощью флага MaxMetaspaceSize.
PermGen (Permanent Generation, постоянное поколение) присутствовало до Java 7. Начиная с Java 8 ему на смену пришла область Metaspace.
CodeCache (кэш кода) — JIT-компилятор компилирует часто исполняемый код, преобразует его в нативный машинный код и кеширует для более быстрого выполнения. Это тоже часть native memory.
Сборка мусора: введение
Что такое «мусор»? Мусором считается объект, который больше не может быть достигнут по ссылке из какого-либо объекта. Поскольку такие объекты больше не используются в приложении, то их можно удалить из памяти.
Например, на диаграмме ниже объект fruit2 может быть удален из памяти, поскольку на него нет ссылок.
Мусор
Что такое сборка мусора? Сборка мусора — это процесс автоматического управления памятью. Освобождение памяти (путем очистки мусора) выполняется автоматически специальным компонентом JVM — сборщиком мусора (Garbage Collector, GC). Нам, как программистам, нет необходимости вмешиваться в процесс сборки мусора.
Источник: Oracle.com
Сборка мусора: процесс
Для сборки мусора используется алгоритм пометок (Mark & Sweep). Этот алгоритм состоит из трех этапов:
Sweep (очистка). На этом шаге освобождается память, занятая объектами, не отмеченными на предыдущем шаге.
Compact (уплотнение). Объекты, пережившие очистку, перемещаются в единый непрерывный блок памяти. Это уменьшает фрагментацию кучи и позволяет проще и быстрее размещать новые объекты.
Mark & Sweep GC
Поколения объектов
Что такое поколения объектов?
Для оптимизации сборки мусора память кучи дополнительно разделена на четыре области. В эти области объекты помещаются в зависимости от их возраста (как долго они используются в приложении).
Young Generation (молодое поколение). Здесь создаются новые объекты. Область young generation разделена на три части раздела: Eden (Эдем), S0 и S1 (Survivor Space — область для выживших).
Old Generation (старое поколение). Здесь хранятся давно живущие объекты.
Поколения в куче
Что такое Stop the World?
Когда запускается этап mark, работа приложения останавливается. После завершения mark приложение возобновляет свою работу. Любая сборка мусора — это «Stop the World».
Что такое гипотеза о поколениях?
Как уже упоминалось ранее, для оптимизации этапов mark и sweep используются поколения. Гипотеза о поколениях говорит о следующем:
Большинство объектов живут недолго.
Если объект выживает, то он, скорее всего, будет жить вечно.
Этапы mark и sweep занимают меньше времени при большом количестве мусора. То есть маркировка будет происходить быстрее, если анализируемая область небольшая и в ней много мертвых объектов.
Таким образом, алгоритм сборки мусора, использующий поколения, выглядит следующим образом:
Сборка мусора поколениями
Новые объекты создаются в области Eden. Области Survivor (S0, S1) на данный момент пустые.
Когда область Eden заполняется, происходит минорная сборка мусора (Minor GC). Minor GC — это процесс, при котором операции mark и sweep выполняются для young generation (молодого поколения).
После Minor GC живые объекты перемещаются в одну из областей Survivor (например, S0). Мертвые объекты полностью удаляются.
По мере работы приложения пространство Eden заполняется новыми объектами. При очередном Minor GC области young generation и S0 очищаются. На этот раз выжившие объекты перемещаются в область S1, и их возраст увеличивается (отметка о том, что они пережили сборку мусора).
При следующем Minor GC процесс повторяется. Однако на этот раз области Survivor меняются местами. Живые объекты перемещаются в S0 и у них увеличивается возраст. Области Eden и S1 очищаются.
Объекты между областями Survivor копируются определенное количество раз (пока не переживут определенное количество Minor GC) или пока там достаточно места. Затем эти объекты копируются в область Old.
Major GC. При Major GC этапы mark и sweep выполняются для Old Generation. Major GC работает медленнее по сравнению с Minor GC, поскольку старое поколение в основном состоит из живых объектов.
Преимущества использования поколений
Minor GC происходит в меньшей части кучи (
2/3 от кучи). Этап маркировки эффективен, потому что область небольшая и состоит в основном из мертвых объектов.
Недостатки использования поколений
В каждый момент времени одно из пространств Survivor (S0 или S1) пустое и не используется.
Сборка мусора: флаги
В этом разделе приведены некоторые важные флаги, которые можно использовать для настройки процесса сборки мусора.
Флаг
Описание
Первоначальный размер кучи
Максимальный размер куча
Отношение размера Old Generation к Young Generation
Отношение размера Eden к Survivor
Возраст объекта, когда объект перемещается из области Survivor в область Old Generation
Типы сборщиков мусора
Сборщик мусора
Описание
Преимущества
Когда использовать
Флаги для включения
Использует один поток.
Эффективный, т.к. нет накладных расходов на взаимодействие потоков.
Работа с небольшими наборами данных.
Использует несколько потоков.
Многопоточность ускоряет сборку мусора.
В приоритете пиковая производительность.
Допустимы паузы при GC в одну секунду и более.
Работа со средними и большими наборами данных.
Для приложений, работающих на многопроцессорном или многопоточном оборудовании.
Выполняет некоторую тяжелую работу параллельно с работой приложения.
Может использоваться как на небольших системах, так и на больших с большим количеством процессоров и большим количеством памяти.
Когда время отклика важнее пропускной способности.
Паузы GC должны быть меньше одной секунды.
Выполняет всю тяжелую работу параллельно с работой приложения.
В приоритете время отклика.
Сборщики мусора в Java
Инструменты мониторинга GC
Что мониторить?
Частота запуска сборки мусора. Так как GC вызывает «stop the world», поэтому чем время сборки мусора меньше, тем лучше.
Длительность одного цикла сборки мусора.
Как мониторить сборщик мусора?
Для мониторинга можно использовать следующие инструменты:
Для включения логирования событий сборщика мусора добавьте следующие параметры JVM:
Сборщик мусора на С++
Привет, Хабр! Эту статью я задумал довольно давно. Речь в ней пойдет о простейшем копирующем сборщике мусора на С++. У него довольно много ограничений (часть не мешает, часть можно обойти, если задаться целью написать какую-то серьезную библиотеку, а для кое-чего неплохо было бы заиметь зачаточную поддержку от языка), зато и кода в нем чуть больше 100 строк. Заинтересовавшихся прошу под кат. Там минимум ООП, простейшие шаблоны и жуткие магические ритуалы с указателями.
Начнем с начала. Что такое сборщик мусора и для чего он нужен?
Сборщик мусора (Gargabe Collector, GC) — это такой способ управления ресурсами, обычно — оперативной памятью, выделяемой в куче. Суть проста — программист просит сборщик мусора выделить ему кусок памяти, а тот уже сам определяет, когда он станет не нужен и может быть освобожден. Это решает большинство проблем с утечками памяти, хотя и лишает возможности героически превознемогать ошибки сегментации. Какая жалость.
Сборщики мусора бывают двух видов — консервативные и копирующие.
Нечто вроде первого типа реализовано в последнем стандарте. Механизм shared_ptr позволяет отказаться от явного использования операторов new и delete. Он считает ссылки, которые указывают на объект и избавляется от него, когда их число становится нулевым. Проблемы с этим подходом возникают, когда создается множество мелких объектов с коротким, но не одинаковым сроком жизни. В результате, куча превращается в кровавое месиво из валидных объектов и лоскутков свободной памяти по несколько десятков байт. Из-за этого создание новых объектов начинает занимать целую вечность и нативный код начинает завидовать Питону.
Для решения этой проблемы — фрагментации кучи – придуман второй тип сборщиков — копирующий. До поры до времени, его стратегия борьбы с мусором — созерцание. Когда же его становится слишком много, он делает следующее:
1. Копирует все нужные данные в другую область памяти.
2. Меняет все указатели на актуальные.
3. Освобождает всю память, которая уже не используется.
Сразу уточню, что я не смотрел вплотную ни одного алгоритма сборки мусора, ни как работают «взрослые» библиотеки GC для С++. Вероятно, у алгоритма, который я сейчас опишу, есть название, возможно, именное, но в тут я обойдусь без ссылок на источники.
Чтобы определить объекты, которые еще нужны программе, предлагаю рассматривать память как обычный граф. Тогда «живыми» объектами после сборки мусора будут считаться те, которые достижимы через цепочку указателей. Здесь возникают вопросы. Во-первых — как для любого возможного объекта, который программист может попросить создать, определить, где у него находятся указатели. Первый способ — с помощью шаблонной магии для каждого класса объектов создавать свой собственный аллокатор. Ужасная идея по многим причинам. Второй — в заголовке каждого объекта писать всю информацию, которая нужна для работы GC (ах да, для классов с виртуальными функциями эта реализация не годится. Пара идей у меня есть, при необходимости).
Заголовок тоже можно использовать многими способами. Мой — самый простой, который вообще может быть (для реализации, но не использования). Во-первых, каждый объект, который планирует создаваться через сборщик мусора, должен иметь в начале своего определения эту структурку:
Во-вторых, сразу после заголовка, и нигде более, должны идти все указатели, которые также относятся к сборщику мусора. Соответственно, в gcData[REF_COUNT] будет хранится их количество. Это одно из ограничений, которое накладывает моя реализация. В gcData[STRUCT_SZ] будет храниться размер структуры в байтах. Назначение указателя я раскрою позднее. Что удобно, размер структуры оказался равен размеру указателя (сейчас 2014, народ!).
Отлично, теперь мы сможем обойти всю нашу память. Вопрос в том, откуда начать обход. Единственная область памяти, которая нам стопроцентно доступна в любой момент — это стек. Проблема та же, что и с указателями в структурах — мы понятия не имеем, какая кучка байт указывает на объект GC. Поэтому, нужно расположение каждого такого указателя записывать явно.
Класс stackRef действует просто. При инициализации, он всего-лишь добавляет свой адрес в стек ссылок. Деструктор, соответственно, удаляет неактуальный адрес из того же стека. Работа стека вызовов и конструкторов с деструкторами синхронизирована, так что аномалий возникать не будет.
В классе нужно переопределить кучу операторов — разыменования, присваивания, etc, но этим появится смысл заниматься не раньше, чем со мной свяжутся парни из Boost Foundation.
Вспомогательные структуры готовы. Можно перейти к выделению памяти.
Классной фичей такого способа управления ресурсами является именно способ их выделения. Стандартному аллокатору С++ приходится после каждого delete обновлять списки свободных блоков, а после new находить среди блоков подходящий, потом дробить его на два мелких блока, а потом что-то еще, что там делают современные аллокаторы. В случае сборщика мусора, операция delete просто не нужна, так что вся занятая память будет идти одним сплошным блоком. Чтобы создать новый объект, нужно всего лишь увеличить размер этого блока, т. е. сдвинуть один указатель. Простая операция, которая выполняется за O(1). Реально перестало это казаться такой уж замечательной идеей, из-за того, что провоцирует кучу сборок тогда, когда можно было бы просто переиспользовать уже не нужную память, но пока можно остановиться на этом.
Разделим память, подконтрольную сборщику мусора на куски по 4 килобайта и свяжем их в список. На самом деле, чуть больше 4 килобайт, но это вопрос моей лени.
firstChunk — начало списка, currentChunk — последний созданный блок памяти. сurrentOffset — начало свободного сегмента памяти относительно currentChunk.
Здесь неочевидных моментов уже больше. Разберем 12-ую строчку.
На этом этапе нам удобнее не думать о том, какой именно тип у нового объекта. Мы точно знаем, что у него есть наш gcHeader, и этого пока достаточно.
После того, как мы выделили память для нового объекта, нужно инициализировать его заголовок. Что может означать загадочное присваивание
Для этого снова посмотрим на определение заголовка
Ключевое слово union означает, что и массив gcData и указатель post_gcAddress располагаются по одному адресу. Это полезно для экономии памяти, но проблема в том, что С++ не запоминает, как данные в union использовались в последний раз — как массив, или как ссылка. Помогает такая особенность архитектур процессоров, как необходимость выравнивания данных.
Если вкратце, то любые переменные длиннее одного байта, должны располагаться на адресах, которые кратны машинному слову в байтах. Нарушение выравнивания на современных процессорах сильно замедляет работу программы, а старые ARM вообще отказываются в таких условиях работать. В результате, 2 или 3 младших бита указателя могут быть использованы как угодно по усмотрению программиста. Например, при реализации красно-черных деревьев, последний бит часто задействуют вместо булевой переменной.
Тут — то же самое. Если младший бит равен единице, то эти восемь байт — гарантированно массив из двух int. Можно, например, использовать еще один бит, чтобы указывать сборщику мусора, что-то типа «это ссылка на полиморфный объект, у него есть указатель vtable, не затри его».
Ну и небольшая обертка над функцией, чтобы использование аллокатора не вызывало особой боли.
Тут следует поставить emplace new, чтобы корректно инициализировались объекты с конструкторами. Как видно, класс объекта, который мы хотим создать, должен иметь статическую константу refCount. Её можно вычислять автоматически с помощью внешнего препроцессора. В противном случае, я вижу тут как минимум три способа отстрелить себе ногу.
Перед тем, как пользоваться этой функцией, нужно инициализировать кучу.
Пора посмотреть на реализацию самой сборки мусора.
Первая функция, gcCollect, должна начать кучу с чистого листа, не забыв сохранить указатели на старый список. Эти строки почти повторяют инициализацию.
Далее, мы с каждого указателя, который хранится на стеке, начинаем процесс сборки.
А теперь просто освобождаем ненужную память.
Обратите внимание, delete вызывается только для больших блоков памяти. Таким образом, деструкторы объектов в сборщике мусора никогда не будут вызваны. Это не проблема для классов, у которых деструкторы только освобождают память, но нет возможности, например, автоматически закрывать соединения и файловые дескрипторы. Mark & Sweep-алгоритмы могут помочь с этим, но и писать их сильно сложнее.
Последний штрих — функция gcMove.
Разберем функцию с середины. Нам нужна возможность перенаправлять ссылки, поэтому в функцию передается указатель на указатель на данные.
GC выделяет объекту нужное количество памяти в новой куче (он знает, сколько, из заголовка) и копирует все данные из старой инкарнации в новую. Потом он пишет новый адрес объекта в старый заголовок. Теперь, если на объект указывает несколько ссылок, алгоритм сможет определить, что объект уже один раз перемещался (младший бит, гарантированно, 0) и не станет копировать его лишний раз впоследствии. Осталось перенаправить старый указатель на новую копию объекта.
Теперь, нужно разобраться с указателями, самого объекта. С ними нужно сделать то же самое. Строчка
получает указатель на первую ссылку в структуре (если она есть, конечно). Помним, что sizeof(gcHeader) == sizeof(void*). В противном случае, это будет занимать на пару строк больше.
Что делать дальше, вопрос уже спорный. Я просто для каждого указателя рекурсивно вызываю функцию gcMove. Такой алгоритм соответствует обходу графа в глубину. Однако, это не лучший выбор.
Киллер-фича копирующих сборщиков мусора для меня — это возможность поддерживать локальность по ссылкам. Если коротко, объекты, которые ссылаются друг на друга, и в памяти тоже должны находиться как можно ближе. Так процессор сможет эффективнее использовать свою кэш-память.
Мой GC такого не умеет. Я выбрал обход в глубину из-за простоты. Желательно перемещать объекты в порядке обхода в ширину. Будет совсем здорово заморочиться и выстраивать объекты в памяти в соответствии со статистикой обращений к ним, как в этом алгоритме, чтобы добиться оптимального количества промахов.
На этом всё. Осталось продемонстрировать работу со сборщиком.
В качестве примера возьму простейшее дерево поиска.
Как уже упоминалось, в начале должен стоять заголовок, а после заголовка все указатели на объекты нашей кучи.
Обычное добавление в дерево. Обратите внимание, как используется gcAlloc.
stFind возвращает ссылку на поддерево с нужным ключом, stPrint распечатывает ключи и адреса поддеревьев, stCut обрезает поддерево, в котором хранится искомый ключ.
Как видно работа со структурами для программиста особо не меняется. Что тут происходит:
1. Мы произвольно заполняем дерево поиска.
2. Создаем еще одну стековую ссылку на один из элементов, чтобы проверить, как GC реагирует на множественные ссылки на один объект.
3. Распечатываем дерево, additionalReference и currentOffset.
4. Вхолостую вызываем сборку мусора.
5. Снова распечатываем дерево. Все указатели, которые нужны — поменялись.
6. Обрезаем одно поддерево и снова вызываем сборку мусора. Всё снова работает как надо. Обратите внимание currentOffset уменьшился, а корень дерева вернулся на тот же адрес, по которому находился в первый раз.
Выводы
Итак, в С++ можно использовать Garbage Collector. Причем, вполне себе симпатичный, на мой замыленный взгляд, да еще и с минимальным оверхедом. Попробую перечислить всё, что нужно сделать, чтобы он был действительно удобным и полезным.
Сначала — организационные моменты.
1. Глобальные переменные — это, конечно, совсем не клёво. Нужно всё оформить как человеческий класс и\или аллокатор С++.
2. Заставлять в каждый класс вставлять хедер — почти садизм. Нужно просто давать отнаследоваться от абстрактного класса, у которого должны быть два метода — getSize и getLayout. Последний должен возвращать ссылку на массив, в котором хранятся относительные координаты всех указателей (затея с «все ссылки стоят начале» ну совсем не годится для чего-то серьезного). Этот массив однозначно должен заполняться автоматически, но я пока что не представляю, как это можно реализовать.
Следующий вопрос — автоматическая сборка. Когда выдвинули саму идею GC, никто не подразумевал, что кто-то реально будет постоянно вызывать что-то вроде функции gcCollect, всё должно происходить само по себе. Но С++ — особый случай. Он славится тем, что весь поток выполнения под носом, или, по крайней мере, предсказуем. Своенравный Garbage Collector любого другого языка здесь — это практически идеологическое преступление. Так что, у него должно быть как минимум два режима:
1. Прозрачный.
2. Бросок исключения после исчерпания некой квоты памяти. Тут уже программисту решать — убраться или выделить память форсированно.
И еще один вопрос. Многопоточность. Тут всё плохо. Чтобы начать сборку мусора, нужно приостановить все потоки, чтобы ничего не сломать. В итоге придется написать половину JVM. Самым лучшим решением мне кажется его отсутствие. Для каждого потока можно просто создавать свой выделенный GC, а если понадобится передать что-то другому подпроцессу, то обычные shared_ptr никто не отменял. Без разделяемой памяти жить, как правило, гораздо веселее.
Закончим на печальной ноте. Такой сборщик мусора тотально несовместим ни с одной готовой библиотекой. Их объекты не смогут предоставлять необходимые данные. Несмотря на то, что std::list, std::map и std::set только выиграют, если переписать их специально под GC, переделывать N гигабайт исходников Boost, например, совершенно бесперспективно. Однако, для борьбы с фрагментацией в случае маленьких объектов, мне такая штука кажется очень даже полезной.