LINUX.ORG.RU

сборка мусора - зацените идейку


1

0

Доброго!

Как я понял, поколенческая сборка мусора требует некоторых дополнительных действий при каждом создании или изменении ссылки, чтобы отследить ссылки старого объекта на молодой. Почему бы тогда не обобщить понятие «поколения» на понятие «область хранения» и не позволить пользователю явно управлять областями? Например, ввести глобальную (поточную) переменную «текущая область хранения» и всё выделение по умолчанию вести в этой области. Или добавить параметр в конструктор (хотя это требует переделки языка). Области могут быть упорядочены в иерархию и тогда нужно будет отслеживать только ссылки «старших» на «младших» по иерархии. Или они могут составлять произвольный граф и тогда нужно отслеживать все ссылки. Причём, можно отслеживать ссылки как тонко (на уровне объектов), так и грубо (на уровне областей). Например, мы знаем, что область A ссылается на область B. Тогда, чтобы собрать мусор в области B, нам нужно искать корни также в области А. Самое главное, если на область B вообще никто не ссылается, то мы можем одним махом убить все объекты в области B.

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

★★★★★

Ответ на: комментарий от Booster

> Для чего отслеживать ссылки старого объекта на молодой?
Смысл поколенческой сборки мусора (хотя это и википедии можно прочитать): все объекты делятся на поколения.
Допустим, на 4 (так во многих лиспах). 1-е поколение - самое молодое, 2-е - постарше и т.п. Есть несколько разновидностей сборок мусора.
Чаще всего делается сборка только в 1-м поколении.
Чуть реже - в 1-м и втором
Ещё реже - в 1-м, 2-м и третьем
Совсем редко - во всей куче.

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

Смысл тут в том, что если объектов много, но меняются они редко, то эти объекты попадают в 4-е поколение и сборка мусора по ним проходит редко. Значит, в целом, время на сборку мусора сокращается.

Если объекты не меняются, то объекты i-го поколения ссылаются только на объекты из поколений [i..4] Но. Если объект из 3-его поколения поменялся, он теперь может ссылаться на объект из 1-го. И может так оказаться, что больше на этот объект никто не ссылается. Если эту ссылку не учесть, то сборка мусора 1-го поколения может уничтожить живой объект 1-го поколения. Значит, нужно отследить конкретно эту ссылку в какой-то таблице. Это усложняет логику создания ссылок и увеличивает требования к памяти.
И, при неблагоприятном раскладе (например, большая хеш-таблица с данными, которая живёт всю жизнь и регулярно меняется), смысл поколенческой сборки начинает размываться.

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

den73 ★★★★★
() автор топика
Ответ на: комментарий от Love5an

> Сборщик это отдельная подсистема рантайма. Подсчет ссылок - нет.

Ы-ы-ы-ы-ы-ы-ы-ы!!! Счётчик ссылок это отдельная подсистема рантайма, сборка мусора — нет. Ну логично, что подсистема и процесс — это немного разные вещи, не находишь?

Границы деления на подсистемы в семействе продуктов весьма условны. Я уже спрашивал — лексический, синтаксический анализатор и компилятор в байт-код — это сколько подсистем, одна, две или три?

Если в тупой подсчёт ссылок добавить отслеживание кольцевых зависимостей, которое будет выполняться периодически, а не на каждое уменьшение счётчика — это резко станет сборщиком мусора?

kemm
()
Ответ на: комментарий от Waterlaz

Ладно, с терминологической (если смотреть на англоязычную терминологию) я не прав. kemm, мои извинения :) Тем не менее, reference counting слабее, чем tracing garbage collection, вряд ли кто-то будет с этим спорить. Потому что не убирает циклические ссылки, и для их удаления нужны либо усилия на уровне кода, либо, опять же, приделать tracing garbage collection (случай Питона). Значит, tracing garbage collection и reference-counting - это принципиально разные вещи. У кого какие квалифицированные предложения по терминологии? Как называть эти вещи по Русски, чтобы можно было понять, что мы говорим о разном. Я всегда считал, что сборка мусора - это tracing garbage collection, а подсчёт ссылок - это reference counting.

Ну а если вернуться к существу вопроса и посмотреть на шутаут, можно заметить, что языки с tracing garbage collection - быстрые (лисп, ява, окамль), а языки с reference-counting - примерно в 30 раз медленнее (Perl,Python,PHP). Отсюда напрашиваются выводы...

den73 ★★★★★
() автор топика
Ответ на: комментарий от Waterlaz

Вот же вы любители переливать из пустого в порожнее.

«управляемый» подсчет ссылок - не ГК. «Неуправляемый» - кривой и не полноценный ГК.

LamerOk ★★★★★
()
Ответ на: комментарий от den73

>Ну а если вернуться к существу вопроса и посмотреть на шутаут, можно заметить, что языки с tracing garbage collection - быстрые (лисп, ява, окамль), а языки с reference-counting - примерно в 30 раз медленнее (Perl,Python,PHP). Отсюда напрашиваются выводы...

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

Waterlaz ★★★★★
()
Ответ на: комментарий от den73

> kemm, мои извинения :)

Принято. 8))

Тем не менее, reference counting слабее, чем tracing garbage collection, вряд ли кто-то будет с этим спорить.

Тяжело спорить с очевидным, да. 8))

У кого какие квалифицированные предложения по терминологии?

Если принципиально — один раз обозвать полным названием, потом употреблять «сборка мусора». Кому надо — поймут гарантированно правильно (ну, либо будет достаточно одного указания на начало текста).

Отсюда напрашиваются выводы...

Эмн... Думаешь, связано именно со способом сборки мусора? Не уверен я что-то...

kemm
()
Ответ на: комментарий от den73

> неясно, что хуже - отсутствие собеседников вообще, или такие, непонимающие собеседники

Так ты пиши по-русски, а не выливай поток сознания. Как можно понять вот это:

типичный компилятор выделяет не слишком много памяти на каждый файл.


На какой еще файл? Что ты хотел сказать? Один телепат недавно был в /д/, но я думаю, опять ушел в отпуск.

с заранее готовым негативным мнением.


Это какбе _норма_. Если хочешь, чтобы твою идею одобрили - докажи/покажи её состоятельность. Или ты сюда не критику пришел послушать, а липовые восторги на тему «гениальности идеи»?

рассмотрим процесс обработки запросов к вебу в языках типа PHP ... при этом, возвращаемое значение - это код ошибки ОС


Щито?

Берём PHP. Переводим на лисп


......

LamerOk ★★★★★
()
Ответ на: комментарий от kemm

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

Тут даже такой терпеливый читатель, как я, не выдержал. Ты хочешь сказать, что если в C++ полностью полагаться на некий фреймворк, все объекты которого инкапсулируют подсчет ссылок, основанный на смартпоинтерах, таким образом, что никогда не приходится удалять объекты самостоятельно, то можно будет считать, что в программе используется «механизм сборки мусора»?

mannaz
()
Ответ на: комментарий от mannaz

> в программе используется «механизм сборки мусора»?

Да, в программе используется один из механизмов сборки мусора. Что тебя смущает?

kemm
()
Ответ на: комментарий от den73

>То, что в Perl называется «механизмом сборки мусора», в Python называется гораздо скромнее — «механизм подсчёта ссылок»

Вот объясни мне, каким образом «правильный GC» позволяет избегать ошибок, если на перле написано астрономическое число программ и при этом в нём убогий протекающий счётчик ссылок вместо православного GC и об этом ещё и не все перлеры знают, а глючат, тормозят и жрут память программы на питоне (все три с половиной)? Как так получается?

legolegs ★★★★★
()
Ответ на: комментарий от LamerOk

>> рассмотрим процесс обработки запросов к вебу в языках типа PHP ... при этом, возвращаемое значение - это код ошибки ОС

Щито?

А то. Что ещё может вернуть процесс? То, что он пишет в поток - это не объекты на куче.

На какой еще файл? Что ты хотел сказать?

Ессно, на каждый компилируемый файл. Их же может быть много за один запуск компилятора :)

den73 ★★★★★
() автор топика
Ответ на: комментарий от mannaz

> GC?

Шо «GC?»?

Что сказать-то хотел? Что подсчёт ссылок не является одним из возможных механизмов сборки мусора (уже разжевали вроде) или что ещё? Не понимаю.

kemm
()
Ответ на: комментарий от legolegs

>Вот объясни мне, каким образом «правильный GC» позволяет избегать ошибок, если на перле написано астрономическое число программ и при этом в нём убогий протекающий счётчик ссылок

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

Absurd ★★★
()
Ответ на: комментарий от kemm

> Что сказать-то хотел?

Является ли подобная реализация «одного из механизмов сборки мусора» GC? С твоей точки зрения.

mannaz
()
Ответ на: комментарий от Absurd

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

По твоей логике в жабовских сервлетах GC тоже может спать спокойно, что покрывает 64% оправданных применений жабы. Т.е. GC скорее не нужен, чем нужен?

mannaz
()
Ответ на: комментарий от mannaz

> Является ли подобная реализация «одного из механизмов сборки мусора» GC? С твоей точки зрения.

С моей точки зрения: если гарантируется соблюдение этих условий (никакой явной игры с памятью в обход фреймворка) — то является, пожалуй. Но единственной гарантией будет использование либо своего компилятора, либо специфического препроцессора, из чего следует, что язык уже не совсем «C++», а какой-то «C++++» в лучшем случае, а то и Ocaml ненароком получиться может. 8))

Без гарантий — ХЗ, но я бы не называл. Да, я не могу дать строгого и однозначного определения GC, если ты об этом.

kemm
()
Ответ на: комментарий от mannaz

>Является ли подобная реализация «одного из механизмов сборки мусора» GC?

Ну там сам активный тред при выходе из скопа ходит по графу объектов и расставляет чанкам бит «unused». С GC блуждание по деревьям объектов и расставление бита «unused» происходило бы асинхронно. Об этом речь?

Absurd ★★★
()
Ответ на: комментарий от mannaz

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

По твоей логике в жабовских сервлетах GC тоже может спать спокойно, что покрывает 64% оправданных применений жабы.

Весь жабовский сервер вместе с сервлетами всегда живет в рамках одного процесса.

Absurd ★★★
()
Ответ на: комментарий от Absurd

> С GC блуждание по деревьям объектов и расставление бита «unused» происходило бы асинхронно.

Требований к асинхронности GC нигде не предъявляется, вроде. В lua, емнип, GC синхронный. В перле не уверен.

kemm
()

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

Booster ★★
()
Ответ на: комментарий от Absurd

> Весь жабовский сервер вместе с сервлетами всегда живет в рамках одного процесса.

Да, не подумал. Хотя есть еще вариант с выполнением JSP на лету.

mannaz
()
Ответ на: комментарий от Booster

>Значит по-мнению kemm-а в Си тоже есть сборщик мусора - автоматическое выравнивание стека при возврате из функции.

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

Absurd ★★★
()
Ответ на: комментарий от mannaz

>> Весь жабовский сервер вместе с сервлетами всегда живет в рамках одного процесса.

Да, не подумал. Хотя есть еще вариант с выполнением JSP на лету.

Насколько я понимаю он их компилирует в .class и грузит класслодером в активную (свою собственную) JVM.

Absurd ★★★
()

>Если объекты не меняются, то объекты i-го поколения ссылаются только на объекты из поколений [i..4] Но. Если объект из 3-его поколения поменялся, он теперь может ссылаться на объект из 1-го.
Пока понятно.

И может так оказаться, что больше на этот объект никто не ссылается. Если эту ссылку не учесть, то сборка мусора 1-го поколения может уничтожить живой объект 1-го поколения. Значит, нужно отследить конкретно эту ссылку в какой-то таблице. Это усложняет логику создания ссылок и увеличивает требования к памяти.

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

Что-то я не понял, если на объект никто не ссылается, зачем тогда он нужен?

Booster ★★
()
Ответ на: комментарий от Booster

> Что-то я не понял, если на объект никто не ссылается, зачем тогда он нужен?

В третьем поколении живёт объект H, в первом - объект E. Единственная ссылка на E - из H. Соответственно, наивная сборка мусора в первом поколении уничтожит E.

den73 ★★★★★
() автор топика
Ответ на: комментарий от Booster

>Что-то я не понял, если на объект никто не ссылается, зачем тогда он нужен?

А как ты планируешь от него избавиться? free() просто ставит на блок бит «unused» ну и все. Чтобы использовать его повторно нужно его найти для начала, при условии что он подходящего размера.

Absurd ★★★
()
Ответ на: комментарий от den73

>В третьем поколении живёт объект H, в первом - объект E. Единственная ссылка на E - из H. Соответственно, наивная сборка мусора в первом поколении уничтожит E.

Это как? Ведь ссылка есть, значит удалять нельзя.

Booster ★★
()
Ответ на: комментарий от den73

>>> рассмотрим процесс обработки запросов к вебу в языках типа PHP ... при этом, возвращаемое значение - это код ошибки ОС

Щито?

А то. Что ещё может вернуть процесс? То, что он пишет в поток - это не объекты на куче.


Пилять, как тебе удается путать возвращаемое глибцы errno («код ошибки ОС») с возвращаемым значением процесса ?!? Или ты почётно именуешь возвращаемое значение процесса «кодом ошибки»? Тогда почему «кодом ОС» и как быть, если был возвращен код успеха? ;)))

типичный компилятор выделяет не слишком много памяти на каждый файл.

На какой еще файл? Что ты хотел сказать?

Ессно, на каждый компилируемый файл.


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

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

LamerOk ★★★★★
()
Ответ на: комментарий от den73

> Это принятая терминология
Сам ты сексуальное меньшинство! В лучшем случае, ты можешь утверждать, что терминология неоднозначна. А может быть, что и автор статьи в Википедии был недостаточно грамотен. Как минимум, если уж у нас есть общепризнанная терминология, то каково общепризнанное название tracing garbage collection на Русском языке?

den73 ★★★★★
() автор топика
Ответ на: комментарий от den73

>Сам ты сексуальное меньшинство!
Тоже считаешь, что в Си есть сборщик мусора?

Booster ★★
()
Ответ на: комментарий от legolegs

>Никогда не известно, сколько именно памяти потребуется для конкретного вычисления

$^&$улся?


Ну зачем так резко. В общем случае неизвесно. Вычисление может иметь древовидную структуру (которая выясняется лишь в процессе вычисления, не как FFT) и пока вычисление не дойдёт до терминальных вершин, оно само не знает, сколько же ему надо было памяти и времени на всё на это. Заранее определить не может, ибо это есть часть самого вычисления: последующие ходы вычисления зависят от результатов, полученных на предыдущих.

BOEHKOM
()
Ответ на: комментарий от den73

Я спросил, как сборка мусора в первом поколении может уничтожить объект, если в другом поколении кто-то на него ссылается? Можно мне на это ответить?

Booster ★★
()
Ответ на: комментарий от den73

Ну нахамить тебе пока не особо хотят (вроде), ибо ты источник ценных лулзов. %))

Но мысли надо учиться выражать. Хотя бы письменно, если не устно.

LamerOk ★★★★★
()
Ответ на: комментарий от LamerOk

Да и вообще хорошие треды создаешь. Нынче этого не хватает.

LamerOk ★★★★★
()
Ответ на: комментарий от den73

>Так, ладно, никто не хрена не понимает, и все норовят обхамить

Добро пожаловать в интернет :D

legolegs ★★★★★
()
Ответ на: комментарий от BOEHKOM

>Ну зачем так резко.

Потому-что из-за идиотов, которые пишут «Никогда не известно» вместо «изредка не известно» мы и наблюдаем повсюду тормозной быдлокод. Наболело.

Вычисление может иметь древовидную структуру

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

legolegs ★★★★★
()
Ответ на: комментарий от Booster

И снова здравствуйте.

Я спросил, как сборка мусора в первом поколении может уничтожить объект, если в другом поколении кто-то на него ссылается? Можно мне на это ответить?

Сборка мусора в первом поколении и корни ищет только в первом поколении. Только поэтому она и может быть быстрой. Во всяком случае, мне это казалось настолько очевидным, что я всегда так думал. Может быть, я не прав, но вряд ли я сейчас полезу в исходники SBCL, чтобы это проверить. Хотя... Ладно, 5 минут можно уделить.

den73 ★★★★★
() автор топика
Ответ на: комментарий от LamerOk

>> На практике в таком случае часто есть

У тебя очень маленькая практика. :3

Ну конечно, Вашество (:

А если серьёзно, по какой причине тебе в твоей практике (она ведь есть, да?) не удавалось определить максимальное время выполнение функции, либо, на худой конец, её O(f(n))? Ведь этой причиной не могла быть лень, верно? :D

legolegs ★★★★★
()
Ответ на: комментарий от den73

>Сборка мусора в первом поколении и корни ищет только в первом поколении. Только поэтому она и может быть быстрой. Во всяком случае, мне это казалось настолько очевидным, что я всегда так думал.
Да, но я не понял что конкретно предлагается. Как понимаю предлагается некая область, которая эквивалентна поколению. Но что это даёт?

Booster ★★
()
Ответ на: комментарий от legolegs

> не удавалось определить максимальное время выполнение функции, либо, на худой конец, её O(f(n))?

При чём тут время? Мы об объёме памяти говорим. )))

Объём потребляемой программой памяти в общем случае зависит от объема входных данных, в частном - еще и от значений входных данных.

Заведомо известный объем входных данных может быть почти исключительно на лабах в школе/вузе. ;)

LamerOk ★★★★★
()
Ответ на: комментарий от legolegs

Пример, когда невозможно определить максимальное время. Это когда выполняется функция «сидеть в интернете». Может продлиться 5 минут, а может выполняться 48 часов для особо запущенных случаев.

BOEHKOM
()
Ответ на: комментарий от den73

Короче, в сорсах не смог разобраться, но они там дают ссылку на статью
uniprocessor garbage collection techniques, где всё так и написано. В общем, вроде я правильно написал.

den73 ★★★★★
() автор топика
Ответ на: комментарий от kemm

> Без гарантий — ХЗ, но я бы не называл. Да, я не могу дать строгого и однозначного определения GC, если ты об этом.

Просто стало интересно, начиная с какого «момента», на твой взгляд, некоторая схема управления памятью становится Garbage Collector'ом. Вопрос снят.

mannaz
()
Ответ на: комментарий от Booster

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

den73 ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.