总体来说，Compacting GC和Mark-Sweep GC各有优劣。所谓Compacting GC，就是在进行GC的时候，同时对堆空间进行压缩，以消除碎片，因此它的堆空间利用率就更高。但是也正因为要对堆空间进行压缩，导致Compacting GC的GC效率不如Mark-Sweep GC。不过，只要我们使用得到恰当，是能够同时发挥Compacting GC和Mark-Sweep GC的长处的。例如，当Android应用程序被激活在前台运行时，就使用Mark-Sweep GC，而当Android应用程序回退到后台运行时，就使用Compacting GC。

为了达到上述目的，ART运行时内部有Foreground和Background两种GC之分。在ART运行时启动的时候，可以通过-Xgc和-XX:BackgroundGC来指定Foreground GC和Background GC的类型，即具体是哪一种Mark-Sweep GC或者Compacting GC。由于Mark-Sweep GC和Compacting GC所需要的堆空间结构是不一样的，因此，当发生Foreground GC和Background GC切换时，ART运行时需要提供支持，以维护堆空间的正确性。

除了适合后台运行时之外，Compacting GC还适合用在内存分配时。在以往的Mark-Sweep GC时，由于碎片而产生的内存不足问题，是解决不了的，只能让应用程序OOM。但是有了Compacting GC之后，就可以在应用程序OOM之前，再作一次努力，那就是对原来的堆空间进行压缩一下，再尝试进行分配，这样就可以提高成功分配内存的概率。

从上面的分析可以看出，Compacting GC的最大特点就是会对堆空间进行压缩。这意味着对象在堆空间的位置是会发生变化的。但是对应用程序来说，这种对象位置的变化是要透明的。因此，Compacting GC的最核心挑战就是在保持应用程序逻辑不变和正确的前提下，在需要的时候对对象的位置进行移动。所以在这篇文章里面，我们第一个要介绍的技术就是对象移动技术，接着再在此基础之上，展开对其它技术的介绍。

一个对象被移动了，要保持它的使用者的正确性，无非就是两种方案。

第一种方案是使用者不是直接引用对象，而是间接引用。这就类似于操作系统里面的文件描述符（fd）。我们在调用操作系统接口open打开一个文件的时候，获得的是一个整型的文件描述符。这个文件描述符其实就是一个索引，它索引到内核为每一个进程都创建的一个打开文件表。这个打开文件表里面的每一个项保存的都是一个指向一个打开文件结构体的指针。我们可以把这个打文件结构体看作就一个对象。当这个对象移动时，也就是在另外一个地方重新分配时，只需要将新分配得到的地址重新填入对应的打开文件表的表项就可以了。这对应用程序来说，是完全透明的，因为它是通过打开文件表来间接访问得到对应的打开文件结构体的。

我们可以轻易看出，上述方案的最大缺点就是每次访问对象都需要有额外的开销，也就是影响效率。但是如果我们可以忽略在执行Compacting GC时的这个开销，是不是就可以使用了呢？答案是否定的。由于Foreground和Background两种GC的同时存在，ART内部可能同时存在着Mark-Sweep和Compacting两种类型的GC。如果我们在Compacting GC中使用了该方案，那么也意味着Mark-Sweep GC也必须是要间接地去访问对象。但是这完全是没有必要的，因此ART使用的是第二种对象移动技术，也就是修改对象使用者的引用，使得它无论何时何地，总是直接指向对象的真实地址。

在ART运行时中，对象使用者无非就是位于两个位置，一个是堆，一个栈。因此，当一个对象被移动时，我们只需要找到它在堆和栈上的使用者的位置，那就可以将它们的值修改为对象被移动后的新地址，那就达到目的了。这个对象移动及其使用者引用者修改的过程示意图如图1所示：

图1 ART运行时Compacting GC对象移动技术

在图1中，被移动的对象是Object-1，它从Source Space移动到Destination Space，并且同时被堆上的对象Object-2和堆上的一个slot引用。这里我们需要解决两个问题。第一个问题是上面提到的，我们要修改Object-2中对Object-1的引用，实际上就是某一个成员变量的值，以及栈上显示的slot位置。第二个问题是要保证Object-1只被移动一次，也就是Object-2中对Object-1的引用和栈上的slot位置指向的是同一个地方。

这是如何实现的呢？我们需要先看一下Object类的定义。这个Object类是ART运行时里面的所有对象的基类，它有一个monitor_成员变量，如下所示：

这个类定义在文件art/runtime/mirror/object.h。

这个32位的monitor_成员变量的责任重大，除了用来描述对象的Monitor和Hash Code信息之外，还包括对象的移动信息。这个monitor_成员变量通过封装成一个LockWord对象来描述，如下所示：

这个类定义在文件art/runtime/lock_word.h中。

通过这个LockWord类的定义我们就可以知道，Object对象的成员变量monitor_的高2位描述的是状态，包括kUnlocked、kThinLocked、kFatLocked、kHashCode和kForwardingAddress五种状态。处于不同状态时，低30位有不同的描述，这里我们只关心kForwardingAddress这种状态。

当一个对象处于kForwardingAddress状态时，即它的成员变量monitor_的高2位值等于0x11时，表示它已经被移动过了，这时候它的位30位描述的就是对象移动后的新地址。有同学可能会说，30位够表示一个对象的地址吗？因为32位的体系架构中，内存的地址是32位的啊。答案是够的，回忆前面ART运行时垃圾收集机制简要介绍和学习计划这个系列的文章，对象的分配都是8字节对齐的，这意味着低3位都是0，因此这里用30位来描述对象的地址是足够的。

有了这个背景知识后，我们来回过头来看图1。我们首先需要明确，对象移动是发生在GC的过程中的，并且只有可达对象才需要移动，而可达对象都是从根集对象开始遍历的。我们假设Object-1是根集对象，并且是被栈上的slot引用。因此，当遍历到栈上的slot时，需要移动对象Object-1。这时候除了要将栈上的slot位置修改为Object-1在Destination Space上的位置之外，还需要将旧的Object-1（位于Source Space上）的成员变量monitor_的高2位设置为0x11，以及将低30位设置为新的Object-1（位于Destination Space上）的地址。

我们再假设Object-2是一个可达对象，也就是说在栈上的slot被遍历之后的某一个时候，Object-2也会被遍历。在遍历Object-2的时候，我们会检查它的每一个引用类型的成员变量。当检查到其引用了Object-1的成员变量的时候，会发现它Object-1（位于Source Space上）的成员变量monitor_的高2位已经被设置为kForwardingAddress状态，因此就直接将其低30位的值取出来，并且设置为Object-2对应的成员变量的值。这样就可以保证Object-2和栈上的slot位置引用的都是新的Object-1了。

以此类推，不管还有多少个可达对象引用了Object-1，按照上面的算法，都能保证它们能够正确地引用移动后的Object-1。

接下来我们就以Semi-Space GC标记对象的过程来说明上述的对象移动过程。Semi-Space GC的执行过程我们在后面的文章中再详细分析，这里主要关注对象的移动过程。首先栈上的根集对象的移动过程，如下所示：