这篇文章主要介绍两种V8中使用到的垃圾回收的算法。

为什么需要垃圾回收机制呢？为何我们不自己手动释放内存，分配内存。如果写过C语言的程序，就会知道在内存管理上，程序语言进化的路线，我们在C++的析构函数中释放内存，或者在java中使用虚拟机管理内存，会明显感受到有垃圾回收机制，让开发效率大大提升，程序员可以集中精力在逻辑上。另外，一个大型系统的内存管理是一个非常复杂的问题，把内存管理交给仔细设计的垃圾回收器，往往比咱们自己手动管理更好。

基本概念

垃圾回收器要解决的最基本问题就是，辨别需要回收的内存。一旦辨别完毕，这些内存区域即可在未来的分配中重用，或者是返还给操作系统。一个对象当它不是处于活跃状态的时候它就可以被回收了。一个对象处于活跃状态是指当且仅当它被一个根对象或另一个活跃对象指向。根对象被定义为处于活跃状态，是浏览器或V8所引用的对象。比如说，被局部变量所指向的对象属于根对象，因为它们的栈被视为根对象；全局对象属于根对象，因为它们始终可被访问；浏览器对象，如DOM元素，也属于根对象，尽管在某些场合下它们只是弱引用。

从侧面来说，上面的定义非常宽松。实际上我们可以说，当一个对象可被程序引用时，它就是活跃的。
比如：

function f() {
    var obj = {
        x: 12
    };
    g(); // 可能包含一个死循环
    return obj.x;
}

译注：这里的obj.x和obj都是活跃的，尽管对其的再度引用是在死循环之后。
很遗憾，我们无法精确地解决这个问题，因为这个问题实际等价于停机问题，无法确定。因此我们做一个等价约定：如果一个对象可经由某个被定义为活跃对象的对象，通过某个指针链所访问，则它就是活跃的。其他的都被视为垃圾。

堆的构成

在我们深入研究垃圾回收器的内部工作原理之前，首先来看看堆是如何组织的。V8将堆分为了几个不同的区域：

• 新生区：大多数对象被分配在这里。新生区是一个很小的区域，垃圾回收在这个区域非常频繁，与其他区域相独立。
• 老生指针区：这里包含大多数可能存在指向其他对象的指针的对象。大多数在新生区存活一段时间之后的对象都会被挪到这里。
• 老生数据区：这里存放只包含原始数据的对象（这些对象没有指向其他对象的指针）。字符串、封箱的数字以及未封箱的双精度数字数组，在新生区存活一段时间后会被移动到这里。
• 大对象区：这里存放体积超越其他区大小的对象。每个对象有自己mmap
  产生的内存。垃圾回收器从不移动大对象。
• 代码区：代码对象，也就是包含JIT之后指令的对象，会被分配到这里。这是唯一拥有执行权限的内存区（不过如果代码对象因过大而放在大对象区，则该大对象所对应的内存也是可执行的。译注：但是大对象内存区本身不是可执行的内存区）。
• Cell区、属性Cell区、Map区：这些区域存放Cell、属性Cell和Map，每个区域因为都是存放相同大小的元素，因此内存结构很简单。

每个区域都由一组内存页构成。内存页是一块连续的内存，经mmap（或者Windows的什么等价物）由操作系统分配而来。除大对象区的内存页较大之外，每个区的内存页都是1MB大小，且按1MB内存对齐。除了存储对象，内存页还含有一个页头（包含一些元数据和标识信息）以及一个位图区（用以标记哪些对象是活跃的）。
有了这些背景知识，我们可以来深入垃圾回收器了。

识别指针

垃圾回收器面临的第一个问题是，如何才能在堆中区分指针和数据，因为指针指向着活跃的对象。大多数垃圾回收算法会将对象在内存中挪动（以便减少内存碎片，使内存紧凑），因此即使不区分指针和数据，我们也常常需要对指针进行改写。
目前主要有三种方法来识别指针：

• 保守法：这种方法对于缺少编译器支持的情况非常必要。大体上，我们将所有堆上对齐的字都认为是指针，这就意味着有些数据也会被误认为是指针。于是某些实际是数字的假指针，会被误认为指向活跃的对象，则我们会时常出现一些奇异的内存泄漏。（译注：因为垃圾回收器会以为死对象仍然还有指针指向，错将死对象误认为活跃对象）而且我们也不能移动任何内存区域，因为这很可能会导致数据遭到破坏。这样，我们便无法通过紧凑内存来获得任何好处（比如更容易的内存分配、更少的内存访问、更有效的内存局部性缓存）。C/C++的垃圾回收器扩展会采用这种方式，比如Boehm-Demers-Weiser。译注：如果内存是紧凑的，则内存分配时可以更容易分配较大片的内存，而无需因内存碎片而不断查找；同时，由于已分配的内存是连续或近似连续的，而Cahce所能缓存的内存有限，如果内存被Cache缓存起来，无需频繁地迫使Cache更换缓存的内存。C/C++由于指针算术的存在，编译器无法确定哪些内存是真正的垃圾，因而无法给垃圾回收器有效的提示，进而导致垃圾回收器不得不采取这样的保守策略。
• 编译器提示法：如果我们和静态语言打交道，则编译器能够准确地告诉我们每个类当中指针的具体位置。而一旦我们知道对象是哪个类实例化得到的，我们就能知道对象中所有的指针。JVM选择了这样的方法来进行垃圾回收。可惜，这种方法对于JS这样的动态语言来说不太好使，因为JS中对象的任何属性既可能是指针，也可能是数据。
• 标记指针法：这种方法需要在每个字的末位预留一位来标记这个字代表的是指针抑或数据。这种方法需要一定的编译器支持，但实现简单，而且性能不俗。V8采用的就是这种方法。某些静态语言也采用了这样的方法，如OCaml。

V8将所有属于-2^30…230-1范围内的小整数（V8内部称其为Smis）以32bit字宽来存储，其中的最低一位保持为0，而指针的最低两位则为01。由于对象以4字节对齐，因此这样表达指针没有任何问题。大多数对象所含有的只是一组标记后的字，因此垃圾回收可以进行的很快。而有些类型的对象，比如字符串，我们确定它只含有数据，因此无需标记。如果想仔细了解指针标记法，可以查看这篇文章Pointer-magic-for-efficient-dynamic-value-representations

分代回收

脚本中，绝大多数对象的生存期很短，只有某些对象的生存期较长。为利用这一特点，V8将堆进行了分代。对象起初会被分配在新生区（通常很小，只有1-8 MB，具体根据行为来进行启发）。在新生区的内存分配非常容易：我们只需保有一个指向内存区的指针，不断根据新对象的大小对其进行递增即可。当该指针达到了新生区的末尾，就会有一次清理（小周期），清理掉新生区中不活跃的死对象。对于活跃超过2个小周期的对象，则需将其移动至老生区。老生区在标记－清除或标记－紧缩（大周期）的过程中进行回收。大周期进行的并不频繁。一次大周期通常是在移动足够多的对象至老生区后才会发生。至于足够多到底是多少，则根据老生区自身的大小和程序的动向来定。
由于清理发生的很频繁，清理必须进行的非常快速。V8中的清理过程称为Scavenge算法，是按照Cheney的算法实现的。现在仔细看一下算法的实现。

这个算法我们需要弄清楚几个概念：

1. root：root表示可以被引用到的对象的根，我们总是从根部开始找活跃对象。

2. new space：本算法将内存分为两部分，老区和新区，老区放当前分配的对象，新区在老区满的时候，会用来把老区中活跃的对象迁移过来，一般来说，迁移过来的对象会在新区中更紧凑，也去掉了那些不活跃对象。最后，新区和老区会互换，可以在下图中明显看到这一点。

   
   
   stop and copy 算法

下面提供算法的伪代码。

1. scan pointer：扫描指针，指向当前被检查的对象
2. alloc pointer：分配指针，指向新区内存，用来存放被移动的而对象
3. forwarding pointer ： 转发指针，为啥要设置这个？并不是很清楚，将来看代码搞清楚在回来补充。可能是途中A->C->F的指针。。

    def scavenge():
      swap(fromSpace, toSpace)
      allocationPtr = toSpace.bottom
      scanPtr = toSpace.bottom

      for i = 0..len(roots):
        root = roots[i]
        if inFromSpace(root):
          rootCopy = copyObject(&allocationPtr, root)
          setForwardingAddress(root, rootCopy)
          roots[i] = rootCopy

      while scanPtr < allocationPtr:
        obj = object at scanPtr
        scanPtr += size(obj)
        n = sizeInWords(obj)
        for i = 0..n:
          if isPointer(obj[i]) and not inOldSpace(obj[i]):
            fromNeighbor = obj[i]
            if hasForwardingAddress(fromNeighbor):
              toNeighbor = getForwardingAddress(fromNeighbor)
            else:
              toNeighbor = copyObject(&allocationPtr, fromNeighbor)
              setForwardingAddress(fromNeighbor, toNeighbor)
            obj[i] = toNeighbor
 
    def copyObject(*allocationPtr, object):
      copy = *allocationPtr
      *allocationPtr += size(object)
      memcpy(copy, object, size(object))
      return copy

虽然伪代码中一些问题没有完全搞明白，但是算法的基本思想已经清楚。此算法号称是垃圾回收最快的算法，就是需要多余的空间。更具体的描述可以看文章参考中的链接。

秘密武器：写屏障

上面有一个细节被忽略了：如果新生区中某个对象，只有一个指向它的指针，而这个指针恰好是在老生区的对象当中，我们如何才能知道新生区中那个对象是活跃的呢？显然我们并不希望将老生区再遍历一次，因为老生区中的对象很多，这样做一次消耗太大。
为了解决这个问题，实际上在写缓冲区中有一个列表，列表中记录了所有老生区对象指向新生区的情况。新对象诞生的时候，并不会有指向它的指针，而当有老生区中的对象出现指向新生区对象的指针时，我们便记录下来这样的跨区指向。由于这种记录行为总是发生在写操作时，它被称为写屏障——因为每个写操作都要经历这样一关。
你可能好奇，如果每次进行写操作都要经过写屏障，岂不是会多出大量的代码么？没错，这就是我们这种垃圾回收机制的代价之一。但情况没你想象的那么严重，写操作毕竟比读操作要少。某些垃圾回收算法（不是V8的）会采用读屏障，而这需要硬件来辅助才能保证一个较低的消耗。V8也有一些优化来降低写屏障带来的消耗：

• 大多数的脚本执行时间都是发生在Crankshaft当中的，而Crankshaft常常能静态地判断出某个对象是否处于新生区。对于指向这些对象的写操作，可以无需写屏障。
  Crankshaft中新出现了一种优化，即在对象不存在指向它的非局部引用时，该对象会被分配在栈上。而一个栈上对象的相关写操作显然无需写屏障。（译注：新生区和老生区在堆上。）
• “老→新”这样的情况相对较为少见，因此通过将“新→新”和“老→老”两种常见情况的代码做优化，可以相对提升多数情形下的性能。每个页都以1MB对齐，因此给定一个对象的内存地址，通过将低20bit滤除来快速定位其所在的页；而页头有相关的标识来表明其属于新生区还是老生区，因此通过判断两个对象所属的区域，也可以快速确定是否是“老→新”。
• 一旦我们找到“老→新”的指针，我们就可以将其记录在写缓冲区的末端。经过一定的时间（写缓冲区满的时候），我们将其排序，合并相同的项目，然后再除去已经不符合“老→新”这一情形的指针。（译注：这样指针的数目就会减少，写屏障的时间相应也会缩短）

“标记－清除”算法与“标记－紧缩”算法

Scavenge算法对于快速回收、紧缩小片内存效果很好，但对于大片内存则消耗过大。因为Scavenge算法需要出区和入区两个区域，这对于小片内存尚可，而对于超过数MB的内存就开始变得不切实际了。老生区包含有上百MB的数据，对于这么大的区域，我们采取另外两种相互较为接近的算法：“标记－清除”算法与“标记－紧缩”算法。

这两种算法都包括两个阶段：标记阶段，清除或紧缩阶段。
当内存不足时，标记阶段找到所有有效的对象。在清楚阶段，收集垃圾对象。没法对象都有一个额外的位，在标记阶段，如果对象可达，设置为1.

mark and swap

我们看一下各个阶段发生的变化

mark and sweep

最后，我们看到的结果是free指向的链表增大了(图中红线)。

我们看一下算法的伪代码：
标记阶段：

标记阶段

清除阶段：

清除阶段

紧缩算法会尝试将对象从碎片页（包含大量小空闲内存的页）中迁移整合在一起，来释放内存。这些对象会被迁移到另外的页上，因此也可能会新分配一些页。而迁出后的碎片页就可以返还给操作系统了。迁移整合的过程非常复杂，因此我只提及一些细节而不全面讲解。大概过程是这样的。对目标碎片页中的每个活跃对象，在空闲内存链表中分配一块其它页的区域，将该对象复制至新页，并在碎片页中的该对象上写上转发地址。迁出过程中，对象中的旧地址会被记录下来，这样在迁出结束后V8会遍历它所记录的地址，将其更新为新的地址。由于标记过程中也记录了不同页之间的指针，此时也会更新这些指针的指向。注意，如果一个页非常“活跃”，比如其中有过多需要记录的指针，则地址记录会跳过它，等到下一轮垃圾回收再进行处理。

增量标记与惰性清理

你应该想到了，当一个堆很大而且有很多活跃对象时，标记-清除和标记-紧缩算法会执行的很慢。起初我研究V8时，垃圾回收所引发的500-1000毫秒的停顿并不少见。这种情况显然很难接受，即使是对于移动设备。
2012年年中，Google引入了两项改进来减少垃圾回收所引起的停顿，并且效果显著：增量标记和惰性清理。
增量标记允许堆的标记发生在几次5-10毫秒（移动设备）的小停顿中。增量标记在堆的大小达到一定的阈值时启用，启用之后每当一定量的内存分配后，脚本的执行就会停顿并进行一次增量标记。就像普通的标记一样，增量标记也是一个深度优先搜索，并同样采用白灰黑机制来分类对象。

但增量标记和普通标记不同的是，对象的图谱关系可能发生变化！我们需要特别注意的是，那些从黑对象指向白对象的新指针。回忆一下，黑对象表示其已完全被垃圾回收器扫描，并不会再进行二次扫描。因此如果有“黑→白”这样的指针出现，我们就有可能将那个白对象漏掉，错当死对象处理掉。（译注：标记过程结束后剩余的白对象都被认为是死对象。）于是我们不得不再度启用写屏障。现在写屏障不仅记录“老→新”指针，同时还要记录“黑→白”指针。一旦发现这样的指针，黑对象会被重新染色为灰对象，重新放回到双端队列中。当算法将该对象取出时，其包含的指针会被重新扫描，这样活跃的白对象就不会漏掉。

增量标记完成后，惰性清理就开始了。所有的对象已被处理，因此非死即活，堆上多少空间可以变为空闲已经成为定局。此时我们可以不急着释放那些空间，而将清理的过程延迟一下也并无大碍。因此无需一次清理所有的页，垃圾回收器会视需要逐一进行清理，直到所有的页都清理完毕。这时增量标记又蓄势待发了。
Google近期还新增了并行清理支持。由于脚本的执行线程不会再触及死对象，页的清理任务可以放在另一个单独的线程中进行并只需极少的同步工作。同样的支持工作也正在并行标记上开展着，但目前还处于早期试验阶段。

总结

垃圾回收真的很复杂。文章中已经略过了大量的细节，而文章仍然变得很长。我一个同事说他觉得研究垃圾回收器比寄存器分配还要可怕，我表示确实如此。也就是说，我宁可将这些繁琐的细节交给运行时来处理，也不想将其交给所有的应用开发者来做。尽管垃圾回收存在一些性能问题而且偶尔会出现灵异现象，它还是将我们从大量的细节中解放了出来，以便让我们集中精力于更重要的事情上。

如果你还想了解更多垃圾回收上的东西，我建议你读读Richard Jones和Rafael Lins写的《Garbage Collection》，这是一个绝好的参考，涵盖了大量你需要了解的内容。你可能还对《Garbage First Garbage-Collection》感兴趣，这是一篇描述JVM所使用的垃圾回收算法的论文。

本文抄录整理自以下资料:
v8-garbage-collection
Pointer-magic-for-efficient-dynamic-value-representations
a-tour-of-v8-garbage-collection
Stop And Copy - Garbage Collection - [Compilers Theory] By Alex Aiken