Сборка мусора на основе трассировки

C# и .NET Framework --- Оптимизация приложений .NET Framework --- Сборка мусора на основе трассировки

Сборка мусора на основе трассировки применяется для управления динамической памятью в .NET CLR, Java VM и в других управляемых окружениях. В этих окружениях не используются счетчики ссылок, ни в какой форме. Разработчику не требуется явно освобождать память - об этом позаботится сборщик мусора. При использовании сборки мусора на основе трассировки в объекты не добавляются счетчики ссылок, и обычно освобождение памяти не выполняется, пока уровень ее использования не достигнет некоторого порога.

Когда запускается цикл сборки мусора, он начинается с фазы маркировки (mark phase), в ходе которой выявляются все объекты, на которые существуют ссылки в приложении (живые объекты). После определения множества живых объектов, сборщик приступает к выполнению фазы чистки (sweep phase), в ходе которой он освобождает память, занимаемую неиспользуемыми объектами. В заключение выполняется фаза сжатия (compact phase), в которой сборщик мусора перемещает живые объекты так, чтобы они располагались в памяти непосредственно друг за другом.

В этой статье мы подробно исследуем различные проблемы, связанные с трассировочной сборкой мусора. Однако в общих чертах эти проблемы можно обозначить уже сейчас:

• Стоимость выделения памяти: стоимость выделения памяти сопоставима с выделением кадра на стеке, потому что отсутствует необходимость предусматривать сохранение какой-либо информации, которая потребуется при освобождении объекта. Выделение памяти заключается в наращивании указателя.

• Стоимость освобождения памяти: сборка мусора выполняется циклически, а не распределяется примерно равномерно по всему времени выполнения приложения. Это имеет свои преимущества и недостатки (в частности для ситуаций, когда требуется низкое время задержки).

• Фаза маркировки: поиск объектов по ссылкам требует значительных затрат от среды выполнения. Ссылки на объекты могут храниться в статических переменных, локальных переменных потоков выполнения, передаваемых как указатели в неуправляемый код, и так далее. Трассировка всех возможных ссылок на каждый доступный объект - далеко не тривиальная задача, и часто сопряжена с затратами на итерации через коллекции.

• Фаза чистки: перемещение объектов в памяти требует времени, что может оказаться невозможным для очень больших объектов. С другой стороны, устранение пустых, неиспользуемых пространств между объектами способствует локальности ссылок (locality of reference), потому что объекты, создававшиеся одновременно, наверняка окажутся в памяти по соседству. Кроме того, выполнение этого этапа избавляет от необходимости использовать дополнительный механизм дефрагментации, так как объекты всегда занимают непрерывную область памяти, без разрывов. Наконец, это означает, что механизм выделения памяти не должен учитывать «дырки» между объектами при поиске свободного места - можно использовать простую стратегию, основанную на увеличении указателя.

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

Фаза маркировки

На этапе маркировки, сборщик мусора выполняет обход графа всех объектов, на которые ссылается приложение. Для успешного обхода графа и предотвращения ошибок первого (false positives) и второго (false negatives) рода (обсуждается ниже), сборщику мусора необходимо множество опорных точек, откуда можно будет начать обход ссылок. Эти отправные точки называют корнями (roots). Как можно заключить из названия, они образуют корни ориентированных графов ссылок.

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

Локальные корни

Наиболее типичными представителями корней являются локальные переменные; единственная локальная переменная может быть корнем целого графа объектов. Например, взгляните на следующий фрагмент кода в теле объекта Main приложения, который создает объект System.Xml.XmlDocument и вызывает его метод Load:

static void Main(string[] args)
{
    XmlDocument doc = new XmlDocument();
    doc.Load("Data.xml");
    Console.WriteLine(doc.OuterXml);
}

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

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

Поддерживает ли сборщик мусора в .NET такую возможность? Давайте рассмотрим следующий код, создающий объект System.Threading.Timer и инициализирующий его функцией обратного вызова, которая вызывает сборку мусора обращением к методу GC.Collect():

using System;
using System.Threading;

class Program
{
    static void Main(string[] args)
    {
        Timer timer = new Timer(OnTimer, null, 0, 1000);
        Console.ReadLine();
    }

    static void OnTimer(object state)
    {
        Console.WriteLine(DateTime.Now.TimeOfDay);
        GC.Collect();
    }
}

Если запустить этот код в отладочном режиме (скомпилировав его из командной строки, вызвав компилятор без ключа /optimize +), можно будет увидеть, что функция OnTimer() вызывается каждую секунду, как и следовало ожидать, явно свидетельствуя, что объект Timer не утилизируется сборщиком мусора. Однако, если скомпилировать программу с ключом /optimize +, функция будет вызвана всего один раз! Иными словами, объект Timer будет утилизирован и прекратит вызывать функцию обратного вызова. Это вполне обычное (и далее желаемое) поведение, потому что локальная ссылка на объект не может больше рассматриваться как активный корень сразу после достижения инструкции вызова метода Console.ReadLine(). По этой причине объект утилизируется сборщиком мусора, и получается результат, неожиданный для тех, кто не следил за нашим обсуждением!

Энергичная сборка мусора

Такое «нетерпение» по отношению к локальным корням в действительности поддерживается динамическим компилятором (Just-In-Time Compiler, JIT) среды выполнения.NET. Сборщик мусора понятия не имеет, когда локальная переменная выходит из употребления в пределах метода. Эта информация записывается в специальные таблицы JIT-компилятором в процессе компиляции метода. Для каждой локальной переменной JIT-компилятор записывает в таблицу адрес самой первой и самой последней инструкции, где локальная переменная остается активным корнем. Эта таблица используется сборщиком мусора в процессе обхода ссылок на стеке. (Обратите внимание, что локальные переменные могут храниться не только на стеке, но и в регистрах процессора, и таблицы JIT-компилятора должны содержать информацию об этом.)

class Widget
{
    public virtual void Use()
    {
    }
}

// ...

class Program
{
    static void Main(string[] args)
    {
        Widget a = new Widget();
        a.Use();

        // ... какой-то код

        Widget b = new Widget();
        b.Use();

        // ... какой-то код

        Foo(); // вызов статического метода
    }
}

// Скомпилированный CIL-код на x86:
; начало метода не показано (для краткости)
call 0x0a890a30        ; конструктор Widget..ctor
+0x14  mov esi, eax    ; esi теперь хранит ссылку

       mov ecx, esi
       mov eax, dword ptr [ecx]
		
; остальные инструкции, составляющие последовательность вызова функции 
+0x24  mov dword ptr [ebp-12], eax      ; ebp-12 теперь хранит ссылку на объект
       mov ecx, dword ptr [ebp-12]
       mov eax, dword ptr [ecx]
		
; остальные инструкции, составляющие последовательность вызова функции
+0x34  call 0x0a880480                  ; вызов статического метода Foo()
;конец метода не показан для краткости

// Таблицы, сгенерированные JIT-компилятором и используемые сборщиком мусора:

Регистр или стек    Смещение начала    Смещение конца
    ESI                 0x14               0x24
    EBP-12              0x24               0x34

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

А как быть, если потребуется явно продлить жизнь таймера до конца выполнения метода? Сделать это можно несколькими способами. Можно было бы использовать статическую переменную (которая является еще одной разновидностью корня, о которой будет рассказываться чуть ниже). Как вариант, в конец метода можно поместить инструкцию использования таймера (например, вызвать метод Timer.Dispose()). Но наиболее очевидный путь достижения цели - вызвать метод GC.KeepAlive(), гарантирующий сохранность ссылки на объект.

Как действует GC.KeepAlive? Кому-то он может показаться неким таинством, скрытым в недрах CLR. Однако в действительности все гораздо проще - его можно написать самому, что мы и сделаем. Если передать ссылку какому-либо методу, который не может быть встроен, JIT-компилятор автоматически будет предполагать, что объект где-то используется. То есть, следующий метод вполне сгодится на роль GC.KeepAlive:

using System.Runtime.CompilerServices;

// ...

[MethodImpl(MethodImplOptions.NoInlining)]
static void MyKeepAlive(object obj)
{
     // Преднамеренно оставлен пустым: метод не выполняет никаких операций
}

Статические корни

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

class Button
{
    public void OnClick(object sender, EventArgs e)
    {
        // Реализация отсутствует
    }
}

class Program
{
    static event EventHandler ButtonClick;

    static void Main(string[] args)
    {
        while (true)
        {
            Button button = new Button();
            ButtonClick += button.OnClick;
        }
    }
}

Эта программа страдает утечкой памяти, потому что статическое событие содержит список делегатов, которые в свою очередь ссылаются на создаваемые программой объекты. Фактически, одной из наиболее типичных для .NET причин утечек памяти является сохранение ссылок на объекты в статических переменных!

Другие корни

Две категории корней, описанные выше, являются наиболее распространенными, однако существуют и другие категории. Например, дескрипторы сборщика мусора (представленные типом GCHandle из пространства имен System.Runtime.InteropServices) также интерпретируются как корни. Очередь объектов, готовых к завершению (freachable queue), - еще один пример корня - объекты, ожидающие финализации, все еще считаются досягаемыми для сборщика мусора. Обе разновидности корней обсуждаются в следующих статьях; знание различных категорий корней может пригодиться при отладке утечек памяти в приложениях для .NET, потому что очень часто в отсутствие простейших (читайте: локальных и статических) корней, ссылающихся на ваши объекты, они продолжают сохраняться в памяти по какой-то другой причине.

Исследование корней с помощью SOS.DLL

Для исследования цепочек корней, удерживающих определенные объекты в памяти, можно использовать библиотеку SOS.DLL, расширение отладчика, с которой мы познакомились ранее. Команда !gcroot библиотеки позволяет получить исчерпывающую информацию о типах корней и цепочках ссылок. Ниже приводится пример вывода команды:

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

Вопросы производительности

Фаза маркировки в цикле сборки мусора является фазой «преимущественно для чтения», в процессе выполнения которой не производится перемещение объектов в памяти или их удаление. Тем не менее, эта фаза оказывает существенное влияние на производительность:

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

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

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

• Производительность фазы маркировки зависит также от количества объектов в графе, но не зависит от объема памяти, занимаемой этими объектами. Большие объекты, содержащие мало ссылок, влекут меньше накладных расходов. А это означает, что производительность фазы маркировки прямо пропорциональная количеству живых объектов в графе.

По завершении фазы маркировки сборщик мусора получает полный граф всех используемых объектов и ссылок на них (показано на рисунке ниже).

Теперь сборщик мусора может перейти к фазе чистки.

Фазы чистки и сжатия

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

В простейшей модели, исследованием которой мы сейчас занимаемся, выделение памяти выполняется простым наращиванием указателя, который всегда ссылается на следующий свободный блок памяти:

Этот указатель называется указателем на следующий объект (next object pointer), или указателем на новый объект (new object pointer) и инициализируется, когда на этапе запуска приложению передается блок динамической памяти.

Выделение памяти в этой модели выполняется чрезвычайно быстро: достаточно выполнить единственную атомарную операцию увеличения указателя. В многопроцессорных системах наверняка будут возникать конкуренция за право доступа к этому указателю.

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

В фазе сжатия сборщик мусора перемещает живые объекты в памяти, размещая их рядом друг с другом, как показано на следующем рисунке:

Заштрихованные объекты (слева) продолжат существование после сборки мусора и будут сдвинуты ближе к началу пула динамической памяти. Это означает, например, что ссылка на объект A (пунктирная линия) будет обновлена. Это способствует локальности ссылок, потому что объекты, создававшиеся одновременно, наверняка окажутся в памяти по соседству. С другой стороны, перемещение объектов влечет за собой две проблемы производительности:

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

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

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

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

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

Закрепление

Модель сборки мусора, представленная выше, не учитывает один из типичных случаев использования управляемых объектов. В данном случае речь идет о передаче управляемых объектов неуправляемому коду. Решить эту проблему можно двумя способами:

• все объекты можно передавать неуправляемому коду по значению (то есть, копировать) и возвращать так же по значению;

• чтобы избежать копирования, объекты можно передавать по ссылке.

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

Модель управления памятью в .NET поддерживает возможность получения адресов управляемых объектов в памяти. Однако передача этих адресов неуправляемому коду в присутствии сборщика мусора порождает серьезную проблему: представьте, что произойдет, если сборщик мусора переместит объект, пока неуправляемый код выполняет его обработку и продолжает использовать прежний адрес?

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

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

Сама операция закрепления стоит не очень дорого - существует несколько механизмов, выполняющих ее очень быстро. Наиболее явным способом закрепления объекта является создание дескриптора сборщика мусора с флагом GCHandleType.Pinned. В результате создается новый корень в таблице дескрипторов, сообщающий сборщику мусора, что объект должен оставаться прикрепленным к определенному адресу в памяти. В число альтернатив входят магическая приправа, добавляемая маршалером P/Invoke, и механизм закрепленных указателей, предоставляемый языком C# в виде ключевого слова fixed (или типа pin_ptr<T> в C++/CLI), который опирается на специальную маркировку локальных переменных.

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

Сильная фрагментация динамической памяти сводит на нет оптимизации, ускоряющие сборку: она препятствует последовательному размещению объектов в памяти (что отрицательно сказывается локальности ссылок), вносит дополнительные сложности в процедуру выделения памяти и вызывает непроизводительный расход памяти из-за невозможности заполнить «дыры» между объектами.

Побочные эффекты, вызываемые закреплением объектов в памяти ,можно наблюдать с помощью множества разных инструментов, включая профилировщик Microsoft CLR Profiler. Этот профилировщик может отображать графы объектов с адресам и, отмечая свободные (фрагментированные) области, как пустое пространство. Аналогично библиотека SOS.DLL (расширение управляемого отладчика) способна отображать «дыры», образовавшиеся в результате фрагментации, как объекты типа «Free». Наконец, определить количество закрепленных объектов в последней области, исследованной сборщиком мусора, можно с помощью счетчика «# of Pinned Objects» («Закрепленных объектов») из категории «.NET CLR Memory» («Память CLR .NET»).

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

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