本周继续探究方舟编译器的垃圾回收优化算法，首先深入了解一下标记-清除算法和RC算法。

在了解标记-清除算法前，我们先要了解几个基本概念。

首先是mutator和collector，这两个名词经常在垃圾收集算法中出现，collector指的就是垃圾收集器，而mutator是指除了垃圾收集器之外的部分，比如说我们应用程序本身。mutator的职责一般是NEW(分配内存),READ(从内存中读取内容),WRITE(将内容写入内存)，而collector则就是回收不再使用的内存来供mutator进行NEW操作的使用。

第二个基本概念是关于mutator roots(mutator根对象),mutator根对象一般指的是分配在堆内存之外，可以直接被mutator直接访问到的对象，一般是指静态/全局变量以及Thread-Local变量(在Java中，存储在java.lang.ThreadLocal中的变量和分配在栈上的变量 - 方法内部的临时变量等都属于此类).

第三个基本概念是关于可达对象的定义，从mutator根对象开始进行遍历，可以被访问到的对象都称为是可达对象。这些对象也是mutator(你的应用程序)正在使用的对象。

顾名思义，标记-清除算法分为两个阶段，标记(mark)和清除(sweep).

在标记阶段，collector从mutator根对象开始进行遍历，对从mutator根对象可以访问到的对象都打上一个标识，一般是在对象的header中，将其记录为可达对象。

而在清除阶段，collector对堆内存(heap memory)从头到尾进行线性的遍历，如果发现某个对象没有标记为可达对象-通过读取对象的header信息，则就将其回收。

从上图我们可以看到，在Mark阶段，从根对象1可以访问到B对象，从B对象又可以访问到E对象，所以B,E对象都是可达的。同理，F,G,J,K也都是可达对象。到了Sweep阶段，所有非可达对象都会被collector回收。同时，Collector在进行标记和清除阶段时会将整个应用程序暂停(mutator)，等待标记清除结束后才会恢复应用程序的运行，这也是Stop-The-World这个单词的来历。

接着我们先看下一般垃圾收集动作是怎么被触发的，下面是mutator进行NEW操作的伪代码：

New():
    ref <- allocate()  //分配新的内存到ref指针
    if ref == null
       collect()  //内存不足，则触发垃圾收集
       ref <- allocate()
       if ref == null
          throw "Out of Memory"   //垃圾收集后仍然内存不足，则抛出Out of Memory错误
          return ref

atomic collect():
    markFromRoots()
    sweep(HeapStart,HeapEnd)

而下面是对应的mark算法:

markFromRoots():
    worklist <- empty
    for each fld in Roots  //遍历所有mutator根对象
        ref <- *fld
        if ref != null && isNotMarked(ref)  //如果它是可达的而且没有被标记的，直接标记该对象并将其加到worklist中
           setMarked(ref)
           add(worklist,ref)
           mark()
mark():
    while not isEmpty(worklist)
          ref <- remove(worklist)  //将worklist的最后一个元素弹出，赋值给ref
          for each fld in Pointers(ref)  //遍历ref对象的所有指针域，如果其指针域(child)是可达的，直接标记其为可达对象并且将其加入worklist中
          //通过这样的方式来实现深度遍历，直到将该对象下面所有可以访问到的对象都标记为可达对象。
                child <- *fld
                if child != null && isNotMarked(child)
                   setMarked(child)
                   add(worklist,child)

在mark阶段结束后，sweep算法就比较简单了，它就是从堆内存起始位置开始，线性遍历所有对象直到堆内存末尾，如果该对象是可达对象的（在mark阶段被标记过的），那就直接去除标记位（为下一次的mark做准备），如果该对象是不可达的，直接释放内存。

sweep(start,end):
    scan <- start
   while scan < end
       if isMarked(scan)
          setUnMarked(scan)
      else
          free(scan)
      scan <- nextObject(scan)

缺点
标记-清除算法的比较大的缺点就是垃圾收集后有可能会造成大量的内存碎片，像上面的图片所示，垃圾收集后内存中存在三个内存碎片，假设一个方格代表1个单位的内存，如果有一个对象需要占用3个内存单位的话，那么就会导致Mutator一直处于暂停状态，而Collector一直在尝试进行垃圾收集，直到Out of Memory。

那么怎样提升引用计数算法的效率？
1.延迟引用计数。
2.合并引用计数：在单个时间段内，只关注对象是否第一次被修改，针对同一对象的再次修改则会被忽略。
3.缓冲引用计数：将所有的引用计数操作缓冲起来以便后续处理，同时只有回收线程可以执行引用计数变更操作。

延迟引用计数：
只有当赋值器操作堆中的对象时产生的引用计数变更才会立即生效，而操作栈或者寄存器（局部变量）所产生的变更则会延迟执行—>代价：引用计数器不再准确，所以不能立即回收引用计数等于0的对象，转而要引入stop the world来定期修正引用计数。
当引用变成0之后，需要将其添加到零引用表中（零引用表中的对象都是引用计数为0但可能仍然存活的对象，当赋值器把零引用对象的引用写入到堆中某一对象时，可以将其从零引用表中移除）。
当堆中内存耗尽时就必须进行垃圾回收：挂起所有赋值器线程并检查零引用表。怎么确定零引用表中的对象是否存活呢？最简单的办法是对根指向的对象进行扫描并增加引用计数。完成这一步后，所有被根引用的对象的引用计数都大于0，那些仍然为0的就是需要回收的垃圾了。

合并引用计数：
延迟引用计数解决了赋值器操作局部变量时的引用计数变更。而合并引用计数则只需关注对象在某一个时段开始和结束时的状态，忽略中间的变化。

具体来讲，就是在某一个时段开始前，在回收器日志中记录下A都引用了哪些对象（如图是B,C），然后在该时段结束时，得到A现在都引用了哪些对象（B,D），然后先对回收器日志中记录的对象的引用计数都-1，再对现在引用的对象的引用计数+1.（B先-1，再+1，最后引用计数保持不变。C减1。D直接+1）

将延迟引用和合并引用结合在一起可以显著大部分赋值器上的开销，但是我们也付出了一定的代价，即引入了停顿，降低了回收的时效性，日志缓冲区和零引用表也带来了额外的空间开销。

GC的基本单位——对象，对象一般包含头（header）和体（field），头包含了这个对象的定义信息，包括大小（size）、类型（type）和信息（info），体包括了这个对象的行为方法以及构造方法（构造方法就是产生对象用的）。

方舟编译器垃圾回收机制方舟编译器垃圾回收算法，在垃圾回收方面采用的是RC计数优化算法（计数参数是ref）加消除环算法（改进版–标记消除环）。其实RC计数中最明显的问题应该是循环引用，一旦两个对象循环引用，其引用计数始终是2，无法归零回收。采用消除环算法（就是AB循环引用了，最后都要给AB对象赋值NULL，从根节点上走就碰不到循环引用无法回收的问题了）可以解决这个问题，不过方舟在这方面做得改进更加智能。为避免内存被这些环的死循环占用，方舟引入了标记处理，就是对这些环进行管理和标注，就是在编程阶段，出现环问题时就要警告你这么做危险，这样子可以减少大部分程序中环的出现。另外一方面，方舟编译器在运行状态下引入了高效的环回收机制，允许有选择地智能回收某个APP的内存占用，对于传统环回收算法来说这是很强大的一个改进。