概述
垃圾回收方案大致分类
- 引用计数
- 标记清除
- 二色标记
- 三色标记（增量扫描）
- 分代回收
垃圾回收的关键指标
- 吞吐量 ( ops/s or MB/s )
- 吞吐量需要大于垃圾产生的速度，不然没法工作了。
- 吞吐量大了。gc暂停的时间就多了，性能会变好。
- 延时
- STW pause duration（StopTheWorld）
- gc 消耗的 cpu 也是一种延时，只是不像 STW 那么典型。
- CPU消耗
- 峰值内存
其他
垃圾回收的内部细节极多。就算最简单的二色标记，也可以写的很复杂。
只有lua的代码完整的读过，其他的或是看过代码片段，或是看过些文章。
引用计数
C++ 的智能指针就可以算是了。
引用计数最大缺点是：无法处理循环引导，会内存泄漏。
PHP 使用的这种方案，并在 5.3.0 版本解决了循环引用的问题。
在 PHP 之前的版本是有内存泄漏的，不过php用于响应网络请求并没啥问题，不回收都没啥问题，请求完毕，直接关闭就好了。
标记清除 二色标记
思路很简单：Mark-Sweep.一般黑白色标记。
- 初始时全部是白色的。
- 递归搜索有用的对象，全部染成黑色。【Mark】
- 这时白色的就是垃圾了。清除掉。【Sweep】
- 黑色的对象全部变白色，回到初始状态。【这一步可以使用标志翻转的方式实现。0成本】
Mark阶段是要 STW 的。Sweep阶段到时可以延后慢慢做分步做，称之为：增量清理。
UnrealEngine GC Mark-Sweep
UE 的GC就是这种方案。
它的Mark阶段使用了多线程，不过那是在STW的情况下，用多线程加速标记的。
// 多线程标记的一个底层工具函数
bool ThisThreadAtomicallySetFlag(EInternalObjectFlags FlagToSet)
{
bool bIChangedIt = false;
while (1)
{
int32 StartValue = int32(Flags);
if (StartValue & int32(FlagToSet))
{
break;
}
int32 NewValue = StartValue | int32(FlagToSet);
if ((int32)FPlatformAtomics::InterlockedCompareExchange((int32*)&Flags, NewValue, StartValue) == StartValue)
{
bIChangedIt = true;
break;
}
}
return bIChangedIt;
}
在GC阶段是不能操作 UObject 比如 NewObject 时会有
checkf(!IsGarbageCollecting(), TEXT("Unable to create new object: %s %s.%s. Creating UObjects while Collecting Garbage is not allowed!"),
*GetNameSafe(InClass), *GetPathNameSafe(InOuter), *InName.ToString());
也就导致不能在 Game Thread 之外 NewObject, 除非锁住不让GC运行。
标记清除 三色标记
三色标记可以降低 Mark 阶段 STW 导致的延时峰值。会降低吞吐量。
黑白灰三色，gc 运行过程大致如下。【lua 基本就是这样】
- 初始全部是白色。root 对象变灰。【实现时可以保持root对象为灰色，之类的细节后面就不说了，太多了】
- 增量标记阶段。每次选择部分灰色对象，递归所搜标记白色对象为灰色或者黑色。
- 有对外引用的对象为灰色，其他为黑色。
- 不断执行这一步，值得没有灰色对象。（二次变灰的对象后面说）
- 结束标记阶段。原子操作，需要 STW。
- 递归扫描二次变灰对象。
- 这时只有黑白两色了。白色的就是要清理的。对于像 lua 这种语言，世界还没结束。
- 对于白色对象里自定义析构函数的对象，添加到待析构集合里，并执行标记。
- 【待析构对象会多存活一轮，对于分代GC也有这样的问题】
- 清理阶段。
- 释放白色对象的内存。
- 执行待析构对象的析构函数。
- 重置阶段。
- 翻转标记，黑色变白色。准备下次GC。
三色标记之写屏障
增量标记阶段是分步，乃至于多线程并行的，不需要 STW 。
因为标记的过程中，对象间的引用关系可能改变，要处理写屏障，保证算法正确。
三色标记正确运行需要满足下面2个条件中的一个
- 强三色不变式：黑色对象不引用白色对象。
- 弱三色不变式：黑色对象引用的白色对象可以通过灰色对象搜索到。
当使用增量回收和并发回收时，回收过程中，用户程序会新建对象修改对象引用，会破坏上面的条件。
写屏障就是为了处理这个事情。分前向屏障和后向屏障，见下面伪代码。
// 后向屏障: 当obj是黑色时，重新标记成灰色，进入二次灰色队列。在增量标记结束后，结束标记时再次递归标记。
// 这事基于假设：如果黑色对象引用新的对象，它很可能会再次发生修改，这时不如改成灰色，就不用反复使用屏障了。
// 进入二次灰色队列是为了增量标记能正常结束。
// 比如 线程栈 对象就需要如此处理。它会频繁修改。
write_barrier_back(obj, ref, ptr){
set_gray_again(obj) // obj 从黑色变灰色，进入二次灰色队列
ref = ptr
}
// 当obj是黑色时，标记插入的*prt对象至少为灰色。满足强三色条件
// GC运行时，新new出来的对象，可以直接标记成黑色。
djjkstra_write_barrier(obj, ref, ptr){
shade(ptr) // shade的做法时如果是白色就标记成灰色，否则不变。后面的伪代码都是这个意思。
ref = ptr
}
// 从obj上删除ref时，标记*ref至少为灰色。这样可以满足弱三色条件
// 悲观认为所有被删的对象都可能被黑色对象引用了，会降低吞吐量。
// **注意：**GC运行时，新new出的对象必须直接标记成黑色
yuasa_write_barrier(obj, ref, ptr){
shade(ref) // 当obj时黑色时，可以不标记，因为删掉黑色到白色之类引用关系不破坏弱三色条件
ref = ptr
}
golang 的混合写屏障
一般来说dijk就挺好的，但像golang这种希望写栈上的引用时不使用写屏蔽，提高性能，所以得找别的方法。
- golang早期用的dijk的方法，得把栈本身重新标记成灰色，mark的最后阶段STW，然后扫描下栈，完成标记。STW 可以达到100ms。
- golang 1.8 用yuasa的方法，并且改进了：
当栈还不是黑色时，所有复制操作，额外把ptr标记成灰色，就当是从栈里删除下来的。
// golang 1.8的方式，说法是结合了dij和yuasa，称为：混合写屏障。吞吐量比yuasa还低。
// **注意：**GC运行时，新new出的对象必须直接标记成黑色
golang_hybird_write_barrier(obj, ref, ptr){
shade(ref)
// 当栈本身还没完成扫描时，假定ptr就是从栈上删除取下来的对象。
// 当栈扫描完，可以当成标记为黑色，这时就不需要补充标记了。
if current stack is grey:
shade(ptr)
ref = ptr
}
这样就可以实现，栈里面的写操作不需要barrier处理，而且终止扫描阶段也不需要STW重新扫描栈。
golang 1.8 ，STW 控制在 1ms 以内。非常优秀。
分代gc
多数对象，是临时的，朝生暮死。函数栈上的对象基本都是这类。
分代回收基于这个前提设计，优化性能。多数情况下只扫描少量 new 对象（minor_gc），少数情况下执行全量gc(major_gc)。
分代GC要正确运行也是有条件的，old_obj 引用 new_obj 时，需要执行下面操作之一
- old_obj 添加到特殊集合，minor_gc 时，需要遍历这些 old_obj
- lua 把这种状态定义为 touch
- new_obj 添加到特殊集合，gc 执行时，它直接变成 old
对于多代gc 比如 lua 5.4 , 情况还要更加特殊。
lua 的分代gc
lua 5.2 引入分代gc, 5.3 删掉, 5.4 再次引入。默认还是三色标记。
lua 5.2 的分代gc，很简单，就两代，new or old.
但是效果不理想，以至于 lua5.3 删掉了分代gc。
原因大概是不少临时对象变成 old 的了：
- minor_gc 在 lua 运行时触发，这个时候栈里的临时对象也会变成old
- 定义了 __gc 函数的对象，会额外活过一轮，也就会变成 old
lua 5.4 重新设计了下，现在一个 new_obj 需要活过两轮 minor_gc 才能变 old.
状态数旧变成了三代 new > survival > old.
但是没这么简单。实际状态数有7个。
/* object age in generational mode */
#define G_NEW 0 /* created in current cycle */
#define G_SURVIVAL 1 /* created in previous cycle */
#define G_OLD0 2 /* marked old by frw. barrier in this cycle */
#define G_OLD1 3 /* first full cycle as old */
#define G_OLD 4 /* really old object (not to be visited) */
#define G_TOUCHED1 5 /* old object touched this cycle */
#define G_TOUCHED2 6 /* old object touched in previous cycle */
#define isold(o) (getage(o) > G_SURVIVAL)
/* 一些解释说明
1. G_OLD 引用的对象需要 isold 【这是个大的条件】。 否则需要使用写屏障。
- 前向屏障：标记引用的对象为 G_OLD0 【两轮 minor_gc，G_OLD0 => G_OLD1 => G_OLD 】
- 后向屏障：标记自己成 G_TOUCHED1
2. G_OLD1 有什么作用？
- 刚变old的对象可能还引用着活过一轮（G_SURVIVAL）的年轻对象，为了满足条件1，不能直接标记成 G_OLD.
- 标记成G_OLD1，下次执行 minor_gc 时，会把他们当成root对象，进行一次标记。gc 过后，真实变成 G_OLD.
3. G_TOUCHED2 有什么作用？
- 和 G_OLD1 类似。Touch 对象可能引用着 G_New 对象，年轻对象需要两轮gc，Touch 对象就需要做两次 Root 对象。
- G_TOUCHED1 一轮 minor_gc 后变成 G_TOUCHED2, 再一轮 minor_gc 变灰 G_OLD.
- G_TOUCHED2 是不能引用 G_NEW 的，遇到就要触发写屏障。后向屏障时，本身变成 G_TOUCHED1
*/
lua 5.4 的 major_gc 是 STW 下的全量gc，Orz。云风提到major_gc可以切换成inc_gc，执行完再切回来。
但是 lua 5.4 没这么做。当然了，默认也没有开启分代gc。
PS: lua的源码非常值得一读，至少代码量少呀。一个人就可以掌握并魔改。
dotnet c# 的分代GC
没看源码。应该比较复杂吧。
有多种gc可选，而且还有多种延时模式。
https://learn.microsoft.com/en-us/dotnet/standard/garbage-collection/latency
https://learn.microsoft.com/en-us/dotnet/api/system.runtime.gcsettings?view=net-7.0
PS: go vs c#, 对于 Max STW, go只有c#的百分之一!!
golang 的 垃圾回收
[图片上传失败...(image-eaed7a-1689944468106)]
go 的 STW 做的非常好。代价是 低吞吐量，高cpu耗时，以及更加频繁的gc（这个不知道比例如何）。
GCBurn 测试的一些结果
这个测试对比了 go 1.11 和 .NET Core 4.6 。结论大概是
- c# 的吞吐量是 go 的十倍，最佳情况下。多数情况没这么夸张。
- go 的 STW 是 c# 的百分之一，甚至更多！！
- 1G Memory，Max STW, go 0.5ms，c# 50ms。差不多这个样子。STW 随着内存增加接近线性增加。
- 当然啦。总的 gc cpu 时间，go不见得少，25% of the CPU during GC cycle。
golang 为什么没有使用分代回收。
go 使用的三色标记方案，这篇文章 讲述了 go 使用分代回收的尝试。
对于 go 来说收益不多，它的 STW 已经非常好了。
文章提到了分代回收的缺点：
- 需要时刻维护写屏障。
- 如果是三色标记，当垃圾回收停止时，是可以全速利用 cpu 的，完全没 gc 消耗。
go 的协程是有栈式的，这对于分代gc是不友好的，栈上的对象一般来说都是朝生暮死的，但当栈变old后，栈上的对象也要变old。
c# 的 await 协程是无栈式的状态机。【不知道这种实现是不是有分代gc的影响】
参考阅读资料
lua 5.4 源码 同时支持三色标记和分代回收
Getting to Go: The Journey of Go's Garbage Collector
A Guide to the Go Garbage Collector
Go vs C#, part 2: Garbage Collection
GCBurn github go cs c#
Lua GC 的工作原理 by 云风
垃圾回收之写屏障
Golang三色标记、混合写屏障GC模式图文全分析
Go 语言原本
