golang gc的内部优化

今天讲一个常见的gc compiler（也就是官方版本的go编译器和runtime）在垃圾回收的扫描标记阶段做的优化。
我对这个优化的描述印象最深的是在bigcache的解释里，大致内容是假如map的键值都不包含指针，那么gc扫描的时间不管这个map多多数不会深入扫描map内部存储的数据，只查抄map自己是否必要回收。
这么做的好处显然是可以让gc的扫描速度大大增加，从而减少gc对性能的损耗。
减少指针数目自己就是常见的优化手段，但让我感到好奇的是解释里说的“跳过”。跳过的依据究竟是什么，以及只有map存在这种跳过吗？
于是我进行了全面的搜索，效果除了复读bigcache里那段话的，没什么有效的发现。
于是这篇文章诞生了。
跳过扫描指的是什么

前置知识少不得。
简单的说，gc在查抄对象是否存活的时间，除了对象自己，还要查抄对象的子对象是否引用了其他对象，具体来说：

• 数组和slice的话指存储在里面的每一个元素是否存活，这里被存储的元素是数组/slice的子对象
  
• map的子对象就是里面存的键和值了
  
• struct的子对象是它的每一个字段
  

为了查抄这些子对象是否引用了其他对象（关系到这些被引用的对象是否能被回收），gc必要深入扫描这些子对象。子对象越多必要扫描的东西就越多。而且这个过程是递归的，因为子对象也会有子对象，想象一下嵌套的数组大概map。
跳过扫描自然就是指跳过这些子对象的扫描，只必要查抄对象自己即可的操作。
什么样的对象是可以跳过扫描的

这也是我的第一个疑问。跳过或不跳过的依据是什么，又大概是什么东西在控制这一过程。
bigcache告诉我们存有不包含指针的键值对的map是可以跳过的，那么具体情况是怎么样的呢？
找不到有效的资料，那只能看代码了，代码以Go 1.22.1为准。
起首应该想到的应该是从gc的代码开始看，于是很快就有了劳绩:

1. // runtime/mgcmark.go
2. // 负责gc扫描的函数，还有个它的兄弟gcDrainN，代码差不多就不放了
3. func gcDrain(gcw *gcWork, flags gcDrainFlags) {
4.     ...
5.     // 先标记所有root对象，检查对象是否存活就是从这开始的
6.     if work.markrootNext < work.markrootJobs {
7.                 for !(gp.preempt && (preemptible || sched.gcwaiting.Load() || pp.runSafePointFn != 0)) {
8.                         markroot(gcw, job, flushBgCredit)
9.                         // 检查自己是否需要被中断，需要的场合函数会直接跳到收尾工作然后返回
10.                 }
11.         }
13.     // 从工作队列里拿需要扫描的对象进行处理
14.     for !(gp.preempt && (preemptible || sched.gcwaiting.Load() || pp.runSafePointFn != 0)) {
15.                 b := gcw.tryGetFast() // 从工作队列拿对象
16.                 scanobject(b, gcw)
17.         ...
18.         }
19.     ...
20. }

复制代码

流程不考虑中断、数据统计和校验的话还是很简单的，就是先标记扫描的出发点，然后从gcw这个工作队列里拿东西出来处置惩罚，直到工作队列里再也没数据了为止。
markroot也很简单，根据root对象的种类，它会调用scanblock大概markrootSpans。此中scanblock会调用greyobject来标记待处置惩罚的对象。因此稍微看看markrootSpans即可。
markrootSpans是用来处置惩罚那些存放设置了终结器的对象的内存的：

1. // runtime/mgcmark.go
2. func markrootSpans(gcw *gcWork, shard int) {
3.         ...
4.         for i := range specialsbits {
5.                 ...
6.                 for j := uint(0); j < 8; j++ {
7.                         // 找到要处理的span（go内存使用的单位，你就当是“一块内存空间”就行）
8.                         s := ha.spans[arenaPage+uint(i)*8+j]
10.                         ...
11.             lock(&s.speciallock)
12.                         for sp := s.specials; sp != nil; sp = sp.next {
13.                                 if sp.kind != _KindSpecialFinalizer {
14.                                         continue
15.                                 }
16.                                 // don't mark finalized object, but scan it so we
17.                                 // retain everything it points to.
18.                 // spf是终结器本身
19.                                 spf := (*specialfinalizer)(unsafe.Pointer(sp))
20.                                 // A finalizer can be set for an inner byte of an object, find object beginning.
21.                                 p := s.base() + uintptr(spf.special.offset)/s.elemsize*s.elemsize
23.                                 // p是设置了终结器的对象
24.                 // 这里检查这个对象占用的内存上是否设置了跳过扫描的标记
25.                 // 设置了的话就不要继续扫描对象自己的子对象了
26.                                 if !s.spanclass.noscan() {
27.                                         scanobject(p, gcw)
28.                                 }
30.                                 // 这个span本身就是root对象，所以剩下的直接用scanblock处理
31.                                 scanblock(uintptr(unsafe.Pointer(&spf.fn)), goarch.PtrSize, &oneptrmask[0], gcw, nil)
32.                         }
33.                         unlock(&s.speciallock)
34.                 }
35.         }
36. }

复制代码

实在很简单，依旧是找到所有的对象，然后进行处置惩罚。然而我们看到了有意思的东西：s.spanclass.noscan()。
看起来这和是否跳过扫描有关。
但我们先不深入这个方法，为什么？因为终结器是被特殊处置惩罚的，没看完scanobject和greyobject之前我们不能断言这个方法是否控制着对对象的扫描。（实在解释上我已经告诉你就是这个东西控制的了，但假如你自己跟踪代码的话头一次看到这段代码的时间是不知道的）
所以我们接着看scanobject，这个函数是扫描对象的子对象的：

1. // runtime/mgcmark.go
2. func scanobject(b uintptr, gcw *gcWork) {
3.         // 先拿到还没扫描过的内存
4.         s := spanOfUnchecked(b)
5.         n := s.elemsize
6.     // n 表示mspan里有几个对象，在被这个函数检查的时候肯定不能是0
7.         if n == 0 {
8.                 throw("scanobject n == 0")
9.         }
10.         if s.spanclass.noscan() {
11.                 // 如果内存设置了noscan标志，就报错
12.                 throw("scanobject of a noscan object")
13.         }
15.         var tp typePointers
16.         if n > maxObletBytes {
17.                 // 大内存分割成不同的块放进工作队列，这样能被并行处理
18.                 if b == s.base() {
19.                         // 分割后入队
20.                         for oblet := b + maxObletBytes; oblet < s.base()+s.elemsize; oblet += maxObletBytes {
21.                                 if !gcw.putFast(oblet) {
22.                                         gcw.put(oblet)
23.                                 }
24.                         }
25.                 }
27.                 // 获取类型信息
28.         } else {
29.                 // 这里不重要
30.         }
32.         var scanSize uintptr
33.         for {
34.                 var addr uintptr
35.         // 获取子对象
36.         // 整个循环的退出条件就是next不再返回子对象的时候（没东西可继续扫描了）
37.                 if tp, addr = tp.nextFast(); addr == 0 {
38.                         if tp, addr = tp.next(); addr == 0 {
39.                                 break
40.                         }
41.                 }
43.                 // 拿到要处理的对象
44.                 scanSize = addr - b + goarch.PtrSize
45.                 obj := *(*uintptr)(unsafe.Pointer(addr))
47.                 // 排除nil和指向当前对象自身的指针
48.         // 后者属于可以被回收的循环引用，当前对象能不能回收不受这个指针影响
49.         // 因为如果当前对象不可访问了，那么它的字段自然也是不可能被访问到的，两者均从root不可达
50.         // 而如果这个指针是可达的，那么当前对象的字段被引用，当前对象也是不需要回收的
51.         // 所以指向当前对象本身的指针字段不需要处理
52.                 if obj != 0 && obj-b >= n {
53.                         if obj, span, objIndex := findObject(obj, b, addr-b); obj != 0 {
54.                                 greyobject(obj, b, addr-b, span, gcw, objIndex)
55.                         }
56.                 }
57.         }
58.         ...
59. }

复制代码

这个函数长归长，条理还是清晰的：

• 起首看看对象是否太大要把对象的内存分割成小块交给工作队列里的其他协程并行处置惩罚
  
• 接着扫描所有子对象，用greyobject标记这些对象
  

因为这个函数自己已经是在扫描了，所以不太会有“跳过”的相关的逻辑，而且你也看到了把这个函数放在不必要扫描子对象的对象上调用时会触发throw，throw会导致程序报错并退出实行。
所以机密就在greyobject里了。看看代码：

1. // runtime/mgcmark.go
2. func greyobject(obj, base, off uintptr, span *mspan, gcw *gcWork, objIndex uintptr) {
3.         ...
4.         if useCheckmark {
5.                 if setCheckmark(obj, base, off, mbits) {
6.                         // Already marked.
7.                         return
8.                 }
9.         } else {
10.                 ...
11.                 // If marked we have nothing to do.
12.                 if mbits.isMarked() {
13.                         return
14.                 }
15.                 mbits.setMarked()
17.                 ...
19.                 // 如果内存被标记为不需要进一步扫描，则会跳过后续的流程（内存会被放进gc扫描的工作队列里等着被取出来扫描）
20.                 if span.spanclass.noscan() {
21.                         ...
22.                         return
23.                 }
24.         }
25.         // 对象被放进工作队列等待扫描
26. }

复制代码

这个函数会先查抄对象是否已经被处置惩罚过，然后标记对象，接着查抄span上的noscan标志，设置了的话就返回调用，没有设置说明必要被进一步扫描，于是被放进工作队列，等着gcDrain大概它兄弟来处置惩罚。
现在我们可以得出结论了，会不会跳过扫描，全部由内存上是否设置noscan标志来控制，设置了就可以跳过。
至于在这块内存上的是map还是slice还是struct，没关系。
跳过扫描的具体流程

看了上面的代码，我想信你一定是懵的，跳过具体发生的流程是什么样的呢？
没关系，我们看两个例子就知道了。
第一个例子是一个顶层的全局的可跳过扫描的对象A，介于我们还没说noscan会在什么情况下被设置，所以我们先忽略A的具体类型，只要知道它可以跳过扫描即可。
A的扫描流程是如许的：

• gc开始运行，先标记root对象
  
• A就是root之一，所以它要么被scanblock处置惩罚要么被markrootSpan处置惩罚
  
• 假设A设置了终结器，又因为A是可跳过扫描子对象的，因此markrootSpan会直接调用scanblock
  
• scanblock会调用greyobject处置惩罚内存里的对象
  
• 因为A可跳过扫描，所以greyobject做完标记就返回了，A不会进入工作队列
  
• A的扫描结束，整个流程上不会有scanobject的调用
  

A的例子相对简单，现在我们假设有个不是root对象的对象B，B自己不可跳过扫描，B有一个子对象C可以跳过扫描。我们来看看C的扫描流程：

• 因为B并不是root对象，且不可跳过扫描，所以它作为某个root对象的子对象，现在肯定在gc工作队列里
  
• gcDrain从队列里拿到了B，于是交给了scanobject处置惩罚
  
• 我们假设B不是很大因此不会被分割（反正分割了也一样）
  
• scanobject把每个B的子对象都用greyobject处置惩罚，C也不破例
  
• 因为C可跳过扫描，所以greyobject做完标记就返回了，C不会进入工作队列
  
• C的扫描结束，整个流程上不会有对C的scanobject的调用
  

如许基本涵盖了所有的情况，一些我没单独说的比如“可跳过对象E是不可跳过root对象D的子对象”如许的情况，实际上和情况2没什么区别。
现在对象的子对象扫描是这么跳过的我们也知道了，只剩一个疑问了：noscan标志是怎么设置的？
noscan标志是怎么设置的

在深入之前，我们先来简单看下go的怎么分配内存的。完备讲解恐怕5篇长文也兜不住，所以我做些概念上的精简。
在go里，mspan是内存分配的基础单元，一个mspan上可以分配多个大小类似可以被归为一类的对象（比如13字节和14字节的对象都是一类，可以被分配到答应最大存储16字节对象的mspan上）。这个“类型”就叫mpan的sizeclass。一个简单的心智模型是把mspan当成一个能存大小相近的对象的列表。
为了加快内存分配，go会给每个线程预分配一块内存，然后按sizeclass分成多份，每份对应一个sizeclass的mspan。这个布局叫mcache。
当然了，总有对象的大小会超过所有mcache的sizeclass规定的范围，这个时间go就会像体系申请一大块内存，然后把内存交给mspan。
存储了span信息的比如sizeclass和noscan的布局叫spanClass。这个布局会作为字段存储在mspan的控制布局里。
知道了这些之后，我们就能看懂s.spanclass.noscan()了，它的意思就是查抄mspan的spanclass信息是否设置了不必要扫描子对象的标志。
而创建spanclass只能用makeSpanClass这个函数：

1. // runtime/mheap.go
2. type spanClass uint8
4. func makeSpanClass(sizeclass uint8, noscan bool) spanClass {
5.         return spanClass(sizeclass<<1) | spanClass(bool2int(noscan))
6. }

复制代码

slice中的元素的类型信息被传给了mallocgc。假如slice的元素不包含指针，那么slice是可以跳过扫描的。
map比力特殊，跳过扫描的是它的bucket，而bucket外界是看不到的：

1. // runtime/malloc.go
2. func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
3.         ...
4.     // size是指类型的大小
5.     // typ是需要创建的对象的类型信息，如果只是分配内存，typ要传nil
6.         // typ是否是空的或者typ是否包含有指针
7.         noscan := typ == nil || !typ.Pointers()
8.         if 如果size足够小可以从mspan上分配 {
9.                 if size满足要求可以用tinyallocator分配 {
10.                 } else {
11.                         // 计算sizeclass（size对应到哪一类span）
12.                         spc := makeSpanClass(sizeclass, noscan) // noscan是这里传进去的
13.                         span = c.alloc[spc] // 从mcache拿mspan
14.             v := nextFreeFast(span) // 从mspan真正拿到可用的内存
15.                         // 后面是把内存内容清零和维护gc信息等代码
16.                 }
17.         } else {
18.                 // 大对象分配
19.                 // mcache.allocLarge也调用makeSpanClass(0, noscan)，然后用mheap.alloc根据span的信息从系统申请内存
20.                 span = c.allocLarge(size, noscan) // noscan是这里传进去的
21.                 // 后面是把内存内容清零和维护gc信息等代码
22.         }
23. }

复制代码

可以看到要是键值对里都不包含指针的话，map就可以被跳过。
所以总结下，只要创建的对象不包含指针（例如数组/切片成员都是不包含指针的类型，map的键值对都不包含指针，布局体所有字段不包含指针）大概只是单纯分配块内存（makeslicecopy里分配一块内存然后再把数据copy进去的时间会判断element里包不包含指针，不包含的时间会传nil给mallocgc），noscan就会被设置。
现在所有的疑问都解决了：noscan是内存分配时根据类型信息来设置的；能跳过扫描的不只是map，符合条件的类型不管是slice、map还是struct都可以。
优化带来的提升

说了这么多，这个优化带来的提升有多少呢？
看个例子：

1. // runtime/slice.go
2. func makeslice(et *_type, len, cap int) unsafe.Pointer {
3.         mem, overflow := math.MulUintptr(et.Size_, uintptr(cap))
4.         if overflow || mem > maxAlloc || len < 0 || len > cap {
5.                 // NOTE: Produce a 'len out of range' error instead of a
6.                 // 'cap out of range' error when someone does make([]T, bignumber).
7.                 // 'cap out of range' is true too, but since the cap is only being
8.                 // supplied implicitly, saying len is clearer.
9.                 // See golang.org/issue/4085.
10.                 mem, overflow := math.MulUintptr(et.Size_, uintptr(len))
11.                 if overflow || mem > maxAlloc || len < 0 {
12.                         panicmakeslicelen()
13.                 }
14.                 panicmakeslicecap()
15.         }
17.         return mallocgc(mem, et, true)
18. }

复制代码

我们分别创建20个包含10000个int64大概*int64的slice（两个类型在x64体系上都是8字节大小），然后手动触发一次GC。为了让效果更正确，我们还在测试开始前禁用了自动触发的gc，而且我们创建的slice的长度和slice里元素的大小都是一样的，所以总体来说效果应该比力接近真实的gc回收内存时的性能。
这是效果：

1. // runtime/map.go
2. // 调用链：makemap -> makeBucketArray -> newarray -> mallocgc
3. func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
4.         base := bucketShift(b)
5.         nbuckets := base
6.         // For small b, overflow buckets are unlikely.
7.         // Avoid the overhead of the calculation.
8.         if b >= 4 {
9.                 // Add on the estimated number of overflow buckets
10.                 // required to insert the median number of elements
11.                 // used with this value of b.
12.                 nbuckets += bucketShift(b - 4)
13.                 sz := t.Bucket.Size_ * nbuckets
14.                 up := roundupsize(sz, !t.Bucket.Pointers())
15.                 if up != sz {
16.                         nbuckets = up / t.Bucket.Size_
17.                 }
18.         }
20.         if dirtyalloc == nil {
21.         // t.Bucket.Pointers() 返回键值对中是否包含指针
22.                 buckets = newarray(t.Bucket, int(nbuckets))
23.         } else {
24.                 // dirtyalloc was previously generated by
25.                 // the above newarray(t.Bucket, int(nbuckets))
26.                 // but may not be empty.
27.                 buckets = dirtyalloc
28.                 size := t.Bucket.Size_ * nbuckets
29.                 if t.Bucket.Pointers() {
30.                         memclrHasPointers(buckets, size)
31.                 } else {
32.                         memclrNoHeapPointers(buckets, size)
33.                 }
34.         }
36.         if base != nbuckets {
37.                 // We preallocated some overflow buckets.
38.                 // To keep the overhead of tracking these overflow buckets to a minimum,
39.                 // we use the convention that if a preallocated overflow bucket's overflow
40.                 // pointer is nil, then there are more available by bumping the pointer.
41.                 // We need a safe non-nil pointer for the last overflow bucket; just use buckets.
42.                 nextOverflow = (*bmap)(add(buckets, base*uintptr(t.BucketSize)))
43.                 last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.BucketSize)))
44.                 last.setoverflow(t, (*bmap)(buckets))
45.         }
46.         return buckets, nextOverflow
47. }
49. func newarray(typ *_type, n int) unsafe.Pointer {
50.         if n == 1 {
51.                 return mallocgc(typ.Size_, typ, true)
52.         }
53.         mem, overflow := math.MulUintptr(typ.Size_, uintptr(n))
54.         if overflow || mem > maxAlloc || n < 0 {
55.                 panic(plainError("runtime: allocation size out of range"))
56.         }
57.         return mallocgc(mem, typ, true)
58. }

复制代码

内存用量大家都一样，但存指针的时间速度慢了五分之一。slice越大差距也会越大。可见跳过扫描带来的提升还是很大的。
别的少用指针还有助于增加数据的局部性，不但仅是惠及gc扫描。
如何使用这一优化

最后我们看看如何使用这一优化。
少用指针可以减轻gc压力大家都知道，但有一些“不得不用”指针的时间。
以一个本地cache为例：

1. var a int64 = 1000
3. func generateIntSlice(n int64) []int64 {
4.         ret := make([]int64, 0, n)
5.         for i := int64(0); i < n; i++ {
6.                 ret = append(ret, a)
7.         }
8.         return ret
9. }
11. func generatePtrSlice(n int64) []*int64 {
12.         ret := make([]*int64, 0, n)
13.         for i := int64(0); i < n; i++ {
14.                 ret = append(ret, &a)
15.         }
16.         return ret
17. }
19. func BenchmarkGCScan1(b *testing.B) {
20.         defer debug.SetGCPercent(debug.SetGCPercent(-1)) // 测试期间禁止自动gc
21.         for i := 0; i < b.N; i++ {
22.                 for j := 0; j < 20; j++ {
23.                         generatePtrSlice(10000)
24.                 }
25.                 runtime.GC()
26.         }
27. }
29. func BenchmarkGCScan2(b *testing.B) {
30.         defer debug.SetGCPercent(debug.SetGCPercent(-1))
31.         for i := 0; i < b.N; i++ {
32.                 for j := 0; j < 20; j++ {
33.                         generateIntSlice(10000)
34.                 }
35.                 runtime.GC()
36.         }
37. }

复制代码

值必要用指针是有两个原因，一是map的元素不能取地址，假如我们想要cache里的数据可以自由使用的话那就不得不用临时变量加复制，如许假如我们想更新值的时间就会很麻烦；二是假如值很大的话复制带来的开销会很大，用cache就是想提升性能呢反过来降落了怎么行。
但这么做就会导致Cache.m里的每一个键值对要被扫描，假如键值对很多的话性能会十分感人。
如许看起来是“不得不用指针”的场景。真的是如许吗？考虑到cache自己就是空间换时间的做法，我们不妨再多用点空间：

1. goos: windows
2. goarch: amd64
3. cpu: Intel(R) Core(TM) i5-10200H CPU @ 2.40GHz
4.          │   old.txt   │               new.txt               │
5.          │   sec/op    │   sec/op     vs base                │
6. GCScan-8   379.0µ ± 2%   298.0µ ± 2%  -21.51% (p=0.000 n=10)
8.          │   old.txt    │            new.txt             │
9.          │     B/op     │     B/op      vs base          │
10. GCScan-8   1.563Mi ± 0%   1.563Mi ± 0%  ~ (p=0.438 n=10)
12.          │  old.txt   │            new.txt             │
13.          │ allocs/op  │ allocs/op   vs base            │
14. GCScan-8   20.00 ± 0%   20.00 ± 0%  ~ (p=1.000 n=10) ¹
15. ¹ all samples are equal

复制代码

我们用一个slice来存所有的值，然后再把key映射到值在slice中的索引上。对于slice的元素，我们是可以取地址的，因此可以简单拿到值的指针，对于值的更新也可以基于这个Get拿到的指针，时间复杂度不变，简单又方便。
然后我们再来看，现在buf和m都没有指针了，只要K和V不包含指针，那么不管我们的cache里存了多少东西对gc来说都只要看看外层的Cache对象是否存活就够了。
但是这么做会有代价：
<ul>Get会稍微慢一点，因为不但要做额外的查抄，还必要从两个不同的数据布局里拿数据，对缓存不友好
存数据进Cache的时间不可制止地必要一次复制
Get返回的指针没有稳定性，在底层的buf扩容后就会失效
删除元素会很慢，这怪我们用了slice，你可以再多浪费点内存用墓碑标志来模仿删除大概干脆不提供删除功能（不好做就干脆不做，这是非常golang的做法
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。