解密方舟的高性能内存回收技术——HPP GC

众所周知，内存是操作系统的一项重要资源，直接影响系统性能。而在应用蓬勃发展的今天，系统中运行的应用越来越多，这让内存资源变得越来越紧张。在此背景下，方舟JS运行时在内存回收方面发力，推出了高性能内存回收技术——HPP GC（High Performance Partial Garbage Collection 。本文我们将从GC的基础入手，由浅入深地为大家介绍HPP GC。

GC（全称Garbage Collection ，字面意思是垃圾回收。在计算机领域，GC就是找到内存中的垃圾，释放和回收内存空间。目前主流编程语言实现的GC算法主要分为两大类 引用计数和对象追踪（即Tracing GC 。

1. 引用计数

当一个对象A被另一个对象B指向时，A引用计数+1；反之当该指向断开时，A引用计数-1。当A引用计数为0时，回收对象A。

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 对象追踪

引用计数和对象追踪算法各有优劣，但考虑到引用计数存在循环引用的致命性能问题，方舟JS运行时选择基于对象追踪（即Tracing GC 算法来设计自己的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（High Performance Partial Garbage Collection 中的“High Performance”（高性能 ，HPP GC对GC流程做了大量优化。所以下面我们就从分代模型、混合算法和GC流程优化三个方面来为大家介绍HPP GC。

1. 分代模型

如图5所示，方舟JS运行时将新分配的对象直接分配到年轻代（Young Generation 的From空间。经过一次GC后依然存活的对象，会进入To空间。而经过再次GC后依然存活的对象，会被复制到老年代（Old Generation 。

图5 分代模型

2. 混合算法

(1) 部分复制

(2) 部分整理+部分清扫

具体的回收策略如下

由上可知，启发式CSet选择算法同时兼顾了 “标记-整理回收”和“标记-清扫回收”这两种算法的优点，既避免了内存碎片问题，也兼顾了性能。

3. GC流程优化

为此，我们在HPP GC流程中引入了大量的并发和并行优化，以减少对应用性能的影响。如图6所示，HPP GC流程中采用了并发+并行标记（Marking 、并发+并行清扫（Sweep 、并行复制/整理（Evacuation 、并行回改（Update 和并发清理（Clear 。

图6 HPP GC流程

(1) 并发+并行标记

措施一 在新增引用关系时增加标记屏障(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) 并发+并行清扫

在并发+并行清扫过程中，HPP GC采取增加区域空闲队列(Region Free List)的优化措施，用于提高多线程并发清扫的效率。

并发+并行清扫过程中，Sweeping线程发现不可达对象后，需要将对象放入全局的空闲队列，同时JS线程执行的业务代码可能需要从空闲队列分配对象。为了确保数据安全，这个过程需要增加原子化 者锁，但会影响到分配和清扫的效率。

为了提升效率，HPP GC增加区域空闲队列。将所有需要清扫的内存按内存地址分成若干个区域，每个区域拥有独立的空闲队列，且每个区域同时只有一个线程进行清扫。在并发清扫过程中，Sweeping线程会首先将不可达对象放入本区域的空闲队列。当JS线程需要从空闲队列分配对象时，先获取已经完成清扫的区域，再将这些区域的空闲队列发布到全局空闲队列中，用于对象分配，如图11所示。由于发布的任务由JS线程单独完成，所以整个并行清扫的过程都不需要加锁，大大提高了并发+并行清扫的效率。

图11 增加区域空闲队列

(3) 并行复制/整理

(4) 并行回改

图12 地址回改

(5) 并发清理

HPP GC仍有很大的探索空间，我们还将继续努力，为大家提供更高性能的内存回收能力！

想了解更多HarmonyOS技术？