Как реализовать сборку мусора в C ++

Question

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

Я хочу получить общее представление о том, как это сделать. Большое спасибо!

Это вопрос интервью Bloomberg, который мне сказал мой друг. Он сделал плохо в то время. Мы хотим знать ваши идеи по этому поводу.

Answer 1

Сборка мусора в C и C ++ является сложной темой по нескольким причинам:

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

2. Указатели не являются непрозрачными.Многие сборщики мусора, такие как сборщики стоп-копий, любят перемещать блоки памяти или сжимать их для экономии места.Поскольку вы можете явно просматривать значения указателей в C и C ++, это может быть трудно реализовать правильно.Вы должны быть уверены, что, если кто-то делает что-то хитрое с типизацией в целые числа, вы правильно обновите целое число, если вы переместили блок памяти.,Любой сборщик мусора должен учитывать, что пользователь может в любое время явно освобождать блоки памяти.

3. В C ++ существует разделение между распределением / освобождением и построением объекта/ уничтожение.Блок памяти может быть выделен с достаточным пространством для хранения объекта без какого-либо объекта, фактически построенного тамХороший сборщик мусора должен знать, когда он восстанавливает память, вызывать ли деструктор для каких-либо объектов, которые могут быть там размещены.Это особенно верно для контейнеров стандартной библиотеки, которые часто используют std::allocator, чтобы использовать этот прием из соображений эффективности.

4. Память может быть выделена из разных областей.C и C ++ могут получать память либо из встроенного freestore (malloc / free или new / delete), либо из ОС через mmap или другие системные вызовы, а в случае C ++ из get_temporary_buffer или return_temporary_buffer.Программы могут также получить память из какой-нибудь сторонней библиотеки.Хороший сборщик мусора должен иметь возможность отслеживать ссылки на память в этих других пулах и (возможно) должен отвечать за их очистку.

5. Указатели могут указывать на серединуобъекты или массивы.Во многих языках сборки мусора, таких как Java, ссылки на объекты всегда указывают на начало объекта.В C и C ++ указатели могут указывать на середину массивов, а в C ++ - на середину объектов (если используется множественное наследование).Это может значительно усложнить логику для определения того, что еще доступно.

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

Как указывали другие Boehm GC выполняет сборку мусора для C и C ++, но с учетом вышеупомянутых ограничений.

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

Answer 2

C не является C ++, но у обоих одинаковые проблемы со слабой типизацией.Тем не менее, причиной являются не неявные типы типов, но тенденция к «наказанию» (подрыву системы типов), особенно в библиотеках структур данных.

Там есть сборщики мусора.для C и / или C ++.Консервативный коллекционер Бема, наверное, самый известный.Он консервативен в том, что, если он видит битовую комбинацию, похожую на указатель на какой-либо объект, он не собирает этот объект.Это значение может быть полностью другим типом значения, поэтому объект можно собирать, но «консервативный» означает безопасную игру.

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

Конечно, это очень исключительный особый случай.

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

Поскольку шаблон RAII широко распространен в C ++, и в нем используются деструкторы, возникает конфликт IMO.Могут быть допустимые исключения, но я считаю, что если вы хотите сборку мусора, вы должны использовать язык, который был разработан с нуля для сборки мусора (Java, C #, ...).

Answer 3

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

Например:

char* pCharArray = new char[128];
// do some stuff with characters
delete [] pCharArray;

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

std::vector<char> charArray;
// do some stuff with characters

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

Answer 4

Загляните в сборщик мусора Boehm .

Answer 5

Вы можете прочитать о shared_ptr struct.

Он реализует простой подсчет ссылок сборщик мусора.

Если вы хотите настоящийсборщик мусора, вы можете перегрузить оператор new .

Создайте структуру, аналогичную shared_ptr, назовите ее Object.

Это обернет созданный новый объект.Теперь, перегружая его операторы, вы можете управлять GC.

Все, что вам нужно сделать сейчас, - это просто реализовать один из многих GC алгоритмов

Answer 6

Заявление, которое вы видели, является ложным; Boehm сборщик поддерживает C и C ++. Я предлагаю прочитать документацию сборщика Boehm (особенно эта страница ) для хорошего обзора того, как можно написать сборщик мусора на C или C ++.