Отслеживание сбора мусора

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

Достижимость объекта

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

1. Выделенный набор корней: объекты, которые считаются достижимыми. Обычно к ним относятся все объекты, на которые имеются ссылки из любого места стека вызовов (то есть все локальные переменные и параметры вызываемых в данный момент функций), а также любые глобальные переменные .
2. Все, на что ссылается доступный объект, само по себе достижимо; более формально, достижимость — это транзитивное замыкание .

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

Object x = new Foo();
Object y = new Bar();
x = new Quux();
/* At this point, we know that the Foo object 
 * originally assigned to x will never be
 * accessed: it is syntactic garbage.
 */

/* In the following block, y *could* be semantic garbage;
 * but we won't know until x.check_something() returns
 * some value -- if it returns at all.
 */
if (x.check_something()) {
    x.do_something(y);
}
System.exit(0);

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

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

Сильные и слабые ссылки

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

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

В некоторых реализациях слабые ссылки делятся на подкатегории. Например, виртуальная машина Java предоставляет три формы слабых ссылок, а именно мягкие ссылки , фантомные ссылки , и регулярные слабые ссылки. Объект с мягкой ссылкой подлежит восстановлению только в том случае, если сборщик мусора решит, что программе не хватает памяти. В отличие от мягкой ссылки или обычной слабой ссылки, фантомная ссылка не обеспечивает доступ к объекту, на который она ссылается. Вместо этого фантомная ссылка — это механизм, который позволяет сборщику мусора уведомлять программу, когда объект, на который ссылается, становится фантомно доступным . Объект является фантомно доступным, если он все еще находится в памяти и на него ссылается фантомная ссылка, но его финализатор уже выполнен. Аналогично, Microsoft.NET предоставляет две подкатегории слабых ссылок: а именно длинные слабые ссылки (воскрешение треков) и короткие слабые ссылки.

Слабые коллекции

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

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

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

Основной алгоритм

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

Наивная маркировка и очистка

Наивное действие пометки и очистки на куче, содержащей восемь объектов . Стрелки представляют ссылки на объекты . Круги представляют собой сами объекты. Объекты №1, №2, №3, №4 и №6 имеют строгие ссылки из корневого набора. С другой стороны, на объекты №5, №7 и №8 нет прямых или косвенных ссылок из корневого набора; следовательно, они мусор.

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

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

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

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

Трехцветная маркировка

Пример трехцветной маркировки на куче из 8 предметов. Белые, серые и черные объекты представлены светло-серым, желтым и синим соответственно.

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

Создано три комплекта — белый , черный и серый :

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

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

1. Выберите объект o из серого набора.
2. Переместите каждый белый объект или ссылку на серый набор. Это гарантирует, что ни этот объект, ни любой объект, на который он ссылается, не может быть подвергнут сборке мусора.
3. Перейдите к черному набору
4. Повторяйте последние три шага, пока серый набор не станет пустым.

Когда серый набор пуст, сканирование завершено; черные объекты доступны из корней, а белые объекты — нет, и их можно собирать мусором.

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

Трехцветный метод имеет важное преимущество – его можно выполнять «на лету», не останавливая систему на значительные периоды времени. Это достигается путем маркировки объектов по мере их выделения и во время мутации, сохраняя различные наборы. Отслеживая размер наборов, система может выполнять сбор мусора периодически, а не по мере необходимости. Кроме того, отпадает необходимость трогать весь рабочий комплект в каждом цикле.

Стратегии реализации

Движущиеся и неподвижные

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

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

• Никаких дополнительных работ по освобождению места, освобожденного мертвыми объектами, не требуется; всю область памяти, из которой были перемещены доступные объекты, можно считать свободным пространством. Напротив, неподвижный сборщик мусора должен посетить каждый недоступный объект и зафиксировать, что занимаемая им память доступна.
• Аналогично, новые объекты могут быть выделены очень быстро. Поскольку большие смежные области памяти обычно становятся доступными благодаря движущемуся сборщику мусора, новые объекты могут быть выделены путем простого увеличения указателя «свободной памяти». Стратегия неперемещения может через некоторое время привести к сильно фрагментированной куче, требующей дорогостоящего просмотра «свободных списков» небольших доступных блоков памяти для выделения новых объектов.
• Если используется соответствующий порядок обхода (например, cdr-first для списка conses ), объекты можно перемещать очень близко к объектам, на которые они ссылаются в памяти, увеличивая вероятность того, что они будут расположены в одной и той же строке кэша или виртуальной памяти странице . . Это может значительно ускорить доступ к этим объектам через эти ссылки.

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

Копирование, пометка и очистка и пометка и не очистка

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

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

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

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

Сборщик мусора « Отметить и не очищать» , как и сборщик мусора «Отметить и очистить», сохраняет бит для каждого объекта, чтобы записать, белый он или черный; серый набор сохраняется в виде отдельного списка или с использованием другого бита. Здесь есть два ключевых различия. Во-первых, черное и белое означают разные вещи, чем в сборщике меток и подметании. В коллекторе «отметить и не удалять» все доступные объекты всегда черные. Объект помечен черным в момент его выделения и останется черным, даже если станет недостижимым. Белый объект — это неиспользуемая память, которую можно выделить. Во-вторых, интерпретация бита «черное/белое» может измениться. Первоначально бит черный/белый может иметь значение (0=белый, 1=черный). Если операция выделения когда-либо не может найти доступную (белую) память, это означает, что все объекты помечаются как использованные (черные). Затем смысл бита черный/белый инвертируется (например, 0 = черный, 1 = белый). Все становится белым. Это на мгновение нарушает инвариант, согласно которому доступные объекты являются черными, но немедленно следует фаза полной маркировки, чтобы снова пометить их черными. Как только это будет сделано, вся недоступная память станет белой. Фаза «развертки» не требуется.

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

Таким образом, стратегию «отметить и не удалять» можно рассматривать как компромисс между плюсами и минусами стратегии «отметить и исключить» и стратегии «остановить и скопировать».

Поколенческий GC (эфемерный GC)

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

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

Классический мусорщик Унгара имеет два поколения. Он делит самое молодое поколение, называемое «новым пространством», на большой «рай», в котором создаются новые объекты, и два меньших «пространства выживания»: пространство выживших в прошлом и пространство выживших в будущем. Объекты старшего поколения, которые могут ссылаться на объекты в новом пространстве, сохраняются в «запоминаемом наборе». При каждой очистке объекты в новом пространстве отслеживаются от корней в запомненном наборе и копируются в будущее пространство выживания. Если пространство будущего выжившего заполняется, неподходящие объекты перемещаются в старое пространство - процесс, называемый «владением». В конце сбора некоторые объекты остаются в пространстве будущего выжившего, а пространство Эдема и прошлого выжившего пустует. Затем пространство будущего выжившего и пространство прошлого выжившего меняются местами, и программа продолжается, распределяя объекты в Эдеме. В исходной системе Унгара Эдем в 5 раз больше, чем каждое пространство выживших.

Сборка мусора по поколениям — это эвристический подход, и некоторые недоступные объекты не могут быть удалены в каждом цикле. Поэтому иногда может возникнуть необходимость выполнить полную пометку и очистку или копирование мусора, чтобы освободить все доступное пространство. Фактически, системы времени выполнения для современных языков программирования (таких как Java и .NET Framework ) обычно используют некий гибрид различных стратегий, которые были описаны до сих пор; например, в большинстве циклов сбора могут рассматриваться только несколько поколений, хотя иногда выполняется маркировка и очистка, а еще реже выполняется полное копирование для борьбы с фрагментацией. Термины «малый цикл» и «большой цикл» иногда используются для описания этих разных уровней агрессии коллектора.

Остановить мир, инкрементный и параллельный

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

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

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

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

Точные против консервативных и внутренних указателей

Некоторые сборщики могут правильно идентифицировать все указатели (ссылки) в объекте; их называют точными (также точными или точными ) коллекторами, противоположностью которых является консервативный или частично консервативный коллектор. Консервативные сборщики предполагают, что любой битовый шаблон в памяти может быть указателем, если, интерпретируемый как указатель, он будет указывать на выделенный объект. Консервативные сборщики могут давать ложные срабатывания, когда неиспользуемая память не освобождается из-за неправильной идентификации указателя. На практике это не всегда проблема, если только программа не обрабатывает много данных, которые легко можно ошибочно принять за указатель. Ложные срабатывания обычно менее проблематичны в 64-битных системах, чем в 32-битных системах, поскольку диапазон действительных адресов памяти обычно составляет лишь небольшую часть диапазона 64-битных значений. Таким образом, произвольный 64-битный шаблон вряд ли будет имитировать действительный указатель. Ложноотрицательный результат может также произойти, если указатели «скрыты», например, с помощью связанного списка XOR . Практичность конкретного сборщика обычно зависит от свойств безопасности типов рассматриваемого языка программирования. Примером, для которого потребуется консервативный сборщик мусора, является Язык C , который позволяет приводить типизированные (непустые) указатели к нетипизированным (пустым) указателям и наоборот.

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

Производительность

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

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

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

Выделение кучи вручную

• поиск лучшего/первого подходящего блока достаточного размера
• бесплатное ведение списка

Сбор мусора

• находить доступные объекты
• копировать доступные объекты для перемещения коллекторов
• барьеры чтения/записи для инкрементальных сборщиков
• поиск лучшего/первоподходящего блока и бесплатное ведение списка для неподвижных коллекторов

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

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

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

Детерминизм

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

Сбор мусора в реальном времени

Хотя сбор мусора, как правило, недетерминирован, его можно использовать в системах жесткого реального времени . Сборщик мусора в реальном времени должен гарантировать, что даже в худшем случае он выделит определенное количество вычислительных ресурсов потокам-мутаторам. Ограничения, налагаемые на сборщик мусора в реальном времени, обычно основаны либо на работе, либо на времени. Ограничение, основанное на времени, будет выглядеть так: в каждом временном окне продолжительностью T потокам-мутаторам должно быть разрешено выполнение по крайней мере в течение времени Tm . Для анализа на основе работы MMU (минимальное использование мутатора) обычно используется в качестве ограничения в реальном времени для алгоритма сборки мусора.

Одна из первых реализаций жесткой сборки мусора в реальном времени для JVM была основана на алгоритме Metronome , коммерческая реализация которого доступна как часть IBM WebSphere Real Time . Еще один алгоритм жесткой сборки мусора в реальном времени — Staccato, доступный в IBM от J9 JVM , который также обеспечивает масштабируемость для больших многопроцессорных архитектур, одновременно обеспечивая различные преимущества перед Metronome и другими алгоритмами, которые, напротив, требуют специализированного оборудования.

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

См. также

• Устранение мертвого кода
• Марк – компактный алгоритм