引子 从修真故事说起

上文大略介绍了垃圾回收的机制和标记革除法的外围思路， 接下来筹备深刻介绍下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] = toNeighbordef 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