Я видел сообщение о реализации GC на C, и некоторые люди говорили, что это невозможно сделать, потому что C слабо типизирован. Я хочу знать, как реализовать GC в С++.
Мне нужно общее представление о том, как это сделать. Большое вам спасибо!
Это вопрос интервью Bloomberg, который мой друг сказал мне. В то время он делал плохо. Мы хотим знать ваши идеи об этом.
Сбор мусора на C и С++ - это сложные темы по нескольким причинам:
Указатели могут быть typecast для целых чисел и наоборот. Это означает, что у меня может быть блок памяти, доступный только путем принятия целого числа, приведения его в соответствие с указателем, а затем разыменование его. Сборщик мусора должен быть осторожным, чтобы не думать, что блок недоступен, когда он действительно может быть достигнут.
Указатели не являются непрозрачными. Многие сборщики мусора, такие как сборщики стоп-копий, любят перемещать блоки памяти или сжимать их, чтобы сэкономить место. Поскольку вы можете явно посмотреть на значения указателя в C и С++, это может быть сложно реализовать правильно. Вы должны быть уверены, что если кто-то делает что-то сложное с приведением типов к целым, что вы правильно обновили целое число, если вы переместили блок памяти.
Управление памятью может выполняться явно. Любой сборщик мусора должен принимать во внимание, что пользователь может в явном виде освобождать блоки памяти в любое время.
В С++ существует разделение между распределением/освобождением и построением/разрушением объекта. Блок памяти может быть выделен с достаточным пространством для хранения объекта без какого-либо объекта, который там строится. Хороший сборщик мусора должен знать, когда он восстанавливает память, следует ли вызывать деструктор для любых объектов, которые могут быть выделены там. Это особенно справедливо для стандартных контейнеров библиотек, которые часто используют std::allocator для использования этого трюка по соображениям эффективности.
Память может быть выделена из разных областей. C и С++ могут получать память либо из встроенного freestore (malloc/free, либо new/delete), либо из ОС через mmap или других системных вызовов, а в случае С++ - от get_temporary_buffer или return_temporary_buffer. Программы могут также получать память из сторонней библиотеки. Хороший сборщик мусора должен иметь возможность отслеживать ссылки на память в этих других пулах и (возможно) должен будет нести ответственность за их очистку.
Указатели могут указывать на середину объектов или массивов. Во многих сборниках, связанных с мусором, таких как Java, ссылки на объекты всегда указывают на начало объекта. В C и С++ указатели могут указывать на середину массивов, а в С++ - на середину объектов (если используется множественное наследование). Это может значительно усложнить логику обнаружения того, что еще доступно.
Итак, короче говоря, очень сложно построить сборщик мусора для C или С++. Большинство библиотек, которые делают сборку мусора на C и С++, чрезвычайно консервативны в своем подходе и технически необоснованны - они предполагают, что вы не будете, например, брать указатель, отливать его до целого числа, записывать его на диск и затем загружать он вернулся в какое-то позднее время. Они также предполагают, что любое значение в памяти, что размер указателя может быть указателем, и поэтому иногда отказывается освобождать недостижимую память, потому что существует ненулевой шанс, что есть указатель на него.
Как отмечали другие, Boehm GC делает сборку мусора для C и С++, но с учетом вышеупомянутых ограничений.
Интересно, что С++ 11 включает некоторые новые функции библиотеки, которые позволяют программисту отмечать области памяти как достижимые и недоступные в ожидании будущих усилий по сбору мусора. В будущем возможно создать действительно хороший сборщик мусора С++ 11 с подобной информацией. Тем временем вы должны быть предельно осторожны, чтобы не нарушить ни одно из вышеуказанных правил.
Посмотрите Сборщик мусора Boehm.
C не является С++, но оба имеют те же "слабо типизированные" проблемы. Это не неявные приведения типов, которые вызывают проблему, но и склонность к "карать" (подрыв системы типов), особенно в библиотеках структуры данных.
Там есть сборщики мусора для C и/или С++. Лучше всего известно, что консервативный коллекционер Бёма. Он консервативен тем, что если он видит бит-шаблон, который выглядит как указатель на какой-либо объект, он не собирает этот объект. Это значение может быть каким-то другим типом значения полностью, поэтому объект может быть собран, но "консервативный" означает безопасное воспроизведение.
Даже консервативный коллекционер может быть обманут, хотя, если вы используете рассчитанные указатели. Там есть структура данных, например, где каждый список node имеет поле, указывающее разницу между следующими адресами node и previous-node. Идея состоит в том, чтобы дать поведение с двойным связыванием с одной ссылкой на node за счет более сложных итераторов. Поскольку в большинстве узлов нет явного указателя, они могут быть ошибочно собраны.
Конечно, это очень необычный частный случай.
Более важно - вы можете иметь надежные деструкторы или сбор мусора, а не оба. Когда собран мусорный цикл, сборщик не может решить, какой деструктор должен вызвать первым.
Так как шаблон RAII широко распространен в С++, и он полагается на деструкторы, возникает конфликт IMO. Могут быть допустимые исключения, но я считаю, что если вы хотите сборку мусора, вы должны использовать язык, созданный с нуля для сбора мусора (Java, С#,...).
Вы можете использовать интеллектуальные указатели или создать свой собственный объект-контейнер, который будет отслеживать ссылки и обрабатывать выделение памяти и т.д. Умные указатели, вероятно, будут предпочтительнее. Часто вы можете избежать динамического распределения кучи в целом.
Например:
char* pCharArray = new char[128];
// do some stuff with characters
delete [] pCharArray;
Опасность, связанная с тем, что произошло, если что-то между новым и удалить ваше удаление, не будет выполнена. Что-то вроде выше может быть легко заменено более безопасным кодом "сборщик мусора":
std::vector<char> charArray;
// do some stuff with characters
Bloomberg имеет, как правило, нерелевантные вопросы интервью с точки зрения практического кодирования. Как и большинство интервьюеров, они в первую очередь озабочены тем, как вы думаете, и ваши навыки общения, чем реальное решение.
Заявка, которую вы видели, неверна; Boehm collector поддерживает C и С++. Я предлагаю прочитать документацию сборщика Boehm (особенно на этой странице), чтобы получить хороший обзор того, как можно написать сборщик мусора на C или С++.
Вы можете прочитать о shared_ptr структуре.
Он реализует простой reference-counting сборщик мусора.
Если вы хотите создать сборщик мусора, вы можете перегрузить оператора new.
Создайте структуру, похожую на shared_ptr, назовите ее Object.
Это создаст новый объект. Теперь с перегрузкой своих операторов вы можете управлять GC.
Все, что вам нужно сделать сейчас, просто реализовать один из алгоритмов GC