C 程序中的垃圾回收

作者：Gianluca Insolvibile
于 2003 年 8 月 31 日

当我听说将垃圾回收技术引入 C 或 C++ 程序时，我脑海中出现的第一个词是“胡说八道”。和任何其他热爱这门语言的体面的 C 程序员一样，将我自己的内存管理交给别人似乎几乎是冒犯。15 年前，当我第一次听说编译器会代表我生成汇编代码时，我也有类似的感觉。我过去习惯直接用 6510 操作码编写代码，但那是 Commodore 64——一个完全不同的故事。

什么是垃圾回收？

垃圾回收 (GC) 是一种为未使用的内存块提供自动内存回收的机制。程序员动态分配内存，但是当不再需要某个块时，他们不必使用 free() 调用显式地将其返回给系统。GC 引擎负责识别特定分配的内存块（堆）不再使用，并将其放回空闲内存区域。GC 由 John McCarthy 于 1958 年引入，作为 LISP 语言的内存管理机制。从那时起，GC 算法不断发展，现在可以与显式内存管理竞争。几种语言本身就基于 GC。Java 可能是最流行的语言，其他语言包括 LISP、Scheme、Smalltalk、Perl 和 Python。C 和 C++ 秉承对系统资源管理采取可敬的底层方法的传统，是此列表中最值得注意的例外。

存在许多不同的垃圾回收方法，从而产生了一些算法族，包括引用计数、标记和清除以及复制 GC。混合算法以及分代和保守变体完善了这一图景。选择特定的 GC 算法通常不是程序员的任务，因为内存管理系统是由采用的编程语言强加的。此规则的一个例外是 Boehm-Demers-Weiser (BDW) GC 库，这是一个流行的软件包，允许 C 和 C++ 程序员将自动内存管理包含到他们的程序中。问题是：他们为什么要这样做呢？

Boehm-Demers-Weiser GC 库

BDW 库是一个免费提供的库，为 C 和 C++ 程序提供垃圾回收功能。它采用的算法属于标记和清除收集器系列，其中 GC 分为两个阶段。首先，扫描所有活动内存以标记未使用的块。然后，清除阶段负责将标记的块放入空闲块列表。这两个阶段可以而且通常是分开执行的，以提高库的总体响应时间。BDW 算法也是分代的；它将空闲空间搜索集中在新块上。这是基于旧块在统计上寿命更长的想法。换句话说，大多数分配的块的生命周期都很短。最后，BDW 算法是保守的，因为它需要假设哪些变量实际上是指向动态数据的指针，哪些变量只是看起来像那样。这是 C 和 C++ 作为弱类型语言的结果。

BDW 收集器以静态或动态库的形式提供，并且可以通过下载相应的软件包（请参阅“资源”）并运行传统的 configure、make 和 make install 命令轻松安装。一些 Linux 发行版也带有预制软件包。例如，对于 Gentoo，您只需要键入emerge boehm-gc来安装它。安装的文件包括共享对象 (libgc.o) 和静态库 (libgc.a)。

使用该库是一项相当简单的任务；对于新开发的程序，您只需调用 GC_alloc() 来获取内存，然后在不再需要它时忘记它。“忘记它”意味着将引用它的所有指针设置为 NULL。对于已有的源代码，请将所有分配调用（malloc、calloc、realloc）替换为 GC 赋予的调用。所有 free() 调用都替换为无，但请将任何相关的指针设置为 NULL。

GC_alloc() 实际上将分配的内存设置为零，以最大程度地减少 GC 引擎将先前存在的值误解为有效指针的风险。因此，GC_alloc() 的行为更像 calloc() 而不是 malloc()。

在现有 C 程序中使用 GC

如果您想在现有应用程序中尝试 GC，则无需手动编辑源代码来更改 malloc 和 free。为了将这些调用重定向到 GC 版本，您基本上有三个选项：使用宏、修改 malloc 钩子以及使用 libgc 的 malloc() 覆盖 glibc 的 malloc()。第一种方法是最简单的；您只需要插入类似

#define malloc(x) GC_malloc(x)
#define calloc(n,x) GC_malloc((n)*(x))
#define realloc(p,x) GC_realloc((p),(x))
#define free(x) (x) = NULL

到适当的包含文件中。此代码仅替换代码中包含的显式调用，将启动和库分配留给传统的 malloc/free 调用。

另一种方法是将 malloc 及其朋友钩到您自己的函数，这些函数反过来会调用 GC 版本。清单 1 显示了如何执行此操作，它可以直接链接到现有程序。有关这些钩子的详细信息，请参阅我的文章“高级内存分配”[LJ，2003 年 5 月]。使用此方法，任何堆分配都保证通过 libgc，即使它不是直接由您的代码执行的。

清单 1. 使用 glibc 的 malloc 和 free 钩子启用垃圾回收

/*
 * Using the malloc hooks to substitute GC functions
 * to existing malloc/free.
 * Similar wrapper functions can be written
 * to redirect calloc() and realloc()
 */

#include <malloc.h>
#include <gc.h>

static void gc_wrapper_init(void);
static void *gc_wrapper_malloc(size_t,const void *);
static void gc_wrapper_free(void*, const void *);

__malloc_ptr_t (*old_malloc_hook)
    __MALLOC_PMT((size_t __size,
                  __const __malloc_ptr_t));
void (*old_free_hook)
    __MALLOC_PMT ((__malloc_ptr_t __ptr,
                   __const __malloc_ptr_t));


/* Override initializing hook from the C library. */
void (*__malloc_initialize_hook)(void) =
                                    gc_wrapper_init;

static void gc_wrapper_init() {
    old_malloc_hook = __malloc_hook;
    old_free_hook = __free_hook;
    __malloc_hook = gc_wrapper_malloc;
    __free_hook = gc_wrapper_free;
}

void *
gc_wrapper_malloc(size_t size, const void *ptr) {
    void *result;
    /* Restore all old hooks */
    __malloc_hook = old_malloc_hook;
    __free_hook = old_free_hook;

    /* Call the Boehm malloc */
    result = GC_malloc(size);


    /* Save underlying hooks */
    old_malloc_hook = __malloc_hook;
    old_free_hook = __free_hook;

    /* Restore our own hooks */
    __malloc_hook = gc_wrapper_malloc;
    __free_hook = gc_wrapper_free;

    return result;
}

static void
gc_wrapper_free(void *ptr, const void *caller)
{
  /* Nothing done! */
}

作为第三种选择，您可以在编译 libgc 库之前将 --enable-redirect-malloc 传递给 configure。这样做为库提供了包装函数，这些函数与标准 glibc malloc 系列具有相同的名称。当与您的代码链接时，libgc 中的函数会覆盖标准函数，其净效果类似于使用 malloc 钩子。不过，在这种情况下，效果是系统范围的，因为任何与 libgc 链接的程序都会受到更改的影响。

不要期望使用这些方法中的任何一种轻松地为大型程序赋予 GC。为了利用 GC 函数并帮助收集器算法高效工作，需要一些简单的技巧。例如，我尝试使用 GC 重新编译 gawk（版本 3.1.1），结果得到的执行文件比原始文件慢十倍。通过一些调整，例如在释放每个指针后将其设置为 NULL，执行时间显着提高，即使它仍然大于原始时间。

新程序中的垃圾回收

如果您正在开发一个新程序，并且想要利用自动内存管理，那么您需要做的就是使用 GC_malloc() 系列代替普通的 malloc() 系列并链接 libgc。不再需要的内存块可以通过将任何引用指针设置为 NULL 来简单地处理掉。或者，您可以调用 GC_free() 立即释放该块。

始终记住，您的整个堆会定期被收集器扫描，以查找未使用的块。如果堆很大，则此操作可能需要一些时间，从而导致程序性能下降。此行为不是最优的，因为通常可以保证大型内存块永远不会包含指针，包括用于文件或网络 I/O 和大型字符串的缓冲区。通常，指针仅包含在小型数据结构（例如列表和树节点）内的固定位置。如果 C 和 C++ 是强类型语言，则收集器可以根据指针类型决定是否扫描内存块。不幸的是，这是不可能的，因为在 C 中，char 指针引用列表节点是完全合法的。

为了获得最佳性能，程序员应尝试向收集器提供一些基本的运行时类型信息。为此，BDW 库提供了一组可用于分配内存的替代函数。GC_malloc_atomic() 可以代替 GC_malloc() 使用，以获取永远不会包含有效指针的内存块。也就是说，收集器在查找活动内存引用时会跳过这些块。此外，这些块在分配时不需要清除。GC_malloc_uncollectable() 和 GC_malloc_stubborn() 也可分别用于分配固定块和很少更改的块。最后，可以使用 GC_malloc_explicitly_typed() 并使用 GC_make_descriptor() 构建块映射来提供一些粗略的类型信息。有关更多信息，请参阅 Linux Journal FTP 站点上的 gc_typed.h [可在 ftp.linuxjournal.com/pub/lj/listings/issue113/6679.tgz 获取]。

收集器的行为也可以由用户通过许多函数调用和变量来控制。其中最有用的包括 GC_gcollect()，它强制对整个堆进行完全垃圾回收；GC_enable_incremental()，它启用增量模式收集；以及 GC_free_space_divisor，它调整频繁收集（高值，导致低堆扩展和高 CPU 开销）与时间效率（低值）之间的权衡。

堆状态和调试信息可通过许多函数获得，包括 GC_get_heap_size()、GC_get_free_bytes()、GC_get_bytes_since_gc()、GC_get_total_bytes() 和 GC_dump()。这些参数和函数中的许多都没有记录在案，甚至在源代码本身中也没有。一如既往，好的编辑器是您的朋友。

性能和行为

对于任何程序都有效的最佳内存管理方法并不存在。给定一个特定的应用程序，必须通过在许多不同因素之间进行折衷来找到最佳解决方案，这些因素包括 CPU 开销、堆扩展、分配延迟，以及最重要的一点，代码的可管理性和健壮性。分析程序并测试不同的内存策略可能是解决这些问题的最佳方案。

垃圾回收和编译器优化

反对 GC 的一个微妙之处是，如果启用了编译器优化，则需要格外小心。收集器可能会错误地认为某个指针已消失，仅仅是因为对它的引用已被优化掉。因此，即使程序仍在使用相应的内存块，也可能会释放该内存块，从而产生明显的后果。因此，为了安全起见，可能会很想关闭编译器优化，从而失去通过使用 GC 获得的部分性能提升。

为了了解 GC 与传统内存管理的行为和性能，我们使用一个名为 gctest 的测试程序进行了实验，该程序循环执行简单列表的创建和销毁。尽管看起来很简单，但该测试提出了一些有趣的观点。源代码实际上没有指导意义，而且太长而无法打印，因此可以在 FTP 站点上下载 (ftp.linuxjournal.com/pub/lj/listings/issue113/6679.tgz)。

gctest 可以通过许多选项进行控制，这些选项允许您试验不同的列表长度和节点大小，以及更改工作参数——启用和禁用 GC 库的特定功能。在我们评论我们使用此测试工具获得的结果之前，重要的是要指出这些结果是在人为的而不是过度真实的环境中获得的。因此，再次邀请您自己测试 GC 库并评估它是否适合您的代码。将此处提供的参数作为库是否适合特定应用程序的可能指标。

我们收集的测量值是总体执行时间、CPU 负载；堆扩展，系统请求的内存量相对于程序实际分配的内存量；以及分配延迟平均值和标准偏差，分配单个内存块需要多长时间以及此时间在不同分配之间变化多少。第一个参数的含义非常明显，无需进一步解释。堆扩展衡量的是已分配内存的碎片程度以及库从操作系统请求的额外内存量。正如我们将看到的，该库可能会分配 1MB 的块十次，在每次分配后释放它，并总共请求 10MB 的系统，就好像释放的内存没有放回空闲列表一样。虽然这有时是期望的行为，需要优化分配策略，但在 RAM 可用性有限的系统上可能会很烦人。如果涉及交换空间，它可能会成为 CPU 开销的另一个来源。最后，分配延迟对于实时应用程序很重要，这些应用程序需要有界的最长分配时间。典型案例是多媒体播放应用程序和需要以可预测的时间量对外部事件做出反应的专用嵌入式系统。

关于结果的一些评论

我们的测试箱 A 是一个 Pentium 4 2.53GHz 系统，具有 1GB 的 RAM，运行 Gentoo Linux（所有代码都针对 CPU 架构进行了优化）和 glibc 2.3，它比 glibc 2.2 具有改进的内存管理算法。测试箱 B 是一台 K6-II 400MHz 笔记本电脑，具有 128MB 的 RAM，运行带有 glibc 2.2 的 Slackware Linux。

我们的第一个测试包括分配一个包含 150,000 个节点的列表，每个节点 16 字节，共 30 次。在每次循环中，都会销毁已分配的列表，即，在传统管理的情况下使用 free() 释放，在 GC 的情况下取消链接。测试命令是

gctest -tu -s 4 -n 150000 -l 30

和

gctest -gu -s 4 -n 150000 -l 30

在测试箱 A 上，使用传统管理的总体执行时间为 3.80 秒，使用 GC 的总体执行时间为 2.43 秒，提高了约 35%。在测试箱 B 上执行的相同测试显示出更大的改进，约为 40%。第一个测试表明，与普遍的看法相反，GC 实际上可能比 malloc/free 快得多。堆扩展相当有限，在这两种情况下都约为 2。更令人惊讶的是，分配延迟是相同的——6.7 微秒——GC 情况下的偏差略大。同样有趣的是，通过在每个循环中调用 GC_gcollect()（选项 -G），总体执行时间减少了 0.1 秒。此结果违反直觉，因为我们在循环中多了一个函数调用。

现在，让我们看看如果在每个循环结束时忘记销毁列表会发生什么。在传统管理的情况下，测试执行速度更快，为 2.58 秒，而 GC 为 3.80 秒，但峰值堆扩展为 140MB，是总体分配内存的两倍。在 GC 的情况下，除非我们在每个循环结束时调用显式收集 (-G)，否则测试会因内存耗尽而中止。通过这样做，我们获得了最低的执行时间，2.32 秒。这可能与我们事先可以想象的相去甚远——这就是为什么实际实验对于找到最佳解决方案至关重要的原因。

相同的测试也在测试箱 B 上执行过，但使用的是未经优化的 Slackware 发行版和 glibc 2.2。有趣的是，尽管 GC 相对于 malloc/free 的改进仍然约为 40%，但在 Gentoo 下，测试的运行速度快了 27%。

我们进行的第二个测试显示了 GC 库的一些局限性。测试条件实际上非常极端：我们尝试分配五个列表，每个列表有 1,500,000 个节点，每个节点长 16 字节。尽管 malloc/free 版本运行正确，但 GC 版本由于内存耗尽而未完成测试。问题可能在于连续分配的大量块。

第三个测试使用了更大的节点，每个节点 140 字节，以及更短的列表长度，150,000 个节点。我们运行了

gctest -tu -s 128 -n 150000 -l 5

和

gctest -gu -s 128 -n 150000 -l 5

在这些条件下，GC 相对于 malloc/free 的改进约为 20%，分别为 0.85 秒和 0.60 秒。但请记住，GC 库始终清除已分配的块，但 malloc() 不会。与此操作相关的开销随着节点大小线性增长，因此对于较大的节点更为重要。为了进行公平的比较，我们需要在调用 GC_malloc() 的那些点将 malloc() 替换为 calloc()，就像在

gctest -tuc -s 128 -n 150000 -l 5

此测试产生的执行时间为 0.88 秒，GC 的改进率达到 32%。在 GC 情况下，堆扩展更大，值为 1.7，而为 1.0。传统管理和 GC 管理的分配延迟实际上是相同的，尽管后者经历了更大的延迟变化。启用增量收集（-i 选项）并没有降低变化，尽管引入对 GC_free()（-F 选项）的调用以显式释放列表节点实际上确实比 malloc/free 情况产生了更好的结果，无论是在执行时间还是延迟方面。但是，在这种情况下，我们并没有严格使用真正的垃圾回收方法。

测试更大的内存块使传统内存管理和 GC 内存管理之间的差异非常明显。在 4KB 节点上，GC 在执行时间方面与 malloc/free 相比表现非常差，分别为 0.85 秒和 2 秒；堆扩展分别为 2.75 和 1；延迟分别为 0.7 毫秒和 1.6 微秒。与 calloc/free 性能相比，GC 的执行时间仍然具有很强的竞争力（快 40%）。但是，与堆和延迟相关的问题仍然存在。

结论

GC 技术通常被神话和传说所包围。在本文中，我们已经表明，GC 实际上可以比 malloc/free 表现更好。然而，这些优势并非免费获得，正确使用该库需要对其内部机制有最少的了解。

对于 GC 是否适合 C 程序，尚无最终定论。目前，BDW 库可以成为您工具箱中的又一个工具，下次您处理复杂的软件时，可以认真考虑它。一些开源项目，如 Mono Project 和 GNU gcj Java 运行时，已经使用它一段时间了。

优点和缺点

在决定 GC 适合弱者并且硬核 C 程序员永远不需要它之前，考虑 GC 相对于传统 C/C++ 内存管理方案可能提供的实际优势可能是有益的。正如 Ellis 和 Stroustrup 在 The Annotated C++ Reference Manual 中所说，“C 程序员认为内存管理太重要了，不能留给计算机。LISP 程序员认为内存管理太重要了，不能留给用户。”

众所周知，与内存相关的问题包含 C 程序员可能遇到的一些最隐蔽和浪费时间的错误。即使是经验丰富的程序员也可能很难追踪由无效访问、溢出写入、访问死内存、内存泄漏等引起的错误。此外，从软件设计的角度来看，防止这种情况的需求通常会导致设计人员在应该解耦的模块之间创建不干净的接口。想想返回动态分配的内存块的函数，然后必须由调用者释放该内存块，或者指向内部静态缓冲区的指针，破坏线程安全——strtok() 是这方面的一个典型例子——更不用说由在多个模块之间共享的内存区域引起的问题。每个模块只有在没有其他模块正在或将要使用它时才必须释放这些区域，从而导致模块本身之间更紧密的耦合。这个问题通常通过使用引用计数来解决，其中为该区域的每个活动用户保留一个内部计数器；多个副本，其中为每个模块保留该区域的一个副本；或者，对于那些喜欢 C++ 的人，智能指针。

GC 是处理 C 中与内存相关问题的有效方法，减轻了程序员的内存核算负担。每个内存块都知道它何时在使用中，实际上，GC 引擎知道，并且当不再引用该块时，该块会自动消失。GC 先验地消除了所有过早释放和内存泄漏问题。

GC 当然也有一些缺点，最令人恼火的是失去了控制感，这困扰着 C 程序员。更具体地说，缺点源于资源的自动化管理，这转化为

  • 不知道未使用的内存块何时实际释放以及是否会释放。当内存块是 C++ 对象时，这会产生进一步的后果，其析构函数在未指定的时间调用。

  • 无法提前确定分配需要多少时间（分配延迟和抖动），这通常是实时系统的一个问题。但是，必须说，传统的 malloc() 有时也会出现这个问题。增量 GC 可以帮助缓解问题并为分配时间提供有限的约束。

  • 由于 GC 处理开销而导致更长的执行时间。这通常不是真的，因为有时与传统 free() 相关的开销等于甚至大于 GC 的开销。从这个意义上讲，只有专门为给定程序编写的存储分配器可能更快。即便如此，程序员通常会在没有初步分析活动的情况下编写自己的内存管理系统，有时会对性能产生负面影响。

  • 更高的内存碎片（堆扩展），这是由于当程序分配更多内存时，GC 引擎未释放未使用的对象而引起的。堆远大于特定时间实际使用的内存量是很常见的。更糟糕的是，堆大小有时与程序启动以来执行的分配总量成正比。这在 RAM 可用性稀缺的系统上可能是一个严重的问题，在这些系统中，可能需要频繁的收集和显式的 free() 调用来限制碎片。

  • 引用局部性降低，这是由于垃圾检测阶段必须遍历整个可寻址堆空间以查找未使用的块。这导致缓存和虚拟内存未命中比传统分配更频繁地发生。分代 GC 算法限制了此问题的严重性。

GC 爱好者声称，考虑到 GC 提供的更简洁的设计和更高的健壮性，这些问题并不那么重要。即使这些优势难以具体评估，它们有时也会在代码可管理性和资源损失之间提供方便的权衡。

最后，BDW 库也可以熟练地用作泄漏检测器；例如，Mozilla 团队就是这样使用它的。有关更多信息，请查看随附的文档。

资源

Boehm-Demers-Weiser 主页 www.hpl.hp.com/personal/Hans_Boehm/gc 提供了该库的源代码以及大量文档和链接，以获取有关 GC 的更多信息。良好的起点是 Hans Boehm 和 David Chase，“垃圾收集器安全 C 编译提案”，1992 年，可在 www.hpl.hp.com/personal/Hans_Boehm/gc/papers/boecha.ps.gz 获取；Paul Wilson，“单处理器垃圾收集技术”，德克萨斯大学，1992 年，可在 ftp.cs.utexas.edu/pub/garbage/gcsurvey.ps 获取；以及 Benjamin Zorn，“保守垃圾收集的测量成本”，技术报告，科罗拉多大学博尔德分校，1992 年。

Gianluca Insolvibile 自内核 0.99pl4 以来一直是 Linux 爱好者。他目前从事网络和数字视频研究与开发。可以通过 g.insolvibile@cpr.it 与他联系。

加载 Disqus 评论