共计 5302 个字符，预计需要花费 14 分钟才能阅读完成。
家喻户晓，内存是操作系统的一项重要资源，间接影响零碎性能。而在利用蓬勃发展的明天，零碎中运行的利用越来越多，这让内存资源变得越来越缓和。在此背景下，方舟 JS 运行时在内存回收方面发力，推出了高性能内存回收技术——HPP GC（High Performance Partial Garbage Collection）。本文咱们将从 GC 的根底动手，由浅入深地为大家介绍 HPP GC。
一、什么是 GC？
GC（全称 Garbage Collection），字面意思是垃圾回收。在计算机领域，GC 就是找到内存中的垃圾，开释和回收内存空间。目前支流编程语言实现的 GC 算法次要分为两大类：援用计数和对象追踪（即 Tracing GC）。
1. 援用计数
咱们通过一个示例来理解什么是援用计数：
当一个对象 A 被另一个对象 B 指向时，A 援用计数 +1；反之当该指向断开时，A 援用计数 -1。当 A 援用计数为 0 时，回收对象 A。
● 长处：
援用计数算法设计简略，并且内存回收及时，在对象成为垃圾的第一工夫就会被回收，所以没有独自的暂停业务代码 (Stop The World，STW) 阶段。
● 毛病：
在对对象操作的过程中额定插入了计数环节，减少了内存调配和内存赋值的开销，对程序性能必然会有影响。最致命的一点是存在循环援用问题。
function main() {var parent = {};
var child = {};
parent.child = child;
child.parent = parent;
}
比方以上代码中，对象 parent 被另一个对象 child 持有，对象 parent 援用计数加 1，同时 child 也被 parent 持有，对象 child 援用计数也加 1，这就是循环援用。始终到 main 函数完结后，对象 parent 和 child 仍然无奈开释，导致内存透露。
2. 对象追踪
为了不便大家了解对象追踪算法，咱们通过一个图来进行介绍：
如图 1 所示，从根对象开始遍历对象以及对象的域，所有可达的对象打上标记（彩色），即为活对象，剩下的不可达对象（红色）即为垃圾。
图 1 对象追踪● 长处：
对象追踪算法能够解决循环援用的问题，且对内存的调配和赋值没有额定的开销。
● 毛病：
和援用计数算法相同，对象追踪算法较为简单，且有短暂的 STW 阶段。此外，回收会有提早，导致比拟多的浮动垃圾。
援用计数和对象追踪算法各有优劣，但思考到援用计数存在循环援用的致命性能问题，方舟 JS 运行时抉择基于对象追踪（即 Tracing GC）算法来设计本人的 GC 算法。
二、Tracing GC 介绍
在介绍 HPP GC 之前，咱们先来理解一下 Tracing GC。从后面的介绍可知，Tracing GC 算法通过遍历对象图标记出垃圾。而依据垃圾回收形式的不同，Tracing GC 能够分为三种根本类型：标记 - 打扫回收、标记 - 复制回收、标记 - 整顿回收。
1. 标记 - 打扫回收
此算法的回收形式是：实现对象图遍历后，将不可达对象内容擦除，并放入一个闲暇队列，用于下次对象的再调配。
该种回收形式不须要搬移对象，所以回收效率十分高。但因为回收的对象内存地址不肯定间断，所以该回收形式最大的毛病是会导致内存空间碎片化，升高内存调配效率，极其状况下甚至会呈现还有大量内存的状况下调配不出一个比拟大的对象的状况。
图 2 标记 - 打扫回收（注：灰色块示意可达对象的内存空间，红色块示意不可达对象的内存空间。）
2. 标记 - 复制回收
此算法的回收形式是：在对象图的遍历过程中，将找到的可达对象间接复制到一个全新的内存空间中。遍历实现后，一次将旧的内存空间全副回收。
显然，这种形式能够解决内存碎片的问题，且通过一次遍历便实现整个 GC 过程，效率较高。但同时在极其状况下，这种回收形式须要预留一半的内存空间，以确保所有活的对象能被拷贝，空间利用率较低。
图 3 标记 - 复制回收3. 标记 - 整顿回收
此算法的回收形式是：实现对象图遍历后，将可达对象（红色）往本区域（或指定区域）的头部闲暇地位复制，而后将曾经实现复制的对象回收整顿到闲暇队列中。
这种回收形式既解决了“标记 - 打扫回收”引入的大量内存空间碎片的问题，又不须要像“标记 - 复制回收”那样节约一半的内存空间，然而性能上开销比“标记 - 复制回收”稍大一些。
图 4 标记 - 整顿回收综上所述，Tracing GC 的三种根本类型各有优缺点，那么方舟 JS 运行时的 HPP GC 是基于哪种类型实现的呢？
HPP GC 同时实现了这三种 Tracing GC 算法！没想到吧？HPP GC 综合了这三种算法的长处，且反对依据不同对象区域、采取不同的回收形式。上面就为大家具体解析 HPP GC。
三、HPP GC 详解
后面咱们提到了，HPP GC 反对依据不同对象区域，采取不同的回收形式。这是基于分代模型和混合算法来实现的。另外，为了实现 HPP GC（High Performance Partial Garbage Collection）中的“High Performance”（高性能），HPP GC 对 GC 流程做了大量优化。所以上面咱们就从分代模型、混合算法和 GC 流程优化三个方面来为大家介绍 HPP GC。
1. 分代模型
方舟 JS 运行时采纳传统的分代模型，将对象进行分类。思考到大多数新调配的对象都会在一次 GC 之后被回收，而大多数通过屡次 GC 之后仍然存活的对象会持续存活，方舟 JS 运行时将对象划分为年老代对象和老年代对象，并将对象调配到不同的空间。
如图 5 所示，方舟 JS 运行时将新调配的对象间接调配到年老代（Young Generation）的 From 空间。通过一次 GC 后仍然存活的对象，会进入 To 空间。而通过再次 GC 后仍然存活的对象，会被复制到老年代（Old Generation）。
图 5 分代模型-
混合算法
通过后面的介绍，咱们曾经晓得：HPP GC 同时实现了“标记 - 打扫回收”、“标记 - 复制回收”和“标记 - 整顿回收”这三种 Tracing GC 算法。也就是说，HPP GC 是一种“局部复制 + 局部整顿 + 局部打扫”的混合算法，反对依据年老代对象和老年代对象的不同特点，别离采取不同的回收形式。
(1) 局部复制
思考到年老代对象生命周期较短，回收较为频繁，且年老代对象大小无限的特点，方舟 JS 运行时对年老代对象采纳“标记 - 复制回收”算法。
(2) 局部整顿 + 局部打扫
方舟 JS 运行时依据老年代对象的特点，引入启发式 Collection Set（简称 CSet）抉择算法。此抉择算法的基本原理是：在标记阶段对每个区域的存活对象进行大小统计，而后在回收阶段优先选出存活对象少、回收代价小的区域进行对象整顿回收，再对剩下的区域进行打扫回收。
具体的回收策略如下：
(a) 依据设定的区域存活对象大小阈值，将满足条件的区域纳入初步的 CSet 队列，并依据存活率进行从低到高的排序。
（注：存活率 = 存活对象大小 / 区域大小）
(b) 依据设定的开释区域个数阈值，选出最终的 CSet 队列，进行整顿回收。
(c) 对未被选入 CSet 队列的区域进行打扫回收。
由上可知，启发式 CSet 抉择算法同时兼顾了“标记 - 整顿回收”和“标记 - 打扫回收”这两种算法的长处，既防止了内存碎片问题，也兼顾了性能。
3. GC 流程优化
在内存回收时，尽管开释和回收了内存空间，让零碎有了更多可用的内存资源，但内存回收过程自身须要暂停利用业务代码执行，影响用户应用利用的体验。回收内存时，如何尽可能的减小对利用性能的影响呢？
为此，咱们在 HPP GC 流程中引入了大量的并发和并行优化，以缩小对利用性能的影响。如图 6 所示，HPP GC 流程中采纳了并发 + 并行标记（Marking）、并发 + 并行打扫（Sweep）、并行复制 / 整顿（Evacuation）、并行回改（Update）和并发清理（Clear）。图 6 HPP GC 流程(1) 并发 + 并行标记
在 JS 线程执行业务代码的同时，另外启动线程执行标记，即为“并发标记”。如果另外启动多个线程执行标记，即为“并发 + 并行标记”。
在并发 + 并行标记过程中，为确保标记的正确性和高性能，HPP GC 采取了两项优化措施：
措施一：在新增援用关系时减少标记屏障 (Marking Barrier)，以确保标记后果的正确性。
并发标记过程中，JS 线程有可能会更改对象之间的援用关系，从而导致对象标记后果出错。如图 7 所示，在 marking 线程实现对象 1 的标记、筹备标记对象 2 的过程中，JS 线程更改了对象 3 的援用关系。那么 marking 线程实现对象 2 的标记后，对象 3 不会被标记，回收器会断定对象 3 为垃圾，进行回收。尔后，如果 JS 线程读取对象 1 的字段，将会产生不可预知的谬误。图 7 对象标记出错为确保标记后果的正确性，HPP GC 在新增援用关系时减少标记屏障。如图 8 所示，在 marking 线程实现对象 1 的标记、筹备标记对象 2 的过程中，JS 线程更改了对象 3 的援用关系。此时，JS 线程会将对象 3 退出期待标记队列，等 marking 线程实现对象 2 的标记后，持续对象 3 的标记，从而确保对象 3 不会被回收。
图 8 减少标记屏障措施二：在共享全局工作队列的根底上，减少了本地工作队列 (Local Work List)，以进步读取对象的性能。
如图 9 所示，并行标记时，每个 Marking 线程都要执行以下操作：从全局工作队列 (Global Work List) 获取一个对象，而后设置标记位，最初遍历该对象的每个域，将子对象放入全局工作队列中。思考到线程之间读取数据平安，必须在每个对象的 Push/Pop 操作时减少原子化或者锁，这对对象的读取性能有较大的影响。图 9 全局工作队列为进步读取对象的性能，HPP GC 减少了本地工作队列。每个线程持有一个独立的本地工作队列，优先从本地工作队列获取 / 放入对象。当本地工作队列满时，将本地工作队列的局部队列一次公布到全局工作队列中；当本地工作队列空时，一次从全局工作队列获取若干对象到本地工作队列。这样，只有从全局工作队列公布 / 获取对象那一次须要减少原子化或者锁，兼顾了多线程的并发效率和工作平衡，大大提高了并发标记的效率。
图 10 减少本地工作队列(2) 并发 + 并行打扫
在 JS 线程执行业务代码的同时，另外启动线程执行打扫，即为“并发打扫”。如果另外启动多个线程执行打扫，即为“并发 + 并行打扫”。
在并发 + 并行打扫过程中，HPP GC 采取减少区域闲暇队列 (Region Free List) 的优化措施，用于进步多线程并发打扫的效率。
并发 + 并行打扫过程中，Sweeping 线程发现不可达对象后，须要将对象放入全局的闲暇队列，同时 JS 线程执行的业务代码可能须要从闲暇队列调配对象。为了确保数据安全，这个过程须要减少原子化或者锁，但会影响到调配和打扫的效率。
为了晋升效率，HPP GC 减少区域闲暇队列。将所有须要打扫的内存按内存地址分成若干个区域，每个区域领有独立的闲暇队列，且每个区域同时只有一个线程进行打扫。在并发打扫过程中，Sweeping 线程会首先将不可达对象放入本区域的闲暇队列。当 JS 线程须要从闲暇队列调配对象时，先获取曾经实现打扫的区域，再将这些区域的闲暇队列公布到全局闲暇队列中，用于对象调配，如图 11 所示。因为公布的工作由 JS 线程独自实现，所以整个并行打扫的过程都不须要加锁，大大提高了并发 + 并行打扫的效率。图 11 减少区域闲暇队列(3) 并行复制 / 整顿
在 JS 线程暂停业务代码 (STW) 对可达对象进行复制 / 整顿时，另外启动多个线程一起进行复制 / 整顿，即为“并行复制 / 整顿”。
和并发 + 并行打扫类似，并行复制 / 整顿的瓶颈点在于多个线程同时从全局闲暇队列 / 全局线性分配器调配对象时，须要减少原子化或者锁。为了进步多线程调配性能，在并行复制 / 整顿过程中引入了 TLAB Allocator。
TLAB 英文全称为 Thread Local Allocation Buffer。顾名思义，TLAB Allocator 就是每个线程领有一个独立的本地分配器，该分配器会从全局内存分配器一次调配一块较大的内存，而后在线程外部再调配。这样只需从全局分配器调配时保障多线程平安，即可实现高性能且平安的并行复制 / 整顿性能。
(4) 并行回改
在 GC 实现标记和复制 / 整顿后，须要将可达对象中指向旧对象地址的域改成新对象地址，这个过程就是“地址回改”，如图 12 所示。为了晋升地址回改的效率，HPP GC 引入了“并行回改”，同时启动多个线程进行地址回改，每个线程负责其中一块内存区域对象地址的回改。图 12 地址回改(5) 并发清理
在 GC 复制 / 整顿完结后，JS 线程将不再读写遍历进去的不可达对象和曾经实现复制的可达对象，因而须要清理和回收对应的物理内存。为了缩小 STW 工夫，HPP GC 引入“并发清理”，另外启动一个工作线程进行并发的物理内存回收，这样 JS 线程就能够继续执行业务代码。四、结束语
本期就为大家介绍到这里了，最初咱们总结一下：
● HPP GC 基于分代模型将对象分为年老代和老年代对象。
● HPP GC 基于 Tracing GC 的三种根本类型，实现了“局部复制 + 局部整顿 + 局部打扫”的混合算法，从而实现依据不同对象区域、采取不同的回收形式。
● HPP GC 通过在 GC 流程中引入了大量的并发和并行优化，实现高性能。
HPP GC 仍有很大的摸索空间，咱们还将持续致力，为大家提供更高性能的内存回收能力！