Как сборщики мусора избегают переполнения стека?

23

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

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

Итак, как сборщики мусора пересекают произвольные структуры? Как эта техника обхода позволяет избежать переполнения?

Джейк
источник
1
GC пересекает все структуры более или менее одинаково, но только в очень абстрактном смысле (см. Ответ). То, как они конкретно отслеживают вещи, намного сложнее, чем указано в элементарных презентациях, которые можно найти в учебниках. И они не используют рекурсию. Кроме того, с виртуальной памятью плохие реализации показывают замедление GC, редко как переполнение памяти.
Бабу
Вы беспокоитесь о месте, необходимом для отслеживания. Но как насчет пространства или структур, необходимых для различения памяти, которая была прослежена и, как известно, используется, от памяти, которая потенциально может быть исправлена. Это может иметь значительную стоимость памяти, возможно, пропорциональную размеру кучи.
Бабу
Я подумал, что это будет сделано с битовым вектором для объекта размером более 16 или около того байтов, так что накладные расходы будут как минимум в 1000 раз меньше.
Джейк
Есть много способов сделать это (см. Ответ), и они также могут быть использованы для трассировки, которая затем ответит на ваш вопрос (битовые векторы или битовые карты могут использоваться для трассировки, а не стека или очереди, которые вы предлагаете). Вы не можете предполагать, что все объекты большие, если только вы не намереваетесь тратить пространство на маленькие объекты, которых может быть много, и тогда вам не стоит беспокоиться о пространстве. Если вы находитесь в виртуальной памяти, пространство часто является гораздо меньшей проблемой, и проблемы очень разные.
Бабу

Ответы:

13

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

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

Как только все дочерние узлы узла, кроме одного, будут отсканированы, узел можно удалить из неотсканированной очереди. Это в основном оптимизация хвостового вызова. Сборщики мусора могут включать эвристику, чтобы попытаться отсканировать самого глубокого потомка узла последним; например, GC для Lisp должен сканировать cara consперед cdr.

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

Жиль "ТАК - перестань быть злым"
источник
2
Техника, описанная в последнем абзаце, часто называется « инверсией указателя ».
Блуждающая логика
@WanderingLogic Да, обращение указателя - это то, как я назвал его в своем собственном ответе. Это связано с Дойчем, Шорром и Уэйтом (1967). Однако, это неверно утверждать , что он работает в постоянной памяти: она требует дополнительных бит для каждой ячейки с р указателями, хотя это может быть уменьшено с помощью битовой стеки. Принятый ответ, на который вы ссылаетесь, является не совсем правильным или полным по той же причине. журнал2пп
Бабу
Я уже использовал разворот указателя в пользовательском GC без необходимости этих дополнительных бит; хитрость заключалась в том, чтобы использовать специальное представление в памяти объектов в памяти. А именно, объект «заголовок» был посередине, с полями указателя перед заголовком и полями без указателя после; более того, все указатели были выровнены, а заголовок содержал поле с всегда установленным младшим значащим битом. Таким образом, во время обратного возврата указателя, достигнув следующего указателя и заметив, что мы закончили с объектом, можно сделать однозначно без лишних битов. Этот макет также поддерживает наследование ООП.
Томас Порнин
@ThomasPornin Я думаю, что информация о битах должна быть где-то. Вопрос в том, где? Можем ли мы обсудить это в чате? Я должен уйти сейчас, но я хотел бы докопаться до сути. Или в сети есть описание?
Бабу
1
@babou и Томас, пожалуйста
Жиль "ТАК - перестань быть злым"
11

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

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

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

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

  • набор (посещенных) ячеек, которые уже были найдены мутатором , то есть программа или алгоритм, для которого выполняется GC. Множество V разбивается на два непересекающихся подмножества: V = U T ;ВВВзнак равноUT

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

  • набор (отслеженный) посещенных ячеек, в которых отслежены все их указатели.T

  • мы также отмечаем ЧАС

ВUUT

UВ

UсВUсUT

UUВзнак равноTВЧАС-ВВ

ВUUT

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

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

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

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

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

  • журнал2пп

  • Вы можете проверить предикат на содержание ячейки и ее указатели.

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

  • ВTTU .

  • Вы можете комбинировать эти приемы даже для одного набора.

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

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

Очевидно, что нет рекурсии, и стек алгоритма мутатора не должен использоваться.

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

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

Babou
источник
4

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

DW
источник
Когда вызывается GC, куча обычно заполнена. Другое дело, что случается так, что стек и куча растут с обоих концов одного и того же пространства памяти ..
Бабу
4

В «классических» описаниях сборки мусора (например, Марк Уилсон, « Методы сбора мусора в Uniprocessor », « Международный семинар по управлению памятью» , 1992 г., ( альтернативная ссылка )) или в описании « Реализация современного компилятора» Эндрю Аппеля (издательство Кембриджского университета, 1998)), коллекционеры классифицируются как «Mark and Sweep» или «Copying».

Коллекторы Mark и Sweep избегают необходимости в дополнительном пространстве с помощью обращения указателя, как описано в ответе @ Gilles. Аппель говорит, что Кнут приписывает алгоритм обращения указателя к Петеру Дойчу, Герберту Шорру и WM Waite.

Копирующие сборщики мусора используют так называемый алгоритм Чейни для выполнения обхода очереди без необходимости в дополнительном пространстве. Этот алгоритм был введен в CJ Cheyney, "Алгоритм сжатия нерекурсивных списков", Comm. ACM , 13 (11): 677-678, 1970.

В копирующем сборщике мусора у вас есть кусок памяти, который вы пытаетесь собрать, который называется « из космоса» , и кусок памяти, который вы используете для копий, называемый « пространство» . To-space организован как очередь с scanуказателем, указывающим на самую старую скопированную, но не отсканированную запись, и freeуказателем, указывающим на следующую свободную позицию в to-space. Изображение этого из статьи Уилсона:

Пример алгоритма Чейни

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

Блуждающая логика
источник
На самом деле, как объяснено в моем ответе, Mark + Sweep и Copy collection - это один и тот же алгоритм абстрактного графа. Коллекция MS и Copy отличаются только тем, как реализованы наборы, используемые абстрактным алгоритмом, и оба семейства, со многими вариантами, включены в некоторую комбинацию методов реализации наборов, которые я опишу в своем ответе. Некоторые варианты GC фактически смешивают MS и Copy в одном GC. Разделение MS и Copy рассматривается некоторыми как удобный способ структурирования книг, но это произвольное, и я считаю, устаревшее видение.
Бабу
@babou: Если кто-то использует алгоритм копирования, в котором копируется все посещаемое (медленно, но может быть полезно на небольших платформах, где рабочий набор никогда не бывает настолько большим), некоторые алгоритмы могут быть несколько упрощены, поскольку можно использовать память, ранее занятая перемещенным объектом в качестве блокнота. Можно также получить ограниченную возможность, чтобы другие потоки выполняли доступ только для чтения к объектам во время сбора при условии, что каждый проверяет достоверность объекта до и после каждого чтения и следует за указателем пересылки, если объект был перемещен.
суперкат
@supercat Я не уверен, что вы пытаетесь сказать, каковы ваши намерения. Некоторые из ваших утверждений кажутся правильными. Но я не понимаю, как вы можете использовать из космоса до окончания цикла GC (он содержит указатели пересылки). И это будет блокнот для чего? Упростить алгоритм как? Что касается нескольких потоков-мутаторов, выполняемых во время GC, это в значительной степени ортогональная проблема, хотя она может серьезно повлиять на реализацию. Я не буду пытаться обратиться к этому в комментариях. Это должно вызвать меньше проблем в доступе только для чтения, но дьявол кроется в деталях.
Бабу