Уплотнение сборщика мусора в С++ 0x

Я внедряю сборщик мусора для личного использования в С++ 0x, и у меня есть вопрос. Очевидно, что механики коллектора зависят от движущихся объектов, и мне было интересно, как реализовать это с точки зрения типов интеллектуального указателя, которые указывают на него. Я думал о любом указателе на указатель в самом типе указателя, или коллекционер поддерживает список указателей, указывающих на каждый объект, чтобы их можно было модифицировать, устраняя необходимость двойного исправления при доступе указатель, но добавив некоторые дополнительные накладные расходы во время сбора и дополнительных издержек памяти. Какой лучший способ пойти сюда?

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

Ответ 1

Это довольно прямой вопрос, поэтому прямо ответьте:

Mark-and-sweep (а иногда mark-and-compact, чтобы избежать фрагментации кучи) является самым быстрым, когда речь идет о распределении и доступе (избегая двойных de-refs). Это также очень легко реализовать. Поскольку вы не беспокоитесь о влиянии производительности коллекции (mark-and-sweep имеет тенденцию к замораживанию процесса в недетерминистически), это должен быть путь.

Сведения о реализации, найденные по адресу:

Ответ 2

Нет ничего прямолинейного относительно прививки на дополнительном GC на С++, не говоря уже о алгоритме уплотнения. Не совсем ясно, что вы пытаетесь сделать и как оно будет взаимодействовать с остальным кодом С++.

Я на самом деле написал gc на С++, который работает с существующим С++-кодом, и у него был катком на одном этапе (хотя я уронил его, потому что он был слишком медленным). Но есть много неприятных семантических проблем. Я упоминал Бьярне всего несколько недель назад, что на С++ отсутствует оператор, необходимый для правильной работы, и ситуация в том, что он вряд ли когда-либо существует, потому что он имеет ограниченную полезность.

На самом деле вам нужен оператор re-addres-me. Случается, что вы фактически не перемещаете объекты. Вы просто используете mmap для изменения адреса объекта. Это намного быстрее, и, по сути, он использует функции VM для обеспечения ручек.

Без этого средства у вас должен быть способ выполнить перекрывающееся перемещение объекта, чего вы не можете сделать на С++ эффективно: сначала вам нужно перейти к временному. В C это намного проще, вы можете использовать memmove. На определенном этапе все указатели на или перемещенные объекты должны быть скорректированы.

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

Так что не мешайте ручкам, они не работают.

Это то, что я сделал в Феликсе: вы называете new(shape, collector) T(args). Здесь shape является дескриптором типа, включая список смещений, содержащих указатели (GC), и адрес подпрограммы для завершения объекта (по умолчанию он вызывает деструктор).

Он также содержит флаг, указывающий, можно ли перемещать объект с помощью memmove. Если объект большой или неподвижный, он выделяется malloc. Если объект небольшой и подвижный, он выделяется на арену, если на арене есть место.

Арена уплотняется, перемещая все объекты в ней и используя информацию о форме, чтобы глобально настроить все указатели на или в эти объекты. Уплотнение может выполняться постепенно.

Недостатком программиста на С++ является необходимость создания правильного объекта shape для передачи. Это не беспокоит меня, потому что я реализую язык, который может автоматически генерировать информацию о форме.

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

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

Ответ 3

Генерация детского сада даст вам наилучшую возможную производительность распределения, потому что это всего лишь указатель.

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