Сборка мусора и информация о типе среды выполнения

Question

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

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

Решение fixnum на самом деле очень хорошее, очень ясно, какое значение является указателем, а какое нет. Какие другие часто используемые решения для хранения информации о типах существуют?

Кроме того, мне интересно, что такое fixnum. Не означает ли это, что вы ограничены фиксированными значениями для каждого индекса массива? Или есть какой-то обходной путь для получения полных 64-битных целых чисел?

Answer 1

В основном, для достижения точной маркировки вам нужны метаданные, указывающие, какие слова используются в качестве указателей, а какие нет.

Эти метаданные можно хранить для каждой ссылки, как это делает emacs. Если для вашего языка / реализации вы не заботитесь об использовании памяти, вы можете даже делать ссылки больше, чем слова (возможно, в два раза больше), чтобы каждая ссылка могла нести информацию о типе, а также данные из одного слова. Таким образом, вы можете получить фиксированный номер полного размера 32-битного указателя, за счет того, что все ссылки будут 64-битными.

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

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

Обратите внимание, что сборка мусора не обязательно требует точной маркировки. Вы можете рассматривать каждое слово как указатель, независимо от того, действительно оно или нет, и найти его в «большом списке всего» сборщика мусора. решить, может ли он правдоподобно ссылаться на объект, который еще не был помечен, и, если это так, рассматривать его как ссылку на этот объект. Это просто, но цена, конечно, в том, что он находится где-то между «довольно медленно». и "очень медленно", в зависимости от того, какие структуры данных ваш gc использует для поиска. Кроме того, иногда целочисленное значение имеет то же значение, что и адрес объекта, на который нет ссылок, и заставляет вас хранить целую кучу объектов, которые должны были быть собраны. Поэтому такой сборщик мусора не может дать надежных гарантий относительно когда-либо собранных объектов, на которые нет ссылок. Это может быть хорошо для игрушечной реализации или первой рабочей версии, но вряд ли будет популярным среди пользователей.

Смешанный подход может, скажем, делать точную маркировку объектов, но не областей стека, где вещи становятся особенно волосатыми. Например, если вы пишете JIT, который может создать код, в котором адрес объекта, на который ссылаются, появляется только в регистрах, а не в ваших обычных слотах стека, тогда вам может потребоваться не точно следовать области стека, где ОС хранит регистры, когда она отменил запланированный поток для запуска сборщика мусора. Что, вероятно, довольно неудобно, поэтому разумный подход (потенциально приводящий к более медленному коду) будет требовать, чтобы JIT всегда сохранял копию всех значений указателя, которые он использует, в точно маркированном стеке.

Answer 2

В Squeak (также, я полагаю, Scheme и многие другие динамические языки) у вас есть SmallInteger , класс 31-разрядных целых чисел со знаком и классы для произвольно больших целых чисел, например, <Код> LargePositiveInteger . Вполне могут быть и другие представления, 64-разрядные целые числа, либо как полные объекты, либо с парой битов, как "Я не указатель". флаги.

Но арифметические методы кодируются для обработки избыточных / недостаточных потоков, так что если вы добавите один к SmallInteger maxVal , вы получите 2 ^ 30 + 1 как экземпляр LargePositiveInteger , и если вы вычтете один обратно из него, вы получите 2 ^ 30 как SmallInteger .