GC может быть реализован с помощью сырых указателей C ++?

Question

Мне было интересно, как сборщик мусора может быть реализован с использованием C ++ полной мощности арифметики указателей. Кроме того, в таких языках, как Java, я не могу назначать буквальные адреса ссылкам. В C ++ это очень гибко.

Я считаю, что в C # есть и то и другое, но опять же, небезопасный указатель в C # является обязанностью программиста.

EITD :: парни, я спрашиваю, могут ли указатели C ++ «такими, какие они есть», теоретически GCed или нет?

Answer 1

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

Проблема real заключается в отсутствии метаданных. GC должен знать, что является указателем, а что нет.

Если оно встречает значение 0x27a2c230, оно должно быть в состоянии определить, является ли оно

• указатель (в этом случае он должен следовать за указателем, чтобы рекурсивно пометить пункт назначения как «используемый»)
• Целое число (То же значение является вполне допустимым целым числом. Возможно, это вообще не указатель)
• или что-то еще, скажем, немного строки.

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

Языки GC имеют много инфраструктуры для решения этой проблемы. C ++ не делает.

ГК Boehm является самым близким, который вы обычно можете получить, и он консервативен в том, что, если что-то может быть указателем, ГК предполагает, что он является единым, что означает, что некоторые данные без необходимости поддерживаются живыми. И поэтому он, скорее всего, сохранит данные, которые должны быть GC-файлами.

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

Answer 2

Да. В 1990-х годах в NeXT существовала система, которая работала так: они отслеживают каждый выделенный блок памяти C / C ++. Периодически они сканируют память, чтобы увидеть, присутствует ли 4-байтовое (или 8-байтовое) значение, связанное с этим адресом памяти. Если это не так, они предполагают, что ссылок нет, и освобождают память. Это аккуратно и легко! Но иногда это портит.

Вот некоторые другие подходы: http://www.hpl.hp.com/personal/Hans_Boehm/gc/

http://developers.sun.com/solaris/articles/libgc.html

Answer 3

Вы имеете в виду что-то вроде smart_ptr ?

Answer 4

Арифметика указателей C ++ позволяет вам создать N + 1 указателей на T [N], & T [0] ... & T [N-1] и на стража & T [N-1] +1. Все это указатели на объект массива T [N]. В этом смысле они похожи на другие «внутренние» указатели, такие как & foo.bar (адрес члена объекта).

Другая арифметика указателей - неопределенное поведение, и одним очевидным примером UB может быть непреднамеренное удаление массива с помощью GC.

Answer 5

Вопрос в том, почему вы? В 90% случаев, когда вы думаете, что сборка мусора была бы полезной, будет достаточен умный вектор-указатель (как в векторе / карте, который удаляет объект при его удалении). Большая часть оставшихся 10% может быть обработана с использованием интерфейсов с подсчетом ссылок.

Answer 6

Конечно, почему нет? Арифметика указателей с точки зрения сборщика мусора ничем не отличается от индексации в массив. Это такие вещи, как список xor с двумя связями, который испортит GC, но это не арифметика указателей, а также неопределенное поведение. Кроме того, существует Boehm, что является своего рода эмпирическим подтверждением, это сборщик мусора, который работает для C ++. Черт побери, они угрожали включить GC в качестве необязательной части C ++ 0x.

Answer 7

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

в качестве примера

int *crazy_pointer;
srand ( time(NULL) );

while(true) {
  crazy_pointer = (int *) rand() % MAX_SIZE_OF_MEMORY:
  printf("$d",*crazy_pointer);
}

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

Да, приведенное выше, скорее всего, приведет к сбою в современных операционных системах, но этот код вполне допустим для C / C ++. Невозможно реализовать GC, который может защитить от такого рода злоупотреблений, если вы разрешите арифметику указателей:)

Answer 8

Бём ГК ?

Он написан на C, а не на C ++, и не идеально подходит для C ++, потому что он не вызывает деструкторов, но, вероятно, более или менее отвечает всем требованиям.

Answer 9

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

Если кто-то желает жить с проверенными во время выполнения операциями с указателями, тем самым снова достигая безопасности типов, когда язык отказался, тогда GC может быть намного более агрессивным. Таким образом, сборка мусора C ++ обычно ограничивается консервативными сборщиками, такими как Boehm-Demers-Weiser GC .