如何在C++中实现垃圾回收

Question

我看到有人在讨论在 C 语言中实现垃圾回收，但是有些人认为由于 C 是弱类型语言，这是不可能的。我想知道如何在 C++ 中实现垃圾回收。

我想要一些关于如何实现垃圾回收的通用思路。非常感谢！

这是我朋友告诉我的一个 Bloomberg 面试题。他那时表现很差。我们想知道您对此的想法。

- Josh Morrison

---

在编译器/RTL中？还是在用户空间中？后者必然涉及大量的编程纪律（即不使用指针进行内存操作）；使用某种智能指针/引用计数方案会更便宜。对于C++来说，这更加自然。 - Seva Alekseyev

我认为这个问题在用户空间中... - Josh Morrison

这些论文可能会引起您的兴趣。 n2527 n2585(pdf) n2586 n2587 n2670 - Ise Wisteria

Answer 1

对于C和C ++中的垃圾回收，存在以下几个困难点：

1. 指针可以强制转换为整数，反之亦然。这意味着我可能有一块只能通过将整数强制转换为指针，然后取消引用它来访问的内存块。 垃圾回收器必须小心，以免认为一个块是不可达的，而实际上它仍然可以被访问。

2. 指针不是不透明的。 许多垃圾收集器（如停止并复制收集器）喜欢移动内存块或紧缩它们以节省空间。 由于您可以显式地查看C和C ++中的指针值，因此正确实现可能会很困难。 如果有人正在使用类型转换进行某些棘手的操作，并且您移动了内存块，则必须确保正确更新整数。

3. 内存管理可以明确进行。 任何垃圾收集器都需要考虑用户可以随时显式释放内存块。

4. 在C++中，分配/释放和对象构建/销毁是分开的。 可以分配一块足够容纳对象的内存块，而不必实际在其中构建任何对象。 一个好的垃圾收集器需要知道，在回收内存时，是否调用可能分配在其中的任何对象的析构函数。 对于标准库容器尤其如此，它们经常使用std :: allocator以出于效率原因利用这种技巧。

5. 内存可以从不同区域分配。 C和C ++可以从内置自由存储（malloc / free或new / delete）或通过mmap或其他系统调用从操作系统中获得内存，并且在C ++中，可以使用get_temporary_buffer或return_temporary_buffer从中获取内存。 程序还可能从某些第三方库获取内存。 一个好的垃圾回收器需要能够跟踪这些其他池中内存的引用，并且（可能）要负责清理它们。

指针可以指向对象或数组的中间位置。在许多像Java这样的垃圾回收语言中，对象引用总是指向对象的起始位置。而在C和C++中，指针可以指向数组的中间位置，而在C++中，如果使用了多重继承，则可以指向对象的中间位置。这会极大地复杂化检测什么东西仍然是可达的逻辑。

简而言之，为C或C++构建垃圾回收器非常困难。大多数在C和C++中进行垃圾回收的库都采取了非常保守的方法，并且从技术上讲是不可行的-它们假设您不会将指针转换为整数，将其写入磁盘，然后在以后的某个时间点将其加载回来。他们还假设内存中任何大小为指针的值都可能是指针，因此有时会拒绝释放不可达的内存，因为有一定的机会存在指向它的指针。

正如其他人所指出的，Boehm GC确实对C和C++进行垃圾回收，但受到上述限制。

有趣的是，C++11包括一些新的库函数，允许程序员标记内存区域作为可到达和不可到达，以期望未来的垃圾回收工作。使用这种信息可能有可能在将来构建一个真正优秀的C++11垃圾回收器。但与此同时，您需要非常小心，不要违反上述规则。

- templatetypedef

---

这意味着我可以拥有一块只能通过将整数类型转换为指针，然后取消引用该指针才能访问的内存块。而且没有任何GC算法可以处理 intptr_t x = rand(); intptr_t y = ((intptr_t)p)^x; /* 丢弃p，然后过一段时间 */; use_the_ptr((char*)(x^y));。你需要用户的一些合作。 - Steve Jessop

C++11中有哪些新的库函数可以实现这个？我很想知道 :) - djhaskin987

Answer 2

了解一下Boehm垃圾回收器。

- yan

Answer 3

C语言不是C++，但两者都有相同的“弱类型”问题。然而，引起问题的并不是隐式类型转换，而是对数据结构库的“拼凑”（破坏类型系统）倾向。

在C和/或C++中存在垃圾回收器。Boehm保守收集器可能是最著名的。它是保守的，因为如果它看到一个类似指向某个对象的指针的位模式，它就不会回收该对象。那个值可能完全是另一种类型的值，所以对象可能被回收，但“保守”的意思是要玩得安全。

然而，即使是保守的收集器也可能被愚弄，如果使用计算出来的指针。例如，有一种数据结构，每个列表节点都有一个字段，给出下一个节点和前一个节点地址之间的差异。这个想法是用单个链接给双向链接行为，以更复杂的迭代器为代价。由于大多数节点没有显式指针，它们可能被错误地回收。

当然，这是一个非常特殊的例外情况。

更重要的是，你只能有可靠的析构函数或垃圾回收，不能两者兼备。当收集循环垃圾时，收集器无法决定先调用哪个析构函数。

由于RAII模式在C++中普遍存在，并且依赖于析构函数，因此我认为存在冲突。可能有有效的例外情况，但我的观点是，如果你想要垃圾回收，应该使用从头到尾专门为垃圾回收设计的语言（Java、C#等）。

- user180247

---

我不明白为什么RAII和GC之间会有冲突。RAII在处理资源方面比GC好得多，但是对于涉及不持有资源（例如字符串）的不可变对象的某些情况，跟踪垃圾收集器比RAII更好。将RAII与跟踪垃圾收集器结合使用还可以确定地捕获许多场景，否则这些场景将导致无法捕获的未定义行为（对于普通C++对象，尝试在删除后使用对象就是纯粹的UB；在GC系统中，对象的方法可以测试它们是否被调用）。 - supercat

...已被要求清理其资源，因此不再可用，并在需要时发出警报。不幸的是，编程语言似乎采取了二选一的方法，而不是尝试将它们结合起来。 - supercat

@supercat - 就个人而言，我会着重强调引用循环很少甚至从未存在，除非作为数据结构的一部分。即使是基于静态类型可能具有引用循环但实际上从不发生的结构，在实践中也很少出现，除了数据结构之外。基本上，似乎需要对仅（直接）管理内存的对象进行潜在循环引用，并对可能管理任何资源的对象进行非循环引用。 - user180247

一个足够强大的静态类型系统可以管理这个问题，保持编译时证明只有在有效的情况下才会发生循环，因此引用循环问题永远不会发生，除非需要比释放内存更复杂的清理。但是这在主流语言中并不会发生。我知道（仅仅）关于依赖类型语言的足够多，以知道原则上应该能够做到这一点，但程序员必须编写所有“证明”。 - user180247

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - user180247

Answer 4

你可以使用智能指针或创建自己的容器对象来跟踪引用和处理内存分配等问题。智能指针可能更可取。通常情况下，你可以完全避免动态堆分配。

例如：

char* pCharArray = new char[128];
// do some stuff with characters
delete [] pCharArray;

上述代码的风险在于，如果新建和删除之间出现任何问题，您的删除操作将无法执行。类似上述代码的内容可以轻松地改为更安全的"垃圾收集"代码：

std::vector<char> charArray;
// do some stuff with characters

从实际编码角度来看，彭博社的面试问题常常与实际情况不符。像大多数面试官一样，他们主要关注您的思维方式和沟通能力，而不是真正的解决方案。

- AJG85

---

@GMan - AJG85使用的原始示例是一个简单的固定大小C样式数组 - 只是在堆上而不是栈上。因此，在这种情况下并非无意义。对于您不需要的功能而言，其开销可能微不足道，但仍然是一个开销。 - user180247

@Daniel - 我发现在许多情况下，boost::scoped_array 通过不可复制来实现更安全，但由于同样的原因，它无法在STL容器中使用。基于性能考虑，这将是我使用 std::vector 的 Boost 替代方案。 - AJG85

@Gman和Steve-尽量不要过多地审查我的简单示例，它只是为了说明一个观点。在某些情况下，为了简单和稳定性而增加一些开销是可取的。有时候，性能是唯一关注的问题。在这两种情况下，C++都有你可以使用的工具来实现你想要的功能，所以你们两个都是正确的。 - AJG85

@Daniel - 在堆栈上的C风格数组仍然具有析构函数清理。我预计boost::shared_array和boost::scoped_array各自都有优势，所以感谢您的提示 - 真的是时候让我学习如何正确使用一些boost库了。 - user180247

根据你所使用的类型，大多数情况下最好使用std::vector vec(size)或vec.resize(size)。它将产生与C风格数组相同的性能，可以进行复制，并且具有异常安全性。实质上，使用最适合你实现的方法。 - deceleratedcaviar

Answer 5

你可以阅读关于shared_ptr结构体的内容。

它实现了一个简单的引用计数垃圾回收器。

如果你想要一个真正的垃圾回收器，你可以重载new运算符。

创建一个类似于shared_ptr的结构体，称之为Object。

这将包装新创建的对象。现在通过重载其运算符，你可以控制GC。

现在你只需要实现其中的一种GC算法即可。

- Yochai Timmer

Answer 6

你看到的说法是错误的；Boehm收集器支持C和C++。我建议阅读Boehm收集器的文档（特别是这个页面），以获得如何在C或C++中编写垃圾收集器的良好概述。

- Marcelo Cantos