Bog GC 设计 -- 概念篇

Bog 是一款基于 Zig 开发的小型脚本语言。它的 GC 设计受到一篇论文An efficient of Non-Moving GC for Function languages的启发。

梗概

1. 概述
   • Heap 的设计
   • GC 的类别
   • Bitmap 的设计
2. 实现

概述

GC 是一种垃圾回收的机制，主要是针对heap区域的内存管理策略。在堆中的内存分配是按照指数级增长的大小进行的，此外还有一个专门用于非常大对象的特殊子堆。这种方法的一个优点可能是它可以高效地处理各种大小的内存请求。

以公式来进行表示:

$$ Heap = (M, S, (H_3, H_4, …, H_{12})) $$

其中:

1. M 是特殊的区域，用于存储大对象
2. S 是空闲区域
3. H 是子堆，用于存储小对象，$H_i$表示大小为$2^i$的子堆,每次新增都为之前的两倍

graph TD
  A[Heap]
  B[M]
  C[S]
  D[H:Sub Heap]

  A --> B
  A --> C
  A --> D
  D --> H3
  D --> H4
  D --> H5
  D --> Hi

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

+------------+
|  Container |
|  +------+  |
|  |Box 1|  |
|  +------+  |
|  +------+  |
|  |Box 2|  |
|  +------+  |
|  +------+  |
|  |Box 3|  |
|  +------+  |
+------------+

内存子堆池

我们设计一个内存的资源池。这个池由许多固定大小的分配段组成。这意味着，无论子堆请求多少空间，它都会以这些固定大小的“段”为单位来请求。例如，如果池中的分配段大小为 1MB，那么一个子堆可能会请求 1MB、2MB、3MB 等大小的空间，而不是请求 1.5MB 或 2.5MB 这样的非整数倍的大小。

而子堆从一个由固定大小的段组成的资源池中动态分配和回收空间，这种策略可以提供更高的灵活性，并可能提高内存使用的效率。

GC 的类别

常见的 GC 有很多类型。

以位图记录数据来说，有“代际垃圾收集 GC”。在代际垃圾收集（Generational Garbage Collection）中，“代"或"世代"并不是指位图。它们实际上是指内存中的一部分，用于存储对象。基于对象的生存周期，GC 把它们分为不同的代。这种策略背后的基本思想是，新创建的对象很快就会变为垃圾，而旧对象则可能存活得更久。

一般来说，在代际 GC 中，有两个主要的代：

1. 新生代（Young Generation）：新创建的对象首先被放置在这里。新生代空间通常较小，并且经常进行垃圾收集。

2. 老年代（Old or Tenured Generation）：当对象在新生代中存活了足够长的时间并经历了多次垃圾收集后，它们会被移动到老年代。老年代空间通常比新生代大，并且垃圾收集的频率较低，因为预期老年代中的对象会有更长的生命周期。

位图在这里是一个工具，用于跟踪和管理每一代中哪些对象是活跃的（即仍在使用中）和哪些是垃圾。当算法扩展为代际 GC 时，可以为同一个堆空间的不同代维护多个位图。这样，每个代的活动和非活动对象都可以被单独地跟踪。

“为新生代维护一个位图，为老年代维护另一个位图”。这使得在进行垃圾收集时，我们可以单独地考虑每一个代，从而优化垃圾收集的效率和性能。

以是否移动旧有的数据来说，有“移动 GC”和“非移动 GC”。移动 GC 会将存活的对象移动到新的内存地址、压缩内存，而非移动 GC 则不会移动存活的对象，可以无缝由其他语言来调用内存里的数据。

在这种移动 GC 中，有“分代复制收集器”和“Cheney 复制收集器”。

分代复制收集器(Generational Copying Collector): 是垃圾收集的一种常见方法，特别是在函数式编程语言中。它假设新创建的对象很快就会变得不可达（即“死亡”），而老的对象则更可能持续存在。因此，内存被分成两个或更多的“代”，新对象在“新生代”中创建，当它们存活足够长的时间时，它们会被移到“老生代”。

Cheney 的拷贝收集器: 是一种用于半区（semi-space）的拷贝垃圾收集器。它的工作原理是将可用内存分为两半，并且只在其中一半中分配对象。当这一半用完时，收集器通过拷贝活跃对象到另一半空间来进行垃圾收集。然后，原先的那一半空间就完全清空，成为新的可用空间。Cheney 的收集器特别适用于处理短生命周期的数据，因为它可以快速地只拷贝活跃的数据，而忽略死亡的数据。这使得它在处理大量短生命周期数据的程序（例如函数式程序）时，对于其“次要收集”（minor collection，即仅仅回收新生代数据的收集）非常高效。这种方法的优势在于它可以有效地处理内存碎片，因为通过复制活动对象到新位置，内存会被连续地占用。

特点:

• 任何精确的 copy gc 都需要 runtime 系统定位和更新每个堆分配数据的所有指针
• 在传统的垃圾收集策略（移动 GC）中，压缩是一种常用的技术，它会将活跃的对象移到内存的一个连续区域中，从而释放出未使用的内存。换言之，就是整理内存碎片。

在非移动 GC 中，有“标记-清除”。

不需要进行压缩和对象移动这一特性是非常重要，指针的值（即对象的内存地址）是固定的，也不需要花时间更新移动的地址。这使得非移动 GC 非常适合于需要与其他语言进行交互的语言，因为它们可以在不需要额外的工作的情况下访问内存中的对象。而且不需要移动对象的这一特性对于支持多原生线程也是有益的。在多线程环境中，如果对象在内存中的位置不断移动，那么线程之间的协调和同步将变得更加复杂。因此，避免对象移动可以简化多线程编程。

有益的原因如下：

1. 锁的简化: 在一个多线程环境中，如果对象需要移动（例如，在垃圾收集的压缩阶段），那么我们需要确保其他线程在对象移动时不能访问这个对象。这可能需要使用复杂的锁策略和同步机制。但是，如果对象永远不移动，我们就可以减少这种同步的需求，使得锁策略更简单。

2. 指针的稳定性: 在多线程程序中，线程之间可能会共享指向对象的指针或引用。如果对象在内存中移动了，那么所有共享该对象的线程都需要更新其指针或引用。这不仅会增加同步的复杂性，而且可能会引入错误，如野指针。如果对象不移动，这些指针就会始终有效。

3. 预测性和性能: 不需要移动对象意味着内存访问模式更加稳定和可预测。在多线程程序中，预测性是一个宝贵的特性，因为它可以减少线程之间的争用，从而提高程序的整体性能。

4. 减少暂停时间: 垃圾收集中的对象移动可能导致应用程序的明显暂停，因为必须暂停所有线程来安全地进行移动。在多线程环境中，这种暂停可能更加明显，因为有更多的线程可能正在活跃地使用对象。不移动对象可以减少这种暂停。

5. 与其他语言或系统的互操作: 如果您的多线程应用程序与其他语言（如 C 或 C++）或系统进行互操作，那么对象的稳定位置将更加重要，因为外部代码可能依赖于对象不移动的事实。

但同样的，非移动 GC 也有缺点：

1. 内存碎片: 由于对象不会移动，因此内存中的空间可能会变得不连续。这可能会导致内存碎片，从而降低内存使用效率。
2. 内存分配: 由于内存碎片，内存分配可能会变得更加复杂。例如，如果没有足够的连续空间来满足分配请求，那么分配器可能需要进行更多的工作来查找可用的空间。这可能会导致分配的性能下降。
3. 内存使用: 由于内存碎片，内存使用可能会变得更加低效。例如，如果有一个大对象，但是没有足够的连续空间来存储它，那么它可能会被分成多个碎片，这些碎片可能会被分配给不同的连续空间。这可能会导致内存使用率降低。
4. 内存占用: 由于内存碎片，内存占用可能会变得更加低效。例如，如果有一个大对象，但是没有足够的连续空间来存储它，那么它可能会被分成多个碎片，这些碎片可能会被分配给不同的连续空间。这可能会导致内存使用率降低。

为了解决这些问题需要很多复杂的步骤，在此不多赘述。单以 Bog 的 GC 来讲解。

Meta Bitmap

“元级位图”或“meta-level bitmaps”。这是一个更高级别的位图，用于汇总原始位图的内容。这种层次化的结构类似于文件系统中的 inode 映射或多级页表在计算机内存管理中的使用。

例如，考虑一个简单的位图：1100 1100。一个元级位图可能表示每 4 位中有多少个空闲块。在这种情况下，元级位图可能是 1021（表示第一个 4 位中有 1 个空闲块，第二个 4 位中有 2 个空闲块，以此类推）。

系统不仅仅是盲目地从位图的开始处查找空闲位，而是记住上一次查找到的位置。这样，下次查找可以从这个位置开始，进一步加速查找过程。这意味着无论内存大小如何，找到下一个空闲位所需的时间都大致相同，这是一个非常高效的性能特性。

如果是最坏的情况呢？

以 32 位架构来设计。32 位架构意味着计算机的指令集和数据路径设计为处理 32 位宽的数据单元。因此，当操作 32 位数据单元（例如一个整数或位图的一部分）时，这样的架构通常可以一次性处理所有 32 位。这导致以 32 为底的对数操作，因为对于较大的数据段（如一个位图），操作可能需要按 32 位的块/段进行。查找时间与 segmentSize 的大小成对数关系。

例如，如果一个位图有 320 位，那么在 32 位架构上，最坏的情况可能需要检查 10 个 32 位块才能找到一个空闲位。这可以通过 $\log_{32}(320)$来表示，结果是 10。

Bitmap

由于 Bog 的 GC 本质上还是采用了“标记-清除”，所以利用位图来记录数据是必不可少的。在 Bog 中，我们采用了“位图记录数据”的方式来进行 GC。而为了提高效率，我们增加了元位图的概念，即每 4 个元素对应一个元位图，用于记录多空间的占用状态，并且根据 heap 的对象时间增加深度。

实现

实际上，在 Bog 的设计中，要更加复杂一些。我们增加了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

const Page = struct {
    const max_size = 1_048_576;
    comptime {
        // 2^20, 1MiB
        assert(@sizeOf(Page) == max_size);
    }
    const val_count = @divFloor(max_size - @sizeOf(u32) * 2, (@sizeOf(Value) + @sizeOf(State)));
    const pad_size = max_size - @sizeOf(u32) * 2 - (@sizeOf(Value) + @sizeOf(State)) * val_count;
    ...
}

1. max_size: 表示一个 Page 能够存储的最大字节数。我们定义了一个常量来表示 1 MiB 的大小，并在编译时确保 Page 类型的大小恰好为 1 MiB。否则将会触发编译时错误。
2. val_count: 表示一个 Page 能够存储的 Value 对象的数量
3. pad_size: 表示在存储了最大数量的 Value 对象后，Page 剩余的未使用的空间大小

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

    const State = enum {
        empty,
        white,
        gray,
        black,
    };
    const List = std.ArrayListUnmanaged(*Page);
    meta: [val_count]State,
    __padding: [pad_size]u8,
    free: u32,
    marked: u32,
    values: [val_count]Value,

1. 定义了一个名为 State 的枚举类型，它有四个可能的值：empty、white、gray 和 black。
   • 在垃圾收集（GC）的上下文中，这些状态通常与对象在 GC 过程中的状态有关。例如，在分代垃圾收集中，对象可能会被标记为 “white”（未访问/待处理），“gray”（已访问但其引用尚未处理）或 “black”（已处理）。
2. List: 存储 Page 类型的指针
3. meta: 表示一个 Page 中每个 Value 对象的状态。这里我们使用了一个枚举类型来表示状态，因为状态只有 4 种，所以可以用 2 位来表示。因此，我们可以使用一个 u32 来表示一个 Page 中所有 Value 对象的状态。这样，我们就可以使用一个 u32 来表示一个 Page 中所有 Value 对象的状态。每一个 State 可能对应一个在 values 字段中的 Value 对象的状态。
4. __padding 的字段，用于填充额外的内存空间。它的大小由之前提到的 pad_size 决定，且是一个字节（u8）数组。这通常用于确保数据结构的内存对齐。
5. free: 表示空闲或可用的空间数量、索引或其他与内存管理相关的信息
6. marked: 表示已标记的空间数量、索引或其他与内存管理相关的信息,在垃圾收集的过程中用于检测是否应继续在此页面中检查值
7. values: 表示一个 Page 中的 Value 对象。它是一个 Value 对象的数组，其大小由 val_count 决定。

• ←上一页
• 下一页→