家喻户晓，内存是操作系统的一项重要资源，间接影响零碎性能。而在利用蓬勃发展的明天，零碎中运行的利用越来越多，这让内存资源变得越来越缓和。在此背景下，方舟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仍有很大的摸索空间，咱们还将持续致力，为大家提供更高性能的内存回收能力！
发表回复