V8垃圾回收机制简介

V8垃圾回收器的实现，是V8高效的一个非常重要的原因。

V8在运行时自动回收不再需要使用的对象内存，也即是垃圾回收。

V8使用了全暂停式（stop-the-world）、分代式（generational）、精确（accurate）等组合的垃圾回收机制，来确保更快的对象内存分配、更短的垃圾回收时触发的暂停以及没有内存碎片。

V8的垃圾回收有如下几个特点：

• 当处理一个垃圾回收周期时，暂停所有程序的执行。
• 在大多数垃圾回收周期，每次仅处理部分堆中的对象，使暂停程序所带来的影响降至最低。
• 准确知道在内存中所有的对象及指针，避免错误地把对象当成指针所带来的内存泄露。

在V8中，对象堆被分为两个部分：新创建的对象所在的新生代，以及在一个垃圾回收周期后存活的对象被提升到的老生代。如果一个对象在一个垃圾回收周期中被移动，那么V8将会更新所有指向此对象的指针。

V8垃圾回收机制深入剖析

如大多数动态类型语言一样，JavaScript使用垃圾回收机制来管理内存，然而ECMAScript没有任何操作垃圾回收的接口，所有的操作都有JavaScript引擎自动完成。这让开发者省却了手动管理内存分配所带来的各种棘手问题。

V8在实现JavaScript的垃圾回收机制时，使用了各种非常复杂的策略，保证了高效的内存使用及回收，这也是Node之所以选择V8作为JavaScript引擎的原因之一。如果V8仅会在浏览器中被使用，那么即使发生内存泄漏等各种内存问题也仅仅会影响到一个终端用户，而且考虑到V8引擎在浏览器中的生命周期不长，一旦页面被关闭后，内存即会被释放。但如果在服务器端使用V8（使用Node作为服务器环境），那么内存问题所造成的影响将会波及到大量终端用户，显然V8需要高效的内存管理机制。

V8会限制所使用的内存大小，原因一是最初V8是作为浏览器JavaScript引擎所设计的，二是V8的垃圾回收机制的限制，如果内存分配过大，那么垃圾回收周期也就越长，对程序造成的影响也就越大。V8的内存大小限制是可配置的。

V8的堆组成

V8的堆由一系列区域组成：

• 新生代区：大多数对象的创建被分配在这里，这个区域很小，但垃圾回收非常频繁，独立于其它区。
• 老生代指针区：包含大部分可能含有指向其它对象指针的对象。大多数从新生代晋升（存活一段时间）的对象会被移动到这里。
• 老生代数据区：包含原始数据对象（没有指针指向其它对象）。Strings、boxed numbers以及双精度unboxed数组从新生代中晋升后被移到这里。
• 大对象区：这里存放大小超过其它区的大对象。每个对象都有自己mmap内存。大对象不会被回收。
• 代码区：代码对象（即包含被JIT处理后的指令对象）存放在此。唯一的有执行权限的区域（代码过大也可能存放在大对象区，此时它们也可被执行，但不代表大对象区都有执行权限）。
• Cell区、属性Cell区以及map区：包含cell、属性cell以及map。每个区都存放他们指向的相同大小以及相同结构的对象。

每个区都由一系列的内存页（page）组成。内存页是一块联系的内存，使用操作系统的mmap（或Windows的等价物）分配。每个区的页的大小都是1MB，而且以1MB对齐，除了大对象区（那里可能更大）。除了存储对象，内存页还会包含一个头部信息（包括一些标志和元数据）以及一个记号位图（指明哪些对象是活着的）。每个页还有一个分配在单独内存中的槽缓冲区，放置一组对象，这些对象可能指向在当前页的其他对象。

识别指针

任何垃圾回收器首要解决的任务就是区分开出指针和数据。垃圾回收器需要循着指针来找到活着的对象。多数垃圾回收算法都会在内存中移动对象的位置（为了减少内存碎片以及使内存更紧凑），所以需要可以改写指针指向的位置并且不破坏旧的数据。

目前有三种主流的方法来识别指针：

• 保守法（Conservative）。可在没有编译器支持的情况下实现。基本上，将堆上所有对齐的字都认为是指针，这意味着一些数据也会被当成是指针。因此，当一个整数被当成指针时，可能导致原本应该被回收的内存被误认为还有指针（实际只是个整数）指向它而没有被回收，这会产生非常奇怪的内存泄漏现象。我们不能移动内存中的任何对象，因为当错把整数当成指针时会改变数据本身，这将导致垃圾回收的内存整理算法不会产生任何好处。（内存连续的好处显而易见：更容易分配大的内存，省却了内存碎片导致的不断查找，cache缓存命中的几率高）。
• 编译器提示法（Compiler hints）。如果使用静态类型语言，则编译器可以准确告知每个类中指针的偏移地址。只要能知道一个对象实现自哪个类，就可找出它的全部指针。Java虚拟机使用了此种方法，然而这种方案对于动态类型语言（如JavaScript）来说确不切实际，因为一个对象中的属性既可以是指针也可以是数据。
• 指针标记法（Tagged pointers）。此种方法需要在每个字（word）的末位保留一位来指明其是指针还是数据。这种方法有编译器支持的限制，但实现简单。V8使用了这种方法，一些静态类型语言也使用了这种方法，如OCamI。V8将所有数据以32bit字宽来存储，其中最低一位为0，而指针的最低两位为01。

V8将属于-2³⁰至2³⁰-1范围内的所有小整数（V8内部用Sims表示）使用了一个最低位为0的32位字（word）来表示，指针的最低两位为01。由于所有对象都至少以4个字节（byte）对齐，因此这样实现没有问题。在堆上的绝大多数对象都包含一组标记后的字（word），所以垃圾回收器可以快速的扫描它们，找出指针，忽略整数。有些对象，如string，已知仅包含数据（没有指针），它们的内容可以不被标记。

分代式回收

在大多数程序中，绝大多数对象的生命周期很短，只有少部分对象拥有较长的生命周期。

考虑到这一点，V8将堆分成了两代:新生代（new-space）及老生代（old-space）。

对象在新生代中被创建，新生代很小，只有1~8MB。在新生代中分配内存非常容易，持有一个指向内存区的分配指针，当需要给新对象分配内存时，递增指针即可。当分配指针到达了新生代的末尾，就会触发一个小垃圾回收周期（Scavenge算法），快速地从新生代中回收死去的对象。对于在两个小垃圾回收周期都存活下来的对象，则将其晋升（promote）至老生代。老生代在标记-清除（mark-sweep）或标记-整理（mark-compact）这样的非常不频繁的大垃圾回收周期中回收内存。当足够数量的对象被晋升至老生代中后，将触发一次大垃圾回收周期，至于具体时机，取决于老生代的内存大小及程序的行为。

新生代垃圾回收算法

由于新生代中的垃圾回收非常频繁，因此回收算法必须足够快。V8的新生代垃圾回收使用了Scavenge算法（Cheney算法的一种实现）。

新生代被划分为两个大小相等的子区：to区及from区。绝大多数对象的内存分配都发生在to区（一些特定类型的对象，如可执行的代码对象，被分配在老生代中）。当to区被填满后，交换to区和from区，现在所有对象都存储在from区，然后将活着的对象从from区拷贝到to区或者将它们晋升至老生代中，拷贝的过程实际是对to区内存的一次整理过程，整理后to区的内存占用将是连续的，以便于下次的内存分配依然保持快速和简单。拷贝过后，释放from区的内存。

可以看出，在新生代的垃圾回收周期中，始终有一半的内存时空的，由于新生代很小，因此浪费的空间并不大，而且新生代中的绝大部分对象生命周期都很短，因此需要复制的活着的对象很少，所以时间效率极高。

新生代垃圾回收特点：

• 内存区小
• 浪费一半空间
• 垃圾多
• 拷贝范围小
• 执行频率高且快

算法具体执行过程：

在to区中维护两个指针：allocationPtr（指向为下一个对象分配内存的地址）及scanPtr（指向下一个需要扫描的对象地址）。

首先，to区填满，交换to区与from区，此时to区为空，from区为满。

将from区中所有可从根对象到达的对象拷贝至to区，可以把此时的to区想象成一个双端队列，scanPtr指向队首，allocationPtr指向队尾，然后执行循环，每次遍历一个to区的对象，即每次遍历一个scanPtr所指向的对象，然后自增scanPtr。遍历到一个对象时，依次分析此对象内部的所有指针，如果指针不指向from区里的对象，则忽略它（因为此时它必指向老生代中的对象，而老生代中的对象还未回收）；如果指针指向from区中的对象，并且此对象还未被复制到to区（还未设置转换地址，具体见后文），则将其复制到to区的末端，也即allocationPtr所指向的位置，同时自增allocationPtr。然后将from区中的此对象的转换地址设置为复制后to区中的位置。转换地址保存在此对象的第一个字中（word），代替map地址。垃圾回收器可以通过检查对象第一个字中的低位来区分出转换地址和map地址，map地址的低位被标记，而转换地址没有。后续当分析到一个指针指向一个在from区中的对象，并且此对象已经被复制到to区（已有转换地址），那么只需简单将此指针指向的地址更新为对象的转换地址即可。

当所有to区中的对象都被处理后，即scanPtr与allocationPtr相遇时，算法结束。此时from中的所有对象都是垃圾对象，可以被全部释放。

抽象来看，整个算法遍历过程实际是一个BFS（广度优先搜索）过程，scanPtr之前所有对象都是其内部指针已被分析完毕的对象，scanPtr与allocationPtr之间的对象是需要分析内部指针的对象，当scanPtr与allocationPtr重合，搜索结束。

算法伪代码如下：

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] = toNeighbordef copyObject(*allocationPtr, object):  copy = *allocationPtr  *allocationPtr += size(object)  memcpy(copy, object, size(object))  return copy

写屏障

上面的算法有一个问题被忽略了：如果新生代中的某个对象，只有一个指针指向它，并且此指针属于老生代中的某个对象，那么如何识别出新生代中的此对象不是垃圾对象。将老生代中的全部对象扫描一遍是不现实的，因为数量庞大消耗巨大。

为了解决这个问题，V8在存储缓冲区中维护了一个列表，记录了老生代对象指向新生代对象的情况。当一个新对象被创建时，没有指针指向它，但当一个老生代中的对象指向它时，便在列表中记录下来，由于每次写操作都需要执行这样一个过程，这也称作写屏障。

每次在发生一个指针指向对象这样的写操作时都需要执行这样一系列的额外指令，这就是垃圾回收机制所带来的代价，但是代价并不大，写操作相比读操作并不常发生。一些其它JavaScript引擎的垃圾回收算法使用了读屏障，但这需要硬件辅助才能有较低的消耗。V8采用了一些机制来优化写屏障所带来的消耗：

• 通常可以验证出一个对象位于新生代，写屏障不会发生在新生代对象的操作上。
• 一个对象的所有引用都发生在局部时，此对象会被分配在栈上，栈上的对象显然不需要写屏障。
• 老->新这样的情况很少见，因此快速检测出新->新及老->老这两种常见情况可以提升很大性能，因为此两种情况不需要写屏障。每个页都以1MB来对齐，因此通过过滤一个对象的低20位（bit），可以找到它所在的页。页头含有指向其是否在新旧生代的标识，因此可以快速检查出两个对象所处的生代。
• 当存有关系列表的存储缓冲区被填满后，V8将对其排序，合并相同的项目，移除指针不再指向新生代的情况。

老生代垃圾回收算法

Scavenge算法对于少量内存具有非常快的回收和整理能力，但有很大的内存开销，因为要同时支持to区及from区。这对于少量内存区是可以接受的，但对于超过数MB的内存区来说，使用Scavenge算法是不切实际的。因此对于老生代数百MB的内存空间，V8使用了两种紧密相连的算法，即标记-清除算法与标记-整理算法。

这两种算法都包含了两个阶段：标记阶段，清除阶段或整理阶段。

标记清除（Mark-Sweep）

遍历堆中所有的对象，标记所有活着的对象。在清除阶段，只清除没有被标记的对象，即垃圾对象。由于垃圾对象占比很小，因此效率很高。

标记清除所带来的问题是，当一次清除结束后，内存空间往往出现了很多碎片，导致内存不再连续。当需要分配一个占有大量内存的对象时，如果没有一个内存碎片能满足此对象所需空间的大小，那么V8将无法完成此次分配，导致出发垃圾回收。

标记整理（Mark-Compact）

为了解决标记清除后所带来的内存碎片问题，V8引入了标记整理。标记整理的标记阶段与标记清除一样，但清除阶段变为整理阶段：将活着的对象向内存区的一段移动，移动完后直接清除边界外的内存。整理阶段涉及对象的移动，因此效率不高，但能保证不会产生内存碎片。

老生代垃圾回收特点：

• 内存区大
• 存放的对象生命周期很长
• 被清除的对象少，回收范围小
• 执行频率低且较慢

算法具体执行过程：

在标记阶段，所有在堆上活着的对象都会被发现且被标记。每个页都包含一个标记位图，位图的每一位都对应页上的一个字（一个指针大小就是一个字，也即对象的起始地址的大小就是一个字），这样做非常必要，因为对象可以起始于任何字对齐的偏移地址。位图会占据一定的内存开销（32位系统下占3.1%，64位系统下占1.6%），然而所有的内存管理系统都有类似的开销。同时使用2个位（bit）来代表一个对象的状态，对象至少占有两个字大小，因此这2个位不会重叠。

V8使用了三色标记法，对象的状态可被标记成三种（所以用2位来标记）：

• 如果为白色，那么此对象没有被垃圾回收器发现；
• 如果为灰色，那么此对象已被垃圾回收器发现，但其邻接对象还未被处理；
• 如果为黑色，那么此对象已经被发现，且所有它的邻接对象都已被处理完毕；

如果将堆想象成一个对象间通过指针连接的有向图，那么标记算法本质上是一个DFS（深度优先搜索）。在标记周期起始时，标记位图被清空，所有的对象都为白色。将可从根部直达的所有对象都标记为灰色，然后放入一个单独分配的双端队列中。接着循环处理队列中的每个对象：每次垃圾回收器都从队列中取出一个对象并将其标记为黑色，接着将其邻接对象（内部指针指向的对象）标记为灰色并放入双端队列中。当队列为空时，所有被发现的对象都被标记成了黑色，此时算法结束。对于特别大的对象，如长数组，在处理时可能会被分片处理，以减少队列溢出的几率。如果队列发生溢出，则对象仍会被标记为灰色但不放进队列中（此时它们的邻接对象还未被发现），当队列为空时，垃圾回收器会扫描堆中剩余的灰色对象，然后将它们放入队列中，继续执行标记过程。

伪代码如下：

markingDeque = []overflow = falsedef markHeap():  for root in roots:    mark(root)  do:    if overflow:      overflow = false      refillMarkingDeque()    while !markingDeque.isEmpty():      obj = markingDeque.pop()      setMarkBits(obj, BLACK)      for neighbor in neighbors(obj):        mark(neighbor)  while overflow    def mark(obj):  if markBits(obj) == WHITE:    setMarkBits(obj, GREY)    if markingDeque.isFull():      overflow = true    else:      markingDeque.push(obj)def refillMarkingDeque():  for each obj on heap:    if markBits(obj) == GREY:      markingDeque.push(obj)      if markingDeque.isFull():        overflow = true        return

当标记算法结束后，所有活着的对象都会被标记成黑色，所有死去的对象仍然为白色。这些信息将会被清除阶段或整理阶段使用，这取决于接下来使用哪种算法，这两种算法都以页级单位来回收内存（V8的页是1MB的连续内存，与虚拟内存页不同）。

清除算法扫描连续范围内的垃圾对象，然后释放它们的空间，并将它们加入空闲内存链表中。每个页都包含一些单独的空闲内存链表，分别代表小内存区（<256字）、中内存区（<2048字）、大内存区（<16384字）以及超大内存区。清除算法相当简单，只需遍历页的标记位图，找到范围内的白对象，然后释放。空闲内存链表被大量用于从新生代Scavenge算法所晋升过来放置在老生代的对象，同时也被整理所发用来移动对象。有些对象只能分配在老生代，因此空闲内存链表也被用来分配。

整理算法会尝试将对象从碎片页（包含许多小空闲内存的页）中移动并整合到一起。这些对象会被迁移到别的页上，因此这时可能会需要分配新的页，而迁出后的页即可返还给操作系统。整理的过程非常复杂，大概步骤是，对碎片页中的每个活着的对象拷贝到由空间内存链表分配的一块内存页，然后在碎片页的该对象的第一个字（word）写上新的转换地址，在之后的迁移过程中，对象的旧地址会被记录下来，在迁移结束后，V8会遍历所有记录有旧地址的指针，然后将这些指针更新为新的转换地址。如果一个页非常活跃，有非常多的别的页的指针指向这个页中的对象，那么此页将会保留 ，等到下一轮垃圾回收周期再进行处理。

V8的老生代内存回收结合了标记清除与标记整理两种算法，大部分情况下使用标记清除，当空间不足以分配从新生代晋升过来的对象时，才使用标记整理。

标记-清除与标记-整理的优化

增量标记（Incremental Marking）

由于在标记清除与标记整理的回收期间内，V8会暂停所有正在执行业务的代码，这会造成应用程序的卡顿，并且随着堆大小的增长，卡顿的时间会急速增加，这显然是不太可接受的。因此V8在标记期间，采用了增量标记的方法，将标记的过程拆分成很多部分，每次只标记一小部分，然后恢复业务代码的执行，再标记，这样循环交替执行标记。这样，原来应用程序卡顿的整个时间就会变分拆成多个细小的时间片，极大的提高了应用程序的响应度。

增量标记与标准的标记方式的最大区别在于，在标记期间，对象的有向图会发生改变（因为会间歇允许业务代码的执行）。因此需要解决的是发生黑对象指向白对象这种情况。黑对象已经被垃圾回收器完全处理过，因此不会再次对其处理，所以如果发生这种情况，那么白对象（此时已非垃圾对象）将依然会被当做垃圾对象回收。V8解决的方法依然是使用写屏障技术，此时不仅老生代指向新生代时发生写屏障，当黑对象指向白对象也会触发写屏障，此时黑对象会被重新标记成灰对象，然后放进双端队列中，当标记算法在稍后处理到队列中的该对象时，该对象指向的所有对象都会被标记成灰色，此时之前的白对象也已变成了灰色，目标达成。

惰性清除（Lazy Sweeping）

当增量标记完成后，惰性清除开始此时所有对象都已被标记成或生或死，堆已经准确知道可以回收多少内存，然而此时不必去一次全部回收死去的对象，可以采用延迟清理的处理手段，垃圾回收器可以根据需要来选择回收部分内存， 直到全部垃圾对象回收完毕，整个增量标记-惰性清除的 周期结束。

更多优化

V8已经加入了并行清除，主线程不会操作已死对象，由独立的线程来负责回收死对象的内存，整个过程只需要非常少量的同步操作。

同时V8正在实验并行标记，并将在今后引入这一技术。

总结

垃圾回收是一项非常复杂的技术，要实现高效快速的垃圾回收器需要结合多种算法以及大量优化，幸好引擎已经做了全部的工作，开发者只需关注更重要的业务逻辑即可。

V8 JavaScript引擎研究（三）垃圾回收器的实现