我正在使用C++0x实现一个紧凑型垃圾收集器，需要涉及移动对象，因此我有一个问题。我在思考如何通过智能指针类型来实现移动对象的机制。我一直在考虑在指针类型本身中使用指向指针的指针，或者收集器维护指向每个对象的指针列表，这样它们可以被修改，在访问指针时删除了双重引用的需求但增加了一些额外的收集和内存开销。请问这里最好的方法是什么？
编辑：我的主要关注点是快速分配和访问。我不关心特别高效的收集或其他维护，因为这不是GC的主要目的。
3个回答
11
在C++中添加额外的GC，特别是压缩算法，这并不是一件容易的事情。你需要确切地知道你要做什么以及它如何与其他C++代码交互，这都不是很清晰。
我曾经在C++中编写过一个GC，可以与现有的C++代码一起使用，而且它还有一个压缩算法(虽然我放弃了它，因为速度太慢)。但是有许多问题需要解决。几周前我向Bjarne提到，C++缺少必要的操作符，导致无法完美实现此功能，而且由于其效用有限，这种情况似乎永远也不会发生。
实际上，你需要的是“重新寻址”运算符。它的作用是，并不实际移动对象，而是使用mmap改变对象地址。这样做更快，并且实际上是使用VM功能提供句柄。
没有这个功能，你必须有一种方法来执行重叠移动对象，这在C++中效率不高：你必须先移动到一个临时地址。在C语言中，这更容易，你可以使用memmove函数。在某个阶段，所有指向或进入移动对象的指针都必须进行调整。
使用句柄并不能解决这个问题，它只是将任意大小的对象问题简化为常量大小的问题：在数组中更容易管理，但同样存在问题：你必须管理存储。如果你随机移除了数组中的很多句柄.. 你仍然会遇到碎片化问题。
因此，不要浪费时间去使用句柄，它们行不通。
在Felix中我使用的方法是：你需要调用
它还包含一个标志，说明对象是否可以通过
通过移动arena中的所有对象并使用形状信息来全局调整指向或进入这些对象的所有指针，可以压缩arena。压缩可以逐步进行。
对于C++程序员而言，缺点是需要构建一个正确的
现在的关键是：要进行压缩，你必须使用精确的收集器。压缩无法与保守的收集器一起使用。这非常重要。如果您看到一个看起来像指针但实际上是整数的值，允许一些泄漏是可以接受的：有些对象不会被收集，但这通常没有什么大不了的。但是对于压缩，您必须调整指针，但最好不要更改该整数：因此，您必须确定何时为指针，因此您的收集器必须是精确的：形状必须已知。
在Ocaml中，这相对简单：一切都是指针或整数，并且低位在运行时用于告知。所指向的对象具有指示类型的代码，并且只有几种类型：标量（不扫描）或聚合（扫描它，它仅包含整数或指针）。
我曾经在C++中编写过一个GC，可以与现有的C++代码一起使用，而且它还有一个压缩算法(虽然我放弃了它，因为速度太慢)。但是有许多问题需要解决。几周前我向Bjarne提到，C++缺少必要的操作符，导致无法完美实现此功能，而且由于其效用有限，这种情况似乎永远也不会发生。
实际上，你需要的是“重新寻址”运算符。它的作用是，并不实际移动对象，而是使用mmap改变对象地址。这样做更快，并且实际上是使用VM功能提供句柄。
没有这个功能，你必须有一种方法来执行重叠移动对象，这在C++中效率不高：你必须先移动到一个临时地址。在C语言中，这更容易，你可以使用memmove函数。在某个阶段，所有指向或进入移动对象的指针都必须进行调整。
使用句柄并不能解决这个问题，它只是将任意大小的对象问题简化为常量大小的问题：在数组中更容易管理，但同样存在问题：你必须管理存储。如果你随机移除了数组中的很多句柄.. 你仍然会遇到碎片化问题。
因此，不要浪费时间去使用句柄，它们行不通。
在Felix中我使用的方法是：你需要调用
new(shape, collector) T(args)。这里的shape是一个类型的描述符，包括一个偏移量列表，其中包含(GC)指针，并且还包含一个用于最终化对象的例程的地址(默认情况下，它调用析构函数)。它还包含一个标志，说明对象是否可以通过
memmove移动。如果对象很大或者是不可移动的，它将由malloc分配。如果对象很小且可移动，则在arena中分配，前提是arena中有空间。通过移动arena中的所有对象并使用形状信息来全局调整指向或进入这些对象的所有指针，可以压缩arena。压缩可以逐步进行。
对于C++程序员而言，缺点是需要构建一个正确的
shape对象来传递。这并不困扰我，因为我正在实现一种可以自动生成形状信息的语言。现在的关键是：要进行压缩，你必须使用精确的收集器。压缩无法与保守的收集器一起使用。这非常重要。如果您看到一个看起来像指针但实际上是整数的值，允许一些泄漏是可以接受的：有些对象不会被收集，但这通常没有什么大不了的。但是对于压缩，您必须调整指针，但最好不要更改该整数：因此，您必须确定何时为指针，因此您的收集器必须是精确的：形状必须已知。
在Ocaml中，这相对简单：一切都是指针或整数，并且低位在运行时用于告知。所指向的对象具有指示类型的代码，并且只有几种类型：标量（不扫描）或聚合（扫描它，它仅包含整数或指针）。
- Yttrill
1
2有了句柄，我可以理解为什么句柄池的大小将是曾经存在的句柄的最大数量，但如果句柄不可共享（需要代码想要存储在句柄中的引用的副本，必须构造一个新的句柄，将引用从旧句柄复制到新句柄，然后在不再需要时销毁其新句柄），我认为它们可以很快，很容易地被回收利用。除非任务需要大量的句柄，然后再也不需要接近那么多的句柄，否则我不认为碎片化会成为问题。 - supercat
1
这是一个相当直截了当的问题，所以这里有一个直截了当的答案：
实现细节请参见：
标记-清除（有时为了避免堆碎片而使用标记-压缩）在分配和访问方面是最快的（避免双重引用）。它也非常容易实现。由于您不必担心收集性能影响（标记-清除往往会在非确定性情况下冻结进程），因此应该选择这种方式。实现细节请参见：
- David Titarenco
3
这似乎很容易 - 如果唯一的GC引用存在于堆栈、本地堆或静态分配中。那么我该如何处理来自本地堆的GC引用呢？ - Puppy
我的意思是，堆栈、GC堆、静态分配。 - Puppy
1实际上，标记-清除的分配性能相对较差。代际提供快速分配，并通常与标记-清除结合使用以处理最老一代。 - J D
0
使用幼儿园代际将为您提供最佳的分配性能，因为它只是一个指针增量。
您可以通过使用技术（如影子堆栈）来实现指针更新而不使用双重间接引用，但如果您手动编写此C++代码，则这将非常缓慢且容易出错。
- J D
2
1实际上，如果您正在封装C++代码，则避免GC可以获得最佳性能。一般来说，全局GC非常糟糕。它不可扩展，会清除缓存，无法与多处理兼容等。[看看Ocaml，仍然停留在单线程领域]只有在您可以分区和本地化操作并且不需要GC时，GC才变得可行。在FPL中进行装箱是有害的。Rust语言旨在实现这些目标，但为此放弃了多线程（共享内存并发）。 - Yttrill
1只是为了明确：Felix使用一个非常慢的天真收集器，它不敢移动东西（压缩器被丢弃了）。然而，这并不意味着它很慢，因为它也可以像传统的C++列表对象一样执行操作，这不需要任何GC：它使用抽象来隔离对象节点与外部世界。GC需要扫描列表值中的指针，但从不必回收节点。因此，使用C++，我们已经在程序的某个部分消除了对GC的需求。只有在存在循环时才真正需要GC。 - Yttrill
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
new进行补充，而不是替代它。 - Puppy