Записки программиста

Ни одна достаточно сложная современная программа не обходится без сборки мусора, ручной или автоматической. Тут уж ничего не поделаешь — оперативная память до сих пор остается дорогим ресурсом и мы не можем не освобождать ее по мере возможности. Так какие же существуют подходы к сборке мусора?

Ручное управление памятью

Ручное управление памятью просто до безобразия. Когда приложению нужно сколько-то памяти, оно говорит malloc или new, а когда память перестает быть нужной — free или delete. Жизнь прекрасна и удивительна, вопрос закрыт… или нет?

На практике оказывается, что возложение ответственности по управлению памятью на программиста зачастую приводит к ошибкам утечки памяти и висячих ссылок. Я уже не говорю о таких мелочах, что поддержка кода становится сложнее, чем в случае использования автоматического управления памятью.

Однако ручное управление памятью до сих пор широко применяется в Си, C++ и других языках. Хотя бы по той причине, что не во всякой задаче мы можем позволить себе использование сборщика мусора. В качестве примера таких задач на ум приходит разработка драйверов, компиляторов, кодеков/архиваторов, требовательных к производительности серверных приложений и трехмерных компьютерных игр.

Ручное управление памятью требует от программиста определенной дисциплины. По возможности данные желательно помещать в стек. Если данные требуется хранить в куче, желательно освобождать выделенную память в той же процедуре или том же методе, где она была выделена. Там, где можно обойтись без использования ссылок, данные следует хранить по значению. И так далее.

Счетчики ссылок

Самый простой механизм автоматического управления памятью заключается в использовании счетчиков ссылок. Идея следующая. Помимо самих данных в выделенном участке памяти также хранится счетчик ссылок на эти данные. При создании нового указателя счетчик увеличивается на единицу, а при уничтожении — уменьшается. Если после очередного уменьшения на единицу счетчик стал равен нулю, значит данные больше никем не используются и память следует освободить.

Этот метод практически не уступает по производительности ручному управлению памятью, но при этом позволяет существенно сократить количество присущих ему ошибок. Поддержка кода также упрощается. Существенная проблема данного подхода заключаются в том, что при наличии циклических ссылок некоторые счетчики никогда не обратятся в ноль и память утечет. Для борьбы с этим применяют слабые указатели (weakptr), которые не участвуют в подсчете ссылок.

Счетчики ссылок вполне успешно используется в C++ (так называемые умные указатели) и Perl.

Трассирующий сборщик мусора

Один из способов борьбы с циклическими ссылками заключается в следующем. Время от времени (например, раз в 1000 выделений памяти) мы должны собрать все ссылки из регистров, стека и глобальных переменных, после чего начать обходить по ссылкам все имеющиеся у нас данные. Во время обхода данные помечаются, как используемые. Те данные, которые не были помечены во время обхода, явно никем больше не используются и могут быть смело удалены.

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

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

Копирующий сборщик мусора

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

Когда в первой куче кончается место, мы обходим все данные и копируем их во вторую кучу. При этом данные естественным образом уплотняются, а ссылки на данные модифицируются. По завершении обхода кучи меняются местами, вторая куча становится активной, а первая — зарезервированной.

Тут имеет место масса преимуществ перед трассирующим сборщиком мусора. Во-первых, нам не нужно хранить какую-либо дополнительную информацию обо всех участках выделенной памяти (вопрос о деструкторах-финализаторах временно оставим в стороне). Во-вторых, благодаря уплотнению данных кэш процессора и память используются более эффективно.

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

Также следует обратить внимание на накладные расходы, связанные с необходимостью модификации указателей. И да, выполнение программы на время сборки мусора все еще приходится приостанавливать.

Если не ошибаюсь, подход с использованием двух куч либо используется, либо когда-то использовался в Java.

Трассирующий и уплотняющий сборщик мусора

Данные хранятся в одной куче. Когда в куче кончается место, выполняется обход по ссылкам, после чего используемые данные перемещаются ближе к началу кучи (в простейшей реализации — простым memmove), а ссылки на эти данные модифицируются. Получается нечто среднее между трассирующим и копирующим сборщиком мусора.

В результате долгоживущие данные скапливаются в начале кучи и не перемещаются при каждой сборке мусора. Память используется более эффективно, чем в случае использования двух куч. Однако алгоритм работы сборщика мусора усложняется. Для того, чтобы избежать лишнего копирования данных, по всей видимости, потребуется введение множества оптимизаций типа «не уплотнять данные, если уровень фрагментации в этой части кучи не превышает 25%» и тп.

Сборщик мусора по поколениям

В основу сборщика мусора по поколениям (generational garbage collector) положена идея о том, что большинство объектов (здесь будет удобно позаимствовать терминологию из ООП) перестают использоваться вскоре после создания. В связи с этим все объекты объединяются в различные поколения.

Новые объекты считаются объектами первого поколения. Если такой объект переживает первую (или в общем случае N-ую) сборку мусора, он помещается в множество объектов второго поколения, проверяемых реже. Если объекты из этого множества также переживают сборку мусора (или несколько сборок), они перемещаются в множество объектов третьего поколения, проверяемое еще реже, и так далее.

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

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

Гибридные решения

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

Дополнение: Также вас могут заинтересовать заметки Почему GC не работает и можно ли без него обойтись и Десять решений проблемы stop the world при использовании автоматической сборки мусора.

Метки: Алгоритмы, Разработка, Языки программирования.