вторник, 16 октября 2012 г.

Немного о сборке мусора и поколениях

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

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

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

Давайте рассмотрим такой пример. Предположим, у нас есть некоторый объект “A”, который инициализирует свое свойство отложенным образом:

public class B

{ }

 

public class A

{

    private Lazy<B> _lazyB = new Lazy<B>(

            () => new B());

 

    public B B

    {

        get { return _lazyB.Value; }

    }

}

И доступ к свойству B, а значит и создание этого объекта, происходит уже тогда, когда объект “A” находится во втором поколении:

var a = new A();

GC.Collect();

GC.Collect();

 

// output: A resides in Gen 2, A.B resides in Gen 0

Console.WriteLine("A resides in Gen {0}, A.B resides in Gen {1}",

GC.GetGeneration(a), GC.GetGeneration(a.B));

 

GC.Collect();

Итак, сборка мусора нулевого поколения заключается в анализе только лишь объектов этого поколения. Это означает, что при запуске сборке мусора в строке (3) все объекты нулевого поколения помечаются как недостижимые, включая вновь созданный объект “B”. Затем анализируются все корневые ссылки для определения достижимости объектов этого поколения; если объект достижим, то он считается живым, а все остальные объекты, к которым нет доступа из корневых ссылок, считаются мусором и удаляются.

image

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

Для решения этой проблемы, нам нужно как-то добавить объект “A” в список объектов, которые нужно проанализировать для определения достижимости объекта “B”. Однако вместо того, чтобы сохранять список всех «грязных» объектов, большинство реализаций сборщиков мусора с поддержкой поколений используют специальную структуру данных под названием card table, в которой хранится адрес объекта, создавшего «молодого» потомка.

Card table представляет собой простую структуру данных, которая представляет собой битовую маску, каждый бит которой говорит о том, что объект, расположенным по адресу с определенным диапазоном, является «грязным» и содержит ссылку на «молодой» объект. На данный момент один бит битовой маски представляет собой диапазон в 128 байт, а значит, каждый байт битовой маски содержит информацию о диапазоне в 1К. Данный подход является компромиссом между эффективностью и объемом дополнительной памяти, требуемой сборщику мусора для поддержания этой таблицы в актуальном состоянии. Таким образом, для 32 битовой системы, в которой пользовательскому режиму доступно 2 ГБ адресного пространства, размер card table составит 2 Мб. Однако поскольку один бит в card table помечает диапазон в 128 байт адресного пространства, каждый раз при сборке мусора придется проанализировать десятки других объектов, которые могут и не содержать ссылки на молодые поколения.

image

Для поддержки данной структуры данных в актуальном состоянии, каждый раз при записи поля объекта, JIT компилятор генерирует так называемый «барьер записи» (write barrier), который сводится к обновлению card table, если адрес записываемого объекта находится в эфемерном сегменте (ephemeral segment), т.е. является молодым объектом 0-го или 1-го поколений.

Теперь, если вернуться к нашему случаю, то объект “B” не будет собран сборщиком мусора, поскольку для анализа достижимости будут анализироваться не только корневые ссылки (которые на него не ссылаются), но и все объекты, расположенные по младшим 128 байтам второго поколения, куда попадает наш объект “A”.

Для чего мне все это?

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

Кстати, у данной реализации есть и небольшое практическое следствие: несмотря на то, что объекты старшего поколения создают новые объекты и сохраняют их в полях не так и часто (британские ученые установили, что не более 1% объектов второго поколения поступают таким образом), любая запись в поле объекта требует некоторых дополнительных затрат на тот самый хак, требуемый для обновления card table. Это, например, делает запись поля в управляемом мире немного более дорогостоящей операцией, по сравнению с неуправляемым миром (например, с языком С++).

12 комментариев:

  1. Извини, читал немного вскользь из-за недостатка времени.
    Я не заметил, ты, кажется, не упомянул про эвристическое же правило, которого гласит, что первыми лучше всего создавать "долгожителей", тогда они быстрее попадут в старшие поколения и не будут путаться под ногами у сборщика мусора.
    Это правило еще актуально? :-)

    ОтветитьУдалить
  2. Основная цель заметки - это рассказать о card table, поэтому многие детали были опущены осознано.

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

    Так что шансов, что будет какая-то хоть минимально видимая разница после такой "оптимизации", мне сомнительно.

    ОтветитьУдалить
  3. Вот хотел добавить очень старую (2009), но обширную статью об Generational Garbage Collection

    http://blogs.msdn.com/b/abhinaba/archive/2009/03/02/back-to-basics-generational-garbage-collection.aspx

    ОтветитьУдалить
  4. Этот комментарий был удален автором.

    ОтветитьУдалить
  5. Во! Часто упоминается, что сборщик мусора для иммутабельных объектов гораздо эффективнее, чем для изменяемых. теперь становится понятно почему. Иммутабельные объекты не могут содержать ссылки на объекты младших поколений, а значит для них ненужно поддерживать этот самый card table.

    ОтветитьУдалить
  6. @Antya: спасибо, серия статей и правда хорошая.

    @jack128: ну да, получается что в этом есть смысл. Правда я далеко не уверен, что если на каждый чих вместо модификации свойства изменяемого объекта будет создаваться новый экземпляр неизменяемого, что это будет более эффективно;)

    ОтветитьУдалить
  7. Создается ли card table для объектов первой генерации, содержащих ссылки на объекты нулевой генерации, т.е. обе из эфемерного сегмента?

    ОтветитьУдалить
  8. Позанудствую :). Сереж, я правда считаю, что полезнее было бы написать о разнице в работе сборщика мусора для 4.0 и выше и предыдущими версиями(GC collect gen2). Описать, в чем разница между WorkstationMode and ServerMode. И самое важное (на мой взгляд) рассказать о LowLatency(сейчас уже и не только). Ведь это дает реальный выхлоп. Особенно кому надо высокоэффективные вычисления...

    ОтветитьУдалить
  9. @Aleksey: да, поидее такая запись должна создаваться и на первое поколение тоже.

    @eugene: занудствовать, это хорошо (правда), от этого мы лучше становимся.

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

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

    ОтветитьУдалить
  10. @Sergey Teplyakov
    Ну никто ж геворит о запрете мутабельных объектов. Путь и те и другие сосуществуют. Но в разных блоках памяти, чтоб при сборке мусора объекты с неизменяемыми ссылками не сканировались.

    ОтветитьУдалить
  11. Ок. Твоя мысль мне понятна и близка(писать о том, что пощупал).

    ОтветитьУдалить