Почему сборщики мусора ждут до освобождения?

Ответ 1

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

С помощью refcounts существует целое число, отслеживающее количество ссылок, и вы можете сразу вызвать освобождение, когда refcount достигнет нуля. Это нам, как работает CPython, и как работают большинство разновидностей интеллектуальных указателей С++. Реализация CPython добавляет GC для GC/GC в качестве резервной копии, поэтому она очень похожа на гибридный дизайн, который вы описываете.

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

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

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

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

Итак, коллекционер с двумя колесами был намного быстрее, чем malloc(), что было здорово, потому что программы Lisp могли бы делать намного больше распределений, чем программы C. Или, говоря иначе, программы Lisp нуждались в том, чтобы выделить память, такую ​​как стек, но со временем жизни, не ограниченным стеком выполнения, другими словами, стек, который мог бы расти бесконечно без завершения программы памяти. И, по сути, Раймонд Чен утверждает, что именно так люди должны думать о GC. Я очень рекомендую его серию сообщений в блогах, начиная с Все думают о сборке мусора неправильным образом.

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

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

Вы правильно заметили, что истинный GC должен работать "ниже" уровня malloc() и free(). (Как примечание, стоит узнать, как реализованы malloc() и free() - они тоже не волшебны!) Кроме того, для эффективного GC вам нужно либо быть консервативным (например, GC Boehm), никогда не перемещайте объекты и не проверяйте вещи, которые могут быть указателями, или вам нужен какой-то тип "непрозрачного указателя", который вызывает ссылки на Java и С#. Непрозрачные указатели на самом деле отлично подходят для системы распределения, поскольку это означает, что вы всегда можете перемещать объекты, обновляя указатели на них. На языке C, где вы напрямую взаимодействуете с необработанными адресами памяти, никогда не безопасно перемещать объекты.

И есть несколько вариантов алгоритмов GC. Стандартная среда исполнения Java содержит не менее пяти коллекционеров (Young, Serial, old CMS, новый CMS и G1, хотя я думаю, что забыл их), и у каждого есть набор параметров, которые все настраиваются.

Однако GC не волшебны. Большинство GCs просто используют коммюнемент времени в пространстве для пакетной работы, а это означает, что выигрыш в скорости обычно оплачивается при увеличении использования памяти (по сравнению с ручным управлением памятью или refcounting). Но сочетание повышения производительности программы и повышения производительности программиста в сравнении с низкой стоимостью оперативной памяти в эти дни делает компромисс, как правило, заслуживающим внимания.

Надеюсь, это поможет сделать вещи более ясными!

Ответ 2

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

Добавление

Сборщик мусора, который всегда должен воздействовать на каждый живой предмет, чтобы обеспечить его сохранение, может быть медленным, когда есть много живых предметов; вот почему сборщики мусора исторически получили плохой рэп. Интерпретатор BASIC на Commodore 64 (который, кстати, был написан Microsoft за несколько дней до MS-DOS), занимал много секунд, чтобы выполнить сборку мусора в программе с массивом из нескольких сотен строк. Производительность может быть значительно улучшена, если предметы, которые переживают первую сборку мусора, могут быть проигнорированы до тех пор, пока многие предметы не переживут свою первую сборку мусора, и те, кто участвовал в двух мусорных сборах и выжил в них (обратите внимание, что им не придется участвовать в их втором до тех пор, пока многие другие объекты не выживут в первую очередь) могут быть проигнорированы, пока многие другие объекты не участвовали и не выжили во втором. Эта концепция может быть частично реализована легко (даже на Commodore 64, можно заставить все строки, которые существуют в данный момент, быть освобожденными от будущей сборки мусора, что может быть полезно, если при запуске программа создала большие массивы строк, которые никогда не будут изменение), но становится более мощным с небольшой дополнительной поддержкой аппаратного обеспечения.

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

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

Ответ 3

Ваши мысли, как правило, очень проницательны и хорошо продуманны. Вам просто не хватает основной информации.

Сборщики мусора освобождают объект, когда он больше не находится в какой-либо области

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

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

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

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

Я предполагаю, что структура сохраняет целое число для каждого объекта

Не обязательно. Например, OCaml использует один бит.

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

С точки зрения программирования было бы неплохо, если бы код работал быстрее 10 раз.

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

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

Рассмотрим программу, которая решает проблему n-queens, манипулируя списками координат шахматной доски. Ввод представляет собой одно целое число. Вывод представляет собой список, содержащий несколько координат платы. Промежуточные данные представляют собой огромный пакет спагетти связанных узлов списка. Если вы закодировали это, предварительно выделив достаточно большой стек узлов связанного списка, обработав их, чтобы получить ответ, скопируйте (маленький) ответ и затем вызовите free один раз во весь стек, тогда вы будете делать почти точно так же, что делает сборщик мусора поколения. В частности, вы копируете только ~ 6% ваших данных, и вы освободите другой ~ 94% одним вызовом free.

Это был прекрасный сценарий счастливого дня для коллекционера сборщиков мусора, который придерживается гипотезы о том, что "большинство объектов умирают от молодых и старых объектов, редко ссылающихся на новый объект". Пример патологического счетчика, в котором собираются сборщики мусора мусора, заполняет хеш-таблицу со свеже выделенными объектами. Хребет хэш-таблицы - это большой массив, который выживает, поэтому он будет в старом поколении. Каждый новый объект, вставленный в него, является обратным указателем от старого поколения к новому поколению. Каждый новый объект выживает. Таким образом, коллекторы коллекций мусора выделяют быстро, но затем отмечают все, копируют все и обновляют указатели ко всему и, следовательно, запускают ~ 3 раза медленнее, чем простое решение на C или С++.

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

Обратите внимание, что деструкторы и сбор мусора являются ортогональными понятиями. Например,.NET предоставляет деструкторы в виде IDisposable.

FWIW, через ~ 15 лет использования собранных мусором языков я использовал профилирование памяти, возможно, 3 раза.

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

CPython делает это, я считаю. Mathematica и Erlang ограничивают кучу как DAG по дизайну, поэтому они могут использовать только подсчет ссылок. Исследователи GC предложили связанные методы, такие как пробное удаление, в качестве вспомогательного алгоритма для обнаружения циклов.

Отметим также, что подсчет ссылок теоретически асимптотически быстрее, чем трассировка сбора мусора, поскольку его производительность не зависит от размера (живой) кучи. На практике трассировка сборки мусора все еще намного быстрее даже с 100-килограммовыми кучами.

Ответ 4

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

Ответ 5

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

Рассмотрим ряд объектов, последовательно размещенных в памяти:

Object 1
Object 2
Object 3
Object 4
Object 5

Если объект 2 может быть освобожден, и GC немедленно начнет работать, объекты 3, 4 и 5 будут перемещены.

Теперь рассмотрим, что объект 4 может быть освобожден, GC теперь переместит объект 5 рядом с Object 3. Объект 5 был перемещен дважды

Однако, если GC ждет короткое время, оба объекта2 и 4 могут быть удалены одновременно, что означает, что объект 5 перемещается один раз и перемещается дальше.

Умножьте количество объектов, скажем, на 100, и вы сможете увидеть значительную экономию времени от этого подхода.

Ответ 6

@Jim ответил на некоторые из них, я добавлю еще больше.

Во-первых, что заставляет вас думать, что освобождение [A1], как только число 0 является хорошей альтернативой?

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

Кроме того, оказывается, что очистка нескольких объектов происходит быстрее, чем в A[1]. (Подумайте об этом, для комнаты с разбросом песка - быстрее очистить все вместе, а не выбирать каждый из них отдельно)

Во-вторых, для обеспечения безопасности потоков в многопоточных системах для каждого объекта необходимо удерживать блокировку для увеличения/уменьшения количества, которое является плохим показателем производительности и дополнительной памятью. Современные коллекторы имеют возможность делать это параллельно и не останавливай мир (например: Java ParallelGC), мне интересно, как это может произойти с A[1].

Ответ 7

Сбор мусора с использованием подсчета ссылок очень медленный, особенно в поточной среде.

Я действительно рекомендую этот пост Брайана Гарри.

Здесь содержится образец кода, который более чем достаточно, чтобы убедить меня (С#):

public interface IRefCounted : IDisposable
{
        void AddRef();
}

// ref counted base class.
class RefCountable : IRefCountable
{
        private m_ref;
        public RefCountable()
        {
                m_ref = 1;
        }
        public void AddRef()
        {
                Interlocked.Increment(ref m_ref);
        }
        public void Dispose()
        {
                if (Interlocked.Decrement(ref m_ref) == 0)
                        OnFinalDispose();
        }
        protected virtual void OnFinalDispose()
        {
        }
}

Interlocked.Increment(ref m_ref) - атомная операция, которая занимает сотни циклов памяти.