法时,总有一半的内存是空的。但是由于新生代很小,所以浪费的内存空间并不大。而且由于新生代中的对象绝大部分都是非活跃对象,需要复制的活跃对象比例很小,所以其时间效率十分理想。复制的过程采用的是BFS(广度优先遍历)的思想,从根对象出发,广度优先遍历所有能到达的对象
具体的执行过程大致是这样:
首先将From空间中所有能从根对象到达的对象复制到To区,然后维护两个To区的指针scanPtr和allocationPtr,分别指向即将扫描的活跃对象和即将为新对象分配内存的地方,开始循环。循环的每一轮会查找当前scanPtr所指向的对象,确定对象内部的每个指针指向哪里。如果指向老生代我们就不必考虑它了。如果指向From区,我们就需要把这个所指向的对象从From区复制到To区,具体复制的位置就是allocationPtr所指向的位置。复制完成后将scanPtr所指对象内的指针修改为新复制对象存放的地址,并移动allocationPtr。如果一个对象内部的所有指针都被处理完,scanPtr就会向前移动,进入下一个循环。若scanPtr和allocationPtr相遇,则说明所有的对象都已被复制完,From区剩下的都可以被视为垃圾,可以进行清理了
举个栗子(以及凑篇幅),如果有类似如下的引用情况:
在执行Scavenge之前,From区长这幅模样
那么首先将根对象能到达的ABC对象复制到To区,于是乎To区就变成了这个样子:
接下来进入循环,扫描scanPtr所指的A对象,发现其没有指针,于是乎scanPtr移动,变成如下这样
接下来扫描B对象,发现其有指向E对象的指针,且E对象在From区,那么我们需要将E对象复制到allocationPtr所指的地方并移动allocationPtr指针:
B对象里所有指针都已被复制完,所以移动scanPtr:
接下来扫描C对象,C对象中有两个指针,分别指向F对象和G对象,且都在From区,先复制F对象到To区:
然后复制G对象到To区
这样C对象内部的指针已经复制完成了,移动scanPtr:
逐个扫描E,F对象,发现其中都没有指针,移动scanPtr:
扫描G对象,发现其中有一个指向H对象的指针,且H对象在From区,复制H对象到To区,并移动allocationPtr:
完成后由于G对象没有其他指针,且H对象没有指针移动scanPtr:
此时scanPtr和allocationPtr重合,说明复制结束
可以对比一下From区和To区在复制完成后的结果:
D对象没有被复制,它将被作为垃圾进行回收
如果新生代中的一个对象只有一个指向它的指针,而这个指针在老生代中,我们如何判断这个新生代的对象是否存活?为了解决这个问题,需要建立一个列表用来记录所有老生代对象指向新生代对象的情况。每当有老生代对象指向新生代对象的时候,我们就记录下来
当一个对象经过多次新生代的清理依旧幸存,这说明它的生存周期较长,也就会被移动到老生代,这称为对象的晋升。具体移动的标准有两种:
1. 对象从From空间复制到To空间时,会检查它的内存地址来判断这个对象是否已经经历过一个新生代的清理,如果是,则复制到老生代中,否则复制到To空间中
2. 对象从From空间复制到To空间时,如果To空间已经被使用了超过25%,那么这个对象直接被复制到老生代
老生代所保存的对象大多数是生存周期很长的甚至是常驻内存的对象,而且老生代占用的内存较多
老生代占用内存较多(64位为1.4GB,32位为700MB),如果使用Scavenge算法,浪费一半空间不说,复制如此大块的内存消耗时间将会相当长。所以Scavenge算法显然不适合。V8在老生代中的垃圾回收策略采用Mark-Sweep和Mark-Compact相结合
标记清除分为标记和清除两个阶段。在标记阶段需要遍历堆中的所有对象,并标记那些活着的对象,然后进入清除阶段。在清除阶段总,只清除没有被标记的对象。由于标记清除只清除死亡对象,而死亡对象在老生代中占用的比例很小,所以效率较高
标记清除有一个问题就是进行一次标记清楚后,内存空间往往是不连续的,会出现很多的内存碎片。如果后续需要分配一个需要内存空间较多的对象时,如果所有的内存碎片都不够用,将会使得V8无法完成这次分配,提前触发垃圾回收。
标记整理正是为了解决标记清除所带来的内存碎片的问题。标记整理在标记清除的基础进行修改,将其的清除阶段变为紧缩极端。在整理的过程中,将活着的对象向内存区的一段移动,移动完成后直接清理掉边界外的内存。紧缩过程涉及对象的移动,所以效率并不是太好,但是能保证不会生成内存碎片
标记清除和标记整理都分为两个阶段:标记阶段、清除或紧缩阶段
在标记阶段,所有堆上的活跃对象都会被标记。每个内存页有一个用来标记对象的位图,位图中的每一位对应内存页中的一个字。这个位图需要占据一定的空间(32位下为3.1%,64位为1.6%)。另外有两位用来标记对象的状态,这个状态一共有三种(所以要两位)——白,灰,黑:
* 如果一个对象为白对象,它还没未被垃圾回收器发现
* 如果一个对象为灰对象,它已经被垃圾回收器发现,但其邻接对象尚未全部处理
* 如果一个对象为黑对象,说明他步进被垃圾回收器发现,其邻接对象也全部被处理完毕了
如果将对中的对象看做由指针做边的有向图,标记算法的核心就是深度优先搜索。在初始时,位图为空,所有的对象也都是白对象。从根对象到达的对象会背染色为灰色,放入一个单独的双端队列中。标记阶段的每次循环,垃圾回收器都会从双端队列中取出一个对象并将其转变为黑对象,并将其邻接的对象转变为灰,然后把其邻接对象放入双端队列。如果双端队列为空或所有对象都变成黑对象,则结束。特别大的对象,可能会在处理时进行分片,防止双端队列溢出。如果双端队列溢出,则对象仍然会成为灰对象,但不会被放入队列中,这将导致其邻接对象无法被转变为灰对象。所以在双端队列为空时,需要扫描所有对象,如果仍有灰对象,将它们重新放入队列中进行处理。标记结束后,所有的对象都应该非黑即白,白对象将成为垃圾,等待释放
清除和紧缩阶段都是以内存页为单位回收内存
清除时垃圾回收器会扫描连续存放的死对象,将其变成空闲空间,并保存到一个空闲空间的链表中。这个链表常被scavenge算法用于分配被晋升对象的内存,但也被紧缩算法用于移动对象
紧缩算法会尝试将碎片页整合到一起来释放内存。由于页上的对象会被移动到新的页上,需要重新分配一些页。大致过程是,对目标碎片页中的每个活跃对象,在空闲内存链表中分配一块内存页,将该对象复制过去,并在碎片页中的该对象上写上新的内存地址。随后在迁出过程中,对象的旧地址将会被记录下来,在迁出结束后,V8会遍历所有它所记录的旧对象的地址,将其更新为新地址。由于标记过程中也记录了不同页之间的指针,这些指针在此时也会进行更新。如果一个页非常活跃,如其中有过多需要记录的指针,那么地址记录会跳过它,等到下一轮垃圾回收进行处理
V8的老生代使用标记清除和标记整理结合的方式,主要采用标记清除算法,如果空间不足以分配从新生代晋升过来的对象时,才使用标记整理
由于全停顿会造成了浏览器一段时间无响应,所以V8使用了一种增量标记的方式,将完整的标记拆分成很多部分,每做完一部分就停下来,让JS的应用逻辑执行一会,这样垃圾回收与应用逻辑交替完成。经