golang 1.8 gc的演进

在java的gc中，主要有三种算法，即：标记-删除，标记-整理，复制，网上有很多资料介绍相关内容，其中标记主要是为了找到内存中不可达的对象，并将其回收。而gc过程中最关键的指标就是STW时间，如果STW过长，会影响整体程序的响应。

Serial

Serial

采用单一线程进行GC。

特点：STW时间长，但是无线程切换开销，简单高效

ParNew

ParNew

与Serial一样，只是在新生代采用并发gc

CMS

CMS

CMS收集器主要用于老年代内存的回收，致力于降低STW时间，但是却拉长了gc的整体时间。

1. 对CPU资源非常敏感，可能会导致应用程序变慢，吞吐率下降。
2. 无法处理浮动垃圾，因为在并发清理阶段用户线程还在运行，自然就会产生新的垃圾，而在此次收集中无法收集他们，只能留到下次收集，这部分垃圾为浮动垃圾，同时，由于用户线程并发执行，所以需要预留一部分老年代空间提供并发收集时程序运行使用。
3. 由于采用的标记 – 清除算法，会产生大量的内存碎片，不利于大对象的分配，可能会提前触发一次Full GC。虚拟机提供了-XX:+UseCMSCompactAtFullCollection参数来进行碎片的合并整理过程，这样会使得停顿时间变长，虚拟机还提供了一个参数配置，-XX:+CMSFullGCsBeforeCompaction，用于设置执行多少次不压缩的Full GC后，接着来一次带压缩的GC

G1

G1回收器是目前用的比较前沿的回收策略，通过冗余一定量的Survivor空间来提升复制的效率以及减少内存碎片，其也是像CMS一样通过并发标记。

gc in golang

golang1.5也引入了标记清除的回收算法，为了达到更好的并发清除效果，其设计了一个三原色回收法，具体回收过程见 文章

golang’s gc

其基本思路就是：(开始时所有对象都被标为白色(可被回收))

1. STW，将所有栈及global变量标为灰色 (Stack scan)
2. 从灰色对象开始并发标记所有可达对象，将可达对象标为灰色，当一个对象所有引用对象都被标为灰色后，该对象就被置为黑色。(Mark)
3. 当所有对象都被标为黑色后，再进行一次STW，重新扫描栈和global未扫描过的对象。(Mark termination)
4. 并发的清除所有白色对象。(Sweep)

看完这篇文章后，可能会有一个疑问：

1. 在golang的并发标记的同时，会有新对象创建出来，如果新对象被黑色对象引用该怎处理。

写屏障 write barrier

所以这里就需要了解一下写屏障的概念。这也是golang1.8如何去除Mark termination的关键。写屏障的目标就是要保障约束： 黑色对象不会指向白色对象

写屏障的实现有很多模式，在golang1.7之前主要采用的是Dijkstra-style insertion write barrier [Dijkstra ‘78], 其伪码实现如下：

writePointer(slot, ptr):
    shade(ptr)
    *slot = ptr

其思路就是在进行指针的重定向时，将被指向的指针对象标记为灰色(shade it)，这样如果有新的对象被创建或者黑色对象指向白色对象时，目标对象就会标灰，从而满足了 黑色对象不会指向白色对象 约束。

可以发现上述写屏障只shade了堆内存，因为实现将栈对象的写屏障比较难，有较大损失（这个为啥难我也不知道0.0: 文档原文： In particular, it presents a trade-off for pointers on stacks: either writes to pointers on the stack must have write barriers, which is prohibitively expensive, or stacks must be permagrey. Go chooses the later, which means that many stacks must be re-scanned during STW）。

因此对于栈中的元素需要一次STW来进行rescan。

eliminate rescan in golang 1.8

为了尽可能的缩短STW时间，golang将写屏障进行优化，以此来去掉rescan，缩短STW时间。

其提出了一种混合写屏障机制：hybrid write barrier that combines a Yuasa-style deletion write barrier [Yuasa ’90] with a Dijkstra-style insertion write barrier [Dijkstra ’78]，其伪码实现如下：

writePointer(slot, ptr):
    shade(*slot)
    if current stack is grey:
        shade(ptr)
    *slot = ptr

上述伪码实现中，需要保障一个前提就是新建对象都是标为黑色，这样如果栈中新建对象的话不需要重新扫描栈，因为已经标记为黑色，但是会出现如下情况：

{
    ... // B is already created
    A a;  // A is colored in black
    a->c = b->c; // c is white
    b->c = d->c;
}

显而易见如果新建对象比较为黑色的话，会打破黑色 对象引用白色对象 的约束，因此混合写屏障提供了另一种弱的三原色约束： Any white object pointed to by a black object is reachable from a grey object via a chain of white pointers (it is grey-protected). 所有黑色对象引用的白色对象，一定能被另外一个灰色对象引用 ，这样就算黑色对象引用了白色对象，这个白色对象依旧被灰色对象保护着。

正确性证明

对于内存对象的操作主要包括四种情况：1. 堆对象引用变为栈对象引用；

2.栈对象引用变为另一个栈对象引用；3.堆对象引用变为另一个堆对象引用；4栈对象引用变为另一个堆对象引用。

所以我们只要能在上述四种情况下，保障 弱三原色约束 ，就能证明该写屏障是可靠的：

最开始的混合写屏障实现如下：（后面再讨论为啥栈不是gray后，不需要shade了）

writePointer(slot, ptr):
    shade(*slot)
    shade(ptr)
    *slot = ptr

对于情况1：

{
A a; // black
a = b->c; // 栈操作没有写屏障，但是c对象依旧被b->p保护着
b->c = null; // b 不再引用c；此时写屏障中shade(*slot)会将c shade，因此是安全的。满足弱约束
}

对于情况2：

{
A a; // black
a = b; // 栈操作没有写屏障，但是栈对象已经是灰或者黑
}

对于情况3：

{
// a is black
a->d = b->d; // 写屏障 shade(ptr) 依旧保护d对象
b->d = null;  // shade(*slot) 与 shade(ptr) 效果一样
}

对于情况4：

{
a->c = c;  // 堆对象shade(*slot) 当堆对象unlink时保护原有对象
}

综上所述，混合屏障可以满足 弱三原色约束。

为啥栈都标记为黑色后，不需要shade 被指对象

一个栈的所有对象被扫描为黑色后，栈对象锁指向的元素要么是灰色的，要么指向的白色对象被另外一个灰色的堆对象应用着。因此指定对象都会被shade(*slot) 守护。

综上所述：

shade(*slot) 用来满足灰色对象能保护其所有指向的对象约束

shade(ptr) 用来满足当一个对象从栈逃逸到堆时，依旧是被保护的。