在了解 GC 算法 之前，我们需要先来了解一些与算法有关的基本概念。

目录

  • GC 的定义
  • 对象 / 头 / 域
  • 指针
  • mutator
  • 堆
  • 活动对象 / 非活动对象
  • 分配 (allocation)
  • 分块 (chunk)
  • 根 (root)
  • 吞吐量 (throughput)
  • 最大暂停时间
  • 堆使用效率
  • 访问局部性

GC 的定义

GC 是 Garbage Collection 的简称，也就是垃圾收集

Garbage Collector：垃圾收集器

Minor GC：小型 GC

Major GC：大型 GC

Full GC：完全 GC（为了清晰起见，一般直接译为 Full GC）

对象 / 头 / 域

对象

在 GC 的世界中，对象表示的是 “通过应用程序利用的数据的集合”。对象配置在内存空间里。GC 根据情况将配置好的对象进行移动或销毁操作。因此，对象是 GC 的基本单位。

对象由头（header）和域（field）构成。在对象内部，头之后存在 1 个及 1 个以上的域。如图 1.1 所示：

GC_Object

头

用于保存对象本身信息，主要含有以下信息：

  • 对象的大小
  • 对象的种类

域

对象使用者在对象中可访问的部分称为 “域”。

域中的数据类型大致分为两种：

  • 指针：指针是指向内存空间中某块区域的值。
  • 非指针：指的是在编程中直接使用值本身。例如：数值、字符以及真假值。

指针

通过 GC，对象会被销毁或保留，这时候起到关键作用的就是指针，因为 GC 是根据对象的指针指向去搜寻其他对象的，GC 对于非指针不进行任何操作。

我们把图 1.2 中的 B 和 C 称为 A 的子对象。对某个对象的子对象进行某项处理是 GC 的基本操作。

GC_Pointer

mutator

mutator，是 “改变某物” 的意思，那要改变什么呢？ 那就是 GC 对象间的引用关系，它的实体就是 “应用程序”。
mutator 进行的实际操作：

  • 生成对象
  • 更新指针

mutator 在进行这些操作时，会同时为应用程序的用户进行一些处理，随着这些处理的增加，对象间的引用关系也会发生 “改变”，随之，也会产生垃圾，负责回收这些垃圾的机制就是 GC。

堆

堆 指的是用于动态（也就是执行程序时）存放对象的内存空间。当 mutator 申请存放对象时， 所需的内存空间就会从这个堆中被分配给 mutator。

GC 是管理堆中已分配对象的机制。在开始执行 mutator 前，GC 要分配用于堆的内存空间。 一旦开始执行 mutator，程序就会按照 mutator 的要求在堆中存放对象。等到堆被对象占满后， GC 就会启动，从而分配可用空间。如果不能分配足够的可用空间，一般情况下我们就要扩大堆。

我们把 $heap_start 定为指向堆首地址的指针，把 $heap_end 定为指向堆末尾下一个地址的指针。也就是说， $heap_end 等于 $heap_start + HEAP_SIZE。

GC_Heap

活动对象 / 非活动对象

分配到内存空间中的对象中那些能通过 mutator 引用的对象称为 “活动对象”。反之，那些不能通过程序引用的对象称为 “非活动对象”。

GC 会保留活动对象，销毁非活动对象。当销毁非活动对象时，其原本占据的内 存空间会得到解放，供下一个要分配的新对象使用。

GC_Live_Dead

分配 (allocation)

分配（allocation）指的是在内存空间中分配对象。当 mutator 需要新对象时，就会向分配器（allocator）申请一个大小合适的空间。分配器则在堆的可用空间中找寻满足要求的空间， 返回给 mutator。

分块 (chunk)

初始状态下，堆被一个大的分块所占据。

然后，程序会根据 mutator 的要求把这个分块分割成合适的大小，作为（活动）对象使用。 活动对象不久后会转化为垃圾被回收。此时，这部分被回收的内存空间再次成为分块，为下次 被利用做准备。也就是说，内存里的各个区块都重复着分块→活动对象→垃圾（非活动对象）→ 分块→…… 这样的过程。

根 (root)

在 GC 的世界里，指的是指向对象指针的” 起点”。

GC_Root

评价标准

吞吐量 (throughput)

吞吐量（throughput）指的是 “在单位时间内的处理能力”。

GC_Throughput

在 mutator 整个执行过程中，GC 一共启动了 3 次，我们把花费的时间分别设为 A、B、C。 也就是说，GC 总共花费的时间为（A ＋ B ＋ C）。另一方面，我们前面提到过，以 GC 为对象的堆大小是 HEAP_SIZE。 也就是说，在大小为 HEAP_SIZE 的堆进行内存管理，要花费的时长 为（A ＋ B ＋ C）。

因此，这种情况下 GC 的吞吐量为 HEAP_SIZE /（A ＋ B ＋ C）。

最大暂停时间

最大暂停时间指的是 “因执行 GC 而暂停执行 mutator 的最长时间”。图 1.7 中最大暂停时间是 A～C 的最大值，也就是 B。

不管尝试哪种 GC 算法，我们都会发现较大的吞吐量和较短的最大暂停时间不可兼得。所以应根据执行的应用所重视的指标的不同，来分别采用不同的 GC 算法。

堆使用效率

左右堆使用效率的因素有两个：头的大小和堆的用法。

头的大小

在堆中堆放的信息越多，GC 的效率也就越高，吞吐量也就随之得到改善。 但毋庸置疑，头越小越好。因此为了执行 GC，需要把在头中堆放的信息控制在最小限度。

堆的用法

根据堆的用法，堆使用效率也会出现巨大的差异。举个例子，GC 复制算法中将 堆二等分，每次只使用一半，交替进行，因此总是只能利用堆的一半。相对而言，GC 标记 - 清除算法和引用计数法就能利用整个堆。

堆使用效率和吞吐量，以及最大暂停时间不可兼得。

可用的堆越大，GC 运行越快；相反，越想有效地利用有限的堆，GC 花费的时间就越长。

访问局部性

PC 上有 4 种存储器，分别是寄存器、缓存、内存、辅助存储器。

GC_Storage

一般我们会把所有的数据都放在内存里，当 CPU 访问数据时，仅把要使用的数据从内存读取到缓存。与此同时，我们还将它附近的所有数据都读取到缓存中， 从而压缩读取数据所需要的时间。

具有引用关系的对象之间通常很可能存在连续访问的情况。这在多数程序中都很常见，称为 “访问的局部性”。考虑到访问的局部性，把具有引用关系的对象安排在堆中较近的位置，就能提高在缓存中读取到想利用的数据的概率，令 mutator 高速运行。

参考资料