Почему сборщик мусора только подметает кучу?

28

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

Почему он также не проверяет раздел данных (глобальные переменные, константы и т. Д.) Или стек? Что такого в куче, что это единственное, что мы хотим собирать мусором?

Темный тамплиер
источник
21
«подметать кучу» безопаснее, чем «стучать по стеку» ... :-)
Брайан Кноблаух

Ответы:

62

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

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

(Существуют системы, такие как smalltalk, где стековые фреймы являются первоклассными объектами, хранящимися в куче и мусоре, собираемом, как и все другие объекты. Но в наши дни это не популярный подход. JVM Java и CLR Microsoft используют аппаратный стек и непрерывную память .)

Джефф Григг
источник
7
+1 стек всегда полностью доступен, так что нет смысла его подметать
трещотка урод
2
+1 спасибо, занял 4 поста, чтобы правильно ответить. Я не знаю , почему вы должны были сказать , что все в стеке «считается» , чтобы быть в использовании, то есть при использовании его по крайней мере, сильного чувства , как куча объектов до сих пор используется в использовании - но это реальная придираться из очень хороший ответ.
PSR
@psr он имеет в виду, что все в стеке легко достижимо, и его не нужно собирать до тех пор, пока метод не вернется, но этим (RAII) уже явно управляют
ratchet freak
@ratchetfreak - я знаю. И я просто имел в виду, что слово «обдумано», вероятно, не нужно, но можно сделать более сильное заявление без него.
PSR
5
@psr: я не согласен. « считается используемым» более корректно как для стека, так и для кучи по очень важным причинам. Вы хотите отказаться от того, что больше не будет использоваться; то, что вы делаете, это то, что вы отбрасываете то, что недостижимо . У вас вполне могут быть доступные данные, которые вам никогда не понадобятся; когда эти данные растут, у вас возникает утечка памяти (да, они возможны даже на языках GC, в отличие от многих людей). И можно утверждать, что также происходят утечки стека, наиболее распространенный пример - ненужные кадры стека в хвостовых рекурсивных программах, выполняемых без устранения хвостовых вызовов (например, в JVM).
Blaisorblade
19

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

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

Как мы можем избежать этих затрат?

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

Но если мы решили проблему с дырами, мы решили и проблему сбора мусора . У вас есть что-то в этом хранилище, которое еще живо? Да. Было ли все выделено до того, как оно дольше будет жить? Да - это предположение, как мы устранили возможность дыр. Поэтому все, что вам нужно сделать, это сказать «живое ли последнее распределение?» и вы знаете, что в этом хранилище все живо.

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

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

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

(Конечно, стоимость сбора мусора в памяти, на которую ссылаются ссылки на фреймах активации, все еще остается.)

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

C # 2.0 имеет эту функцию в виде yield return. Метод, возвращающий доход, будет активирован позднее - в следующий раз, когда вызывается MoveNext - и когда это произойдет, это не предсказуемо. Поэтому информация, которая обычно находится в стеке для кадра активации блока итератора, вместо этого сохраняется в куче, где она собирается при сборке перечислителя.

Аналогично, функция «async / await», появившаяся в следующих версиях C # и VB, позволит вам создавать методы, чьи активации «приносят» и «возобновляют» в четко определенных точках во время действия метода. Поскольку кадры активации больше не создаются и не уничтожаются предсказуемым образом, вся информация, которая раньше хранилась в стеке, должна храниться в куче.

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

Эрик Липперт
источник
13

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

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

Чад
источник
5
Но куча - это не расположение «данных экземпляра». Они тоже могут быть в стеке.
svick
@svick Зависит от языка, конечно. Java поддерживает только объекты, выделенные в куче, и Vala довольно четко различает кучу (класс) и стек (структура).
пушистый
1
@fluffy: это очень ограниченные языки, вы не можете предполагать, что это в целом верно, поскольку ни один язык не был уточнен.
Матье М.
@MatthieuM. Это была моя точка зрения.
пушистый
@fluffy: так почему классы размещаются в куче, а структуры размещаются в стеке?
Темный тамплиер
10

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

Джейсон Бейкер
источник
1
Мало того, что это будет освобождено «в конечном счете», но это будет освобождено в нужное время.
Борис Янков
3
  1. Их размер является предсказуемым (постоянным, за исключением стека, а размер стека обычно ограничен несколькими МБ) и обычно очень мал (по крайней мере по сравнению с сотнями МБ, которые могут выделять большие приложения).

  2. Динамически размещенные объекты обычно имеют небольшой интервал времени, в течение которого они достижимы. После этого на них нельзя будет ссылаться снова. Сравните это с записями в разделе данных, глобальными переменными и т. Д. Часто есть фрагмент кода, который ссылается на них напрямую (подумайте const char *foo() { return "foo"; }). Как правило, код не изменяется, поэтому ссылка остается, и каждый раз при вызове функции создается другая ссылка (которая может быть в любое время, насколько известно компьютеру - если вы не решите проблему остановки, то есть ). Таким образом, вы все равно не сможете освободить большую часть этой памяти, так как она всегда будет доступна.

  3. Во многих языках, предназначенных для сбора мусора, все, что принадлежит выполняемой программе, выделяется кучей. В Python просто нет никакого раздела данных и нет значений, выделенных стеком (есть ссылки на локальные переменные, и есть стек вызовов, но ни одно из них не является значением в том же смысле, что и intв C). Каждый объект находится в куче.


источник
«В Python просто нет раздела данных». Строго говоря, это не так. None, True и False выделяются в разделе данных, как я понимаю: stackoverflow.com/questions/7681786/how-is-hashnone-calculated
Джейсон Бейкер,
@JasonBaker: Интересная находка! Это не имеет никакого эффекта, хотя. Это деталь реализации и ограничена встроенными объектами. Не говоря уже о том, что эти объекты не должны быть освобождены когда-либо в течение жизни программы в любом случае, нет, и они также имеют крошечный размер (менее 32 байт каждый, я думаю).
@delnan Как любил отмечать Эрик Липперт, для большинства языков существование отдельных областей памяти для стека и кучи является деталью реализации. Вы можете реализовать большинство языков без использования стека вообще (хотя производительность может снизиться, если вы это сделаете) и при этом соответствовать их спецификациям
Jules
2

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

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

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

Райан Калпеппер
источник
Было бы интересно узнать. Первая мысль, что обнуление пробелов является наиболее реалистичным. Обход дерева исключенных областей может занять больше времени, чем простое сканирование через нули. Очевидно, что любая попытка сжать стек чревата опасностью! Создание такой работы звучит как сгибающий ум / подверженный ошибкам процесс.
Брайан Кноблаух
@Brian, на самом деле, подумав еще немного, для типизированной виртуальной машины вам все равно нужно что-то подобное, так что вы можете определить, какие слоты являются ссылками, а не целыми числами, числами с плавающей точкой и т. Д. Кроме того, что касается сжатия стека, см. «CONS Не жалеет своих аргументов »Генри Бейкер.
Райан Калпеппер
Определение типов слотов и проверка их правильного использования могут и обычно выполняются статически, либо во время компиляции (для виртуальных машин, использующих доверенный байт-код), либо во время загрузки (когда байт-код поступает из ненадежного источника, например, Java).
Жюль
1

Позвольте мне указать на несколько фундаментальных заблуждений, которые вы и многие другие ошиблись:

"Почему сборщик мусора только подметает кучу?" Это наоборот. Только самые простые, самые консервативные и самые медленные сборщики мусора охватывают кучу. Вот почему они такие медленные.

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

Поскольку куча примерно в 1000 раз больше стека (ов), такой GC для сканирования стека обычно намного быстрее. ~ 15 мс против 250 мс на кучах нормального размера. Так как он копирует (перемещает) объекты из одного пространства в другое, его обычно называют копирующим сборщиком полупространства, ему требуется 2-кратная память, и, следовательно, он в основном не используется на очень маленьких устройствах, таких как телефоны с небольшим объемом памяти. Он компактен, поэтому в дальнейшем он очень удобен для кэширования, в отличие от простых сканеров меток и развертки.

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

Использование Mark & ​​Sweep тривиально, но его не следует использовать в реальных программах, и особенно его нельзя преподавать как стандартный сборщик. Самым известным из таких копирующих коллекторов с быстрым сканированием стека называется чейни для двух пальцев .

rurban
источник
Похоже, вопрос скорее в том, какие части памяти собирают мусор, а не в конкретные алгоритмы сборки мусора. Последнее предложение особенно подразумевает, что OP использует «sweep» в качестве общего синонима для «сборки мусора», а не в качестве специального механизма для реализации сборки мусора. Учитывая это, ваш ответ звучит так, как будто вы говорите, что кучу собирают только самые простые сборщики мусора, а быстрые сборщики мусора вместо мусора собирают стек и статическую память, оставляя кучу расти и расти до тех пор, пока не закончится память.
8bittree
Нет, вопрос был очень конкретным и умным. Ответы не так. ГХ медленной метки и развертки имеют две фазы: шаг метки, сканирующий корни в стопке, и фазу развертки, сканирующую кучу. Быстрое копирование GC имеет только одну фазу, сканирование стека. Легко как то. Поскольку, очевидно, никто не знает здесь о правильных сборщиках мусора, вопрос нужно ответить. Ваша интерпретация дико отклоняется.
Рурбан
0

Что выделяется в стеке? Локальные переменные и обратные адреса (в C). Когда функция возвращается, ее локальные переменные отбрасываются. Это не обязательно, даже вредно, чтобы подмести стек.

Многие динамические языки, а также Java или C # реализованы на языке системного программирования, часто на C. Можно сказать, что Java реализован с функциями C и использует локальные переменные C, и, следовательно, сборщик мусора Java не нуждается в очистке стека.

Есть интересное исключение: сборщик мусора в Chicken Scheme очищает стек (в некотором роде), потому что его реализация использует этот стек в качестве пространства для сборки мусора первого поколения: см. Википедию Chicken Scheme Design .

nalply
источник