引子 从修真故事说起

上文大略介绍了垃圾回收的机制和标记革除法的外围思路，接下来筹备深刻介绍下 v8 引擎里的垃圾回收算法。既然是算法类的介绍，那天然是比拟干燥的，如果想齐全弄懂，能够珍藏下来，多看几遍（!·_·!）。

为了缓解一下解说的干燥，我感觉能够先从一个比拟有意思的话题来引入。置信大家都看过一些修真玄幻的小说，渡劫和飞升就是外面常见的桥段，当初来给大家讲个故事：

初始大陆 上有很多一般的修真者在修仙，随着时间推移，人数越来越多，最终达到了这个大陆的接受极限，此时天道必然要出手把握均衡，从中提拔留下一下能通过考验的优良之人，革除掉剩下的修为低下之人，从而腾出大陆空间；天道提拔的形式是：

• 将这些人挪移到渡劫空间里，而后开始一场 小天劫，等到小天劫完结后，再把活下来的人送回大陆空间，没有度过的人就会被革除，身死道消；
• 周而复始，只有每次人数达到大陆空间下限，都会进行一次小天劫，

那么这之中就会有度过数次天劫的佼佼者，天道会处分他 飞升 到更高级、更广大的 远古大陆 去，踏上更高一级的修炼途程，然而咱们晓得，修仙之路是逆天之路，更高级的中央天然也有更高级的劫数 ，远古大陆尽管更加辽阔，远胜于初始大陆，然而每隔肯定的工夫，也会触发一次更大级别的 大天劫，清理这个大陆上的修真者。

大部分的修真者生命是短暂的，熬不过一两次 小天劫，只有多数的修真者可能怀才不遇，飞升到远古大陆。

故事临时就讲到这里，接下来就是正题。

堆构造的划分

在聊垃圾回收之前，要先理解下 v8 引擎对于堆构造的划分：

1. 新空间 (New-space)：大多数对象都调配在这里。新空间很小，并且被设计为能够十分疾速地进行垃圾回收，而与其余空间无关。其实这个新生空间对应的，就是前文的 初始大陆
2. 旧指针空间（Old-pointer-space）：蕴含大多数对象，这些对象可能具备指向其余对象的指针。在新空间中生存了一段时间后，大多数对象都移到了这里。（特例也能够先不论）
3. 旧数据空间（Old-data-space）：蕴含仅蕴含原始数据的对象（没有指向其余对象的指针）。在新空间中存活了一段时间后，字符串，装箱的数字和未装箱的双精度数组会移到此处。旧指针空间和旧数据空间合起来就称为旧空间，就对应前文的远古大陆。
4. 大对象空间：此空间蕴含的对象大于其余空间的大小限度。大对象永远不会被垃圾收集器挪动。（能够先不论）
5. 代码空间：此处调配了蕴含 JIT 指令的代码对象。这是惟一具备可执行内存的空间（只管能够在大对象空间中调配代码，并且这些代码也是可执行的。（能够先不论）

介绍到这里，置信有些同学曾经能够对应出一部分内容了，接着往下看（次要先记住后面 3 个空间就好，前面会始终用到）：

分代回收机制(Generational collection)

在大部分小说设定里，一般修真者的生命总是短暂的，能怀才不遇的万中无一。在大部分程序里，对象数据的生命也是短暂的，只有少部分数据对象会长期存活。所以依据这种状况，v8 引擎设计了分代回收的形式 — 也就是后面提到的：天劫分一大一小两类，小天劫产生频繁，打扫新生和一般的修真者，只在初始大陆产生；大天劫距离更久，清理远古大陆的修真者，他们别离产生在不同的空间，共同完成垃圾回收工作。

整体配合机制如下：

1. 在 新空间 调配新对象，直到空间充斥，就触发 小型回收机制；
2. 在小型回收机制中存活下 2 次的对象，就会被挪动到旧空间去（依据数据特点调配到旧指针空间或者旧数据空间）；
3. 旧数据空间内存达到肯定值的时候（这个阈值具体的参数先不必关注），触发 大型回收机制（major garbage collection）；

（能够再去回头读读后面的故事 是不是根本全对上了！）

接下来咱们来别离介绍这两种机制。

小型回收机制 scavenge

小型回收机制，官网名称是 scavenge，它产生概率频繁，所以要求速度要比拟快。根本算法思路源于驰名的 Cheney 算法，思路如下:

1. 把新空间 (new-space) 均分为两局部，命名为 from 空间和 to 空间；（这两个空间不会同时应用）
2. 后面说的新对象的调配 是在 to 空间进行的，直到填满 to 空间为止；
3. 此时替换 from 空间和 to 空间，也就是把 to 空间的所有对象都挪动到 from 空间，这一步执行完后，to空间变成空的，from是满的；
4. 在 from 空间，从 root 开始寻找所有可拜访对象（这是上一篇的内容了，遗记了能够去回顾一下），而后把这些对象都挪动到 to 空间或者 old 空间（某些曾经挨过两次的就应该飞升了），这一步其实 v8 引擎还会顺便做一下压实（compacted）, 也就是把存活的对象地位略微集中一下，减少一下缓存的局部性，放弃调配疾速而简略；
5. 清空 from 空间（筛选剩下的都是可回收的了）；

第一次接触这个算法的读者可能略微有点绕，也会纳闷为什么不间接在 to 空间满了的时候就间接清理垃圾，保留 live 对象 (也就是可拜访对象)，反而要移来移去的；其实多看两遍就很好了解了，这样设计的益处在于to 空间永远作为理论的内存调配空间，from充当的只是一个长期容器，也就是 渡劫的空间，两者不须要同时应用，这样十分清晰。官网还贴了一份伪代码:

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

代码天然看起来干燥一些，适宜有趣味的读者前面缓缓钻研，第一遍浏览齐全能够略过，因为思路都曾经讲完了，缺的只是一些具体的实现。

这里有个小细节，咱们刚刚说到，回收的起始点是 root 对象，也就是全局对象以及所有它能够拜访到的对象（包含闭包等）。那么 如果某个对象只是被曾经飞升到旧空间的数据对象援用了那么办呢？ 依照咱们这种清理形式，如果咱们不把旧空间扫描一遍来排查这样的非凡状况，就会把这个对象给误清理掉；如果咱们真的这么做，那老本就贬低了, 因为咱们说过小型清理的产生频率十分高，所以不可能每次都还去扫描旧空间。

所以，为了解决这个问题，v8 引擎在内存里保护了一个缓冲区，每当新 (new-space) 空间的对象被旧 (old-space) 空间的对象援用时，这个旧空间对象的 key 将会被记录下来，例如:

var user1 = {name: 'leo'};
// ... 这里省略一些代码，假设经验了一段时间并且 user1 被挪动到 old 空间之后
use1.friend = {name: 'john'};

这个例子中，咱们假如 use1 通过一段时间后进入了旧空间，而后 {name: 'john'} 被新调配到新空间，并且只有 user1 保留了对它的援用，此时这个 key，也就是friend 的内存地位会被记录到缓冲区里，前面会专门检测这种状况，避免误杀。
这个尽管须要额定破费一些代价，然而是为了达到回收成果必须要付出的老本，而且理论这种情景的频率并没有设想的高。

大型回收机制

小型回收机制 Scavenge 比拟适宜小区域的清理，因为它须要替换内存空间，有比拟多内存开销，因为新空间比拟小，所以这样做是没问题的，对于要大的多的旧空间，就要用大型回收机制。

大型回收机制指的就是咱们前文说的标记 - 革除法，实际上蕴含分成 标记 - 革除 和标记 - 压实（压实的概念后面也说过了）两种。他们都是分 2 个阶段来运行的：

• 标记 阶段：实质上就是一场深度优先搜寻：有三种色彩的标记（红色 - 初始状态，彩色 - 已查看状态；灰色 - 待查看状态）；

  1. 首先将所有的对象设置为 红色 ，而后从 root 对象登程，将所有能够拜访的对象标记为 灰色。并用一个数组缓存起来；
  2. 而后遍历该数组，每次都把要遍历的对象 涂成彩色并移出 ，并且把他的相邻节点都涂成 灰色，并放入队列，直到队列为空
  3. 持续查看是否有 灰色对象，如果有持续放入队列而后循环, 直到所有的可拜访对象都变成彩色。

这一段看起来尽管有点绕，然而本质上就是深度遍历有向图，比拟根底，所以就不画流程图了。通过标记当前，所有的对象就只剩下彩色和红色了，其中红色的就是可清理垃圾对象。

• 革除（或压实）阶段：革除算法比较简单，依据上一步的查找后果，把对应红色标记对象内存地址转为自由空间；压实算法绝对简单一些，外围的思路是把对象从比拟扩散的内存地址，个体迁徙到其余某一块间断的内存地址外面，个别是另外选取一个间断内存块，而后把对象复制过来，并且在源对象上留下一个转发地址，在迁徙过程中，记录下相干的指针地位，在实现整个迁徙之后，更新指针指向新地位，如果遇到某一块内存地址因为太多对象都要迁徙过来，导致无奈全副迁徙，那么会等到下一个大回收周期再持续迁徙。

好了 到这里，核心内容根本就介绍完了，能够稍作劳动。

v8 引擎的优化机制 - 增量标记和提早革除

遇到大量的实时数据处理时，标记革除（或压实）法会很耗时，所以 Google 提出了两项改良计划：增量标记和提早革除。

增量标记：

这个其实蛮好了解的，因为前文讲到的标记革除算法可能一次做完须要很长的工夫，这个期间是 须要暂停程序的 ，所以 v8 容许设定一个阈值，例如每次标记肯定数量（比方 100 个）的对象，就先回去执行程序，而后再回来持续标记，也就是 在程序运行过程交叉垃圾回收，从而升高最大暂停工夫。

然而这个办法有个问题：如果我第一次曾经把一些对象标记过了，然而返回垃圾回收过程时，有些对象被批改了！

例如后面标记为彩色的对象，在返回执行程序过程，减少了一个指向曾经被标记为红色对象的指针，这就会导致间接继续执行标记会误杀这个红色对象（因为起初它实际上变成可拜访的了），怎么办呢？

很简略，还记不记得小回收阶段，v8 引擎在内存里保护了一个缓冲区，解决 new 空间的对象被 old 空间的对象援用的办法？同样的，他也会记录这种从彩色对象到红色对象的指针，并且之后把这样的彩色对象再变成灰色，从新查看，这样问题就解决了。

提早革除：

这个也很简略，在标记之后，引擎分明直到哪些是能够革除的对象，然而并不代表须要同时革除掉这些垃圾，所以引擎抉择 按需清理，优先从须要的页面开始，逐渐清理所有的页面垃圾，而后就算就实现了一整个垃圾回收周期。

总结

本文在前一节的根底上，深入分析了 v8 引擎的垃圾回收机制，

• 从大的方面来说，分成小回收周期和大的回收周期
• 小回收周期产生在新空间，频率高，工夫短速度快，使用 chenny 算法
• 大回收周期产生在旧空间，频率低，速度慢，用深度优先遍历和三色标记法（黑白灰）
• 优化形式次要是增量标记和提早清理，外围思路是碎片化标记阶段和优先按需清理空间

好了，对于垃圾回收的内容，大略就说到这里，本文绝对前一篇文章略微干燥一些，而且没有画图来阐明过程（问就是懒得画 -_-），然而多看几遍还是挺好了解的，而且曾经去掉了对于内存位图之类更底层的货色不便了解外围思路，想钻研更底层内容的同学能够看前面具体的参考文章。

常规：如果内容有谬误的中央欢送指出（感觉看着不了解不难受想吐槽也齐全没问题）；如果有帮忙，欢送点赞和珍藏，转载请征得批准后著明出处，如果有问题也欢送私信交换，主页有邮箱地址

顺便再说下，RingCentral 目前在杭州也设置了办公点，而且能够申请长期近程办公，辞别 996，均衡工作生存，有趣味的同学能够私信或者发邮件给我，能够收费帮忙内推~

参考文章

http://jayconrod.com/posts/55/a-tour-of-v8-garbage-collection