Статья:
Реализация сборки мусора на С++

Автор(ы): Михаил Чащин
Дата: 18.11.2002

Авторы:
Михаил Чащин

Аннотация:
В данной статье мы рассмотрим обобщённую реализацию сборки мусора на С++. Будут обсуждены два конкретных алгоритма сборки мусора – “Mark-Sweep” и “Mark-Compact”, и их реализация. Мы также рассмотрим ограничения, которые накладываются на приложения при использовании сборки мусора, и изменения в компиляторе C++, которые могли бы помочь избежать этих ограничений.

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

На мой взгляд, сборка мусора на C++ — задача утопическая, особенно для случая уплотняющих алгоритмов. И эта утопичность исходит из сущности указателей, которые растут из C, которые в свою очередь растут из простой косвенной адресации. То есть, сборка мусора должна быть встроена в язык (а в идеале — в процессор!), со всеми вытекающими последствиями, в том числе и с неизбежными потерями производительности, ну типа, как это реализовано в MC++ и вообще в MSIL. При создании C и C++ не было такой задачи — и это правильно, поскольку C++ призван быть максимально эффективным языком. А раз так, то только ручками — new/delete. Я и сам использую "хитрые указатели", но крайне ограниченно. А вот автоматическая сборка мусора ничего кроме дополнительных проблем не создает. Причем, на первый вгляд кажется, что все хорошо, но в сложных проектах, особенно в многопоточных, это "все хорошо" зачастую становится источником трудноуловимых ошибок.

Ребята, а вы вообще, пытались собрать код, который здесь приведён?
template <class class T,... Это что значит?
Зачем вообще тогда его публиковать?

Честно говоря вообще не понимаю зачем нужен GC?
Без сарказма. Действительно не понимаю.

Первыми ввели его в Java. Когда читаешь книжки по Java понимаешь что GC — это
штука, без которой программирование вообще невозможно. А особенно GC полезен для
эффективного использования памяти. ИМХО язык, в котором нет явных указателей на физическую память,
может распоряжаться памятью как ему угодно и когда угодно. ИМХО гораздо полезнее было бы синхронное
удаление объекта при обнулении счётчика ссылок, с синхронным вызовом деструктора.
А уж что происходит с памятью при этом, дело языка: хочет освобождает, хочет нет, хочет перемещает живые объекты в памяти.

Вторыми эту великую идею подхватили в .NET. И настолько ей увлеклись что даже забыли сделать синхронные деструкторы в C++/CLI.
Потом права опомнились и добавили через ж"№;м синтасисом синхронный деструктор.

Ну да фиг с ними. Вот чего я действительно не понимаю так это зачем GC в С++?
Ещё многие кричат что нефиго его в компилятор зафигачить

Насколько я понимаю GC решает 3 задачи:
1. Эффективное управление памятью.
2. Удаление объектов, на которые уже не существует ни одной ссылки.
3. Разруливание циклических ссылок.


1. В С++ с успехом решают свои распределители памяти и аллокаторы. ИМХО как раз самое быстрое\оптимальное распределение памяти
должно предоставляться компилятором. Но пока это не так (если верить многим ) можно пользоваться своими распределителями памяти.

2. Эффективно решается boost::shared_ptr Несколько лет пользуюсь не могу нарадоваться.

3. Самая существенная проблема, но тоже не смертельная. Легко разруливается парами boost::shared_ptr, boost::weak_ptr.
Довольно большой проект собрался с их использованием — проблем никаких. Даже наоборот когда видишь weak_ptr понимаешь что объекта
может уже не быть.


Может я чего-то ещё не вижу?

Тут простой реализацией не ограничиться. Получится монстр, потяжелее STL.
А зачем ? Для использования в нескольких вырожденных случаях ?
Лучше пересесть на .Net или Java. Это будет получше.
Я видел даже ООП на языках Ассемблер и Cи.
GC+C++ — такой же геморрой.
Имеет право жить только в качестве академической задачи.

у Джефа Элджера посимпатичнее расписано , имхо.. Хотя в последней части статьи посерьезнее терминология :)

Еще сборка мусора (технология) нужна в больших проектах. например при написании языка со сборкой мусора (и в шутку и всерьез).
А на счет умных указателей — использую и очень часто. Да тот же СОМ без нее не существовал бы.

ИМХО, слишком много надо телодвижений чтобы избежать планирования времени жизни обьекта.

К тому же, как и все другие, данная реализация деликатно умалчивает о том что есть и другие, non-freestore ресурсы (файлы, хендлы и теде и тепе) которые надо менеджить ручками.
Посему вопрос: нужно ли городить столь большой огород только для того чтобы решить ЧАСТНЫЙ вопрос управления ресурсами? Причем, решить не полностью — т.к. сущности, которые не знают о данном Garbage Collector'е выпадают из его поля зрения...

Так ты не путай CComPtr, в который глядишь, как в зеркало и этот конгломерато-винигрет.

Сразу скажу, статью толком не читал — лень было (не бейте). Но вот как реализована ф-ция-член compact глянул и увидел все тот же memcpy. Вроде как неоднократно писали, что так можно только POD объекты копировать. Может я что-то не понял — извините тогда. И вообще сильно на Элджера все это смахивает.

http://www.hpl.hp.com/personal/Hans_Boehm/gc/

Пример великолепного GC для C/C++. Работает с большим количеством компиляторов и платформ, легок в использовании (унаследуй свой класс от класса gc — и все!).

Я как-то написал тестовую программку для рвзных методов выделения/освобождения памяти под VC7. Первым вышел этот GC, вторым "Small Object Allocator" (из Loki), ну а третьим VC7 аллокатор.

Да, кстати, эта-же программа, переписанная на C#, чтобы использовать .NET GC, была на 4-м месте. На Java не пробовал, но думаю, что получится примерно так-же как и на C#.

Если интересно (source code, etc) пишите сюда:
res0m4rf@verizon.net

Это точно! Мои указатели конечно похитрее CComPtr, но до этой э... не дотягивают

ШЕ>Ну да фиг с ними. Вот чего я действительно не понимаю так это зачем GC в С++?
...
ШЕ>Может я чего-то ещё не вижу?

Глянь здесь (+здесь) и сравни реализацию с GC и без.

S>Глянь здесь (+здесь) и сравни реализацию с GC и без.

Наконец дошло время почитать и осознать.
Согласитесь lock-free очереди — это весьма сомнительный повод прикручивать GC к C++
Во-вторых в статье такая фраза, что вот, мол, мы не можем отследить когда объект перестаёт использоваться,
поэтому нефигово было бы иметь GC который бы знал, когда это можно сделать и сам бы за этим следил.
При этом пан Александреску "забывает" что реализация GC тоже не даётся на шару и тоже сопряжена с проблемой синхронизации.
При этом всё равно как она реализована сбоку от С++ или внутри С++.

Потом, в данном контексте прикручивание GC означает потерю детерминированного деструктора, что тоже черевато.

Шебеко Евгений пишет:
> Честно говоря вообще не понимаю зачем нужен GC?
> Без сарказма. Действительно не понимаю.

Не ты один.


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

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

> Ну да фиг с ними. Вот чего я действительно не понимаю так это зачем GC в
> С++?

> 1. Эффективное управление памятью.

Забыл добавить НЕ вначале.

Еще такой эффект есть — дешёвые исключения. Нет деструкторов,
память удалять не надо, стек раскручивается мгновенно.

Здравствуйте, Шебеко Евгений, Вы писали:

ШЕ>Первыми ввели его в Java.

Вообще-то первый раз он был ряализован и придуман в/для lisp,
около 1960, не думаю тогда Sun еще не было, не то джавы.

Здравствуйте, MasterZiv, Вы писали:

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

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

VoidEx пишет:
> MZ>Не всегда счетчики ссылок работают. Могут быть кольцевые структуры

> Всегда хотел увидеть тривиальный пример, если можно, конечно.

Тоже хотел. Поискал. Нашел вот это

www.memorymanagement.org
и в частности это
reference <br />
counting

VoidEx пишет:
> Всегда хотел увидеть тривиальный пример, если можно, конечно.

здесь <br />
еще

Здравствуйте, MasterZiv, Вы писали:

MZ>Тоже хотел. Поискал. Нашел вот это

Но есть одно но. Там абстрактно, про reference counting и (в последней ссылке) про язык явно со сборкой мусора.
В сборке мусора это актуально, так как любая ссылка может ознакать как владение, так и просто ссылку, в Си++ это можно указать явно, и тогда проблем не будет.
T — содержание объекта, т.е. владение с постоянным временем жизни (относительно владельца)
auto_ptr<T> — владение объектом с контролем времени жизни
shared_ptr<T> — разделяемое владение объектом (несколько хозяев)
T * — ссылка (указатель, если угодно) на объект, т.е. использование его, но не владение
weak_ptr<T> — аналогично, но с возможностью проверить, жив ли объект

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

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

Собственно, поэтому считаю, что ГЦ решает 2 задачи, третью он сам себе вводит и сам ее решает
Хотя нет, вру, в Дельфи именно 3, да

Здравствуйте, VoidEx, Вы писали:

VE>Вот меня и интересует, есть ли пример, где циклические ссылки будут обязательно.
VE>Т.е. я не могу придумать примера, где два объекта владели бы друг другом.

Типичная ситуация при Callback, например connection points в COM.