三色标记法时间复杂度与GCPercent节省的时间分析

上一张图：

三色标记法(tricolor mark-and-sweep algorithm)是传统 Mark-Sweep 的一个改进，它是一个并发的 GC 算法，在Golang中被用作垃圾回收的算法，但是也会有一个缺陷，可能程序中的垃圾产生的速度会大于垃圾收集的速度，这样会导致程序中的垃圾越来越多无法被收集掉。原理如下所示：
step 1: 创建：白、灰、黑 三个集合。
step 2: 将所有对象放入白色集合中。
step 3: 从根节点开始遍历所有对象，把遍历到的对象从白色集合放入灰色集合(备注：这里放入灰色集合的都是根节点的对象)。
step 4: 遍历灰色集合，将灰色对象引用的对象(备注：这里指的是灰色对象引用到的所有对象，包括灰色节点间接引用的那些对象)从白色集合放入灰色集合，然后将分析过的灰色对象放入黑色集合。
step 5: 直到灰色中无任何对象。
step 6: 通过写屏障(write-barrier)检测对象有变化，重复以上操作(备注：因为 mark 和用户程序是并行的，所以在上一步执行的时候可能会有新的对象分配，写屏障是为了解决这个问题引入的)。
step 7: 收集所有白色对象（垃圾）。

时间复杂度分析：
1、标记root节点：rn’（root节点是一个集合）
2、标记灰色、黑色、移动元素：kn（从根结点开始遍历所有对象，遍历过程类似树的遍历）
3、清除白色集合：ln
4、标记所有节点为白色：xn
所以总的时间复杂度：rn’+kn+ln+xn

当GCPercent等于400时：
1、根结点这块不变：rn’
2、因为有用的内存大小并没有变，所以标记阶段还是：kn
3、引起垃圾增加，所以清理的时间增加：4ln
4、标记所有节点为白色：xn
总时间为：rn’+kn+4ln+xn

对比一下在同样的内存垃圾数量下：
GCPercent100*4-GCPercent400=3rn’+3kn+3xn
由于root节点为少数，忽略不计的话：节省的时间为：3kn+3xn
其中x可以为0，比如：初始时候维护一个原色关系{0:”w”, 1:”g”, 2;”b”}，在第四步只需要把这个关系表中的0和2对应的颜色对调一下，即可：{0:”b”, 1:”g”, 2;”w”}
综上所述，m=k/l的值决定GCPercent比例调整的影响，m越大，调整比例越明显，反之亦然

图上可以看出 k = 1000 l

所以，GCPercent调大是可以减少gc的总时间，提高cpu利用率的
建议可根据机器内存大小调整GCPercent为400-1000，不然的话还是好好优化下代码

转载请注明：小Y » 三色标记法时间复杂度与GCPercent节省的时间分析