今天講一個常見的gc compiler（也就是官方版本的go編譯器和runtime）在垃圾回收的掃描標記階段做的優化。 我對這個優化的描述印象最深的是在bigcache的註釋里，大致內容是如果map的鍵值都不包含指針，那麼gc掃描的時候不管這個map多大都不會深入掃描map內部存儲的數據，只檢查ma ...
今天講一個常見的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的代碼開始看，於是很快就有了收穫:
// runtime/mgcmark.go
// 負責gc掃描的函數，還有個它的兄弟gcDrainN，代碼差不多就不放了
func gcDrain(gcw *gcWork, flags gcDrainFlags) {
...
// 先標記所有root對象，檢查對象是否存活就是從這開始的
if work.markrootNext < work.markrootJobs {
for !(gp.preempt && (preemptible || sched.gcwaiting.Load() || pp.runSafePointFn != 0)) {
markroot(gcw, job, flushBgCredit)
// 檢查自己是否需要被中斷，需要的場合函數會直接跳到收尾工作然後返回
}
}
// 從工作隊列里拿需要掃描的對象進行處理
for !(gp.preempt && (preemptible || sched.gcwaiting.Load() || pp.runSafePointFn != 0)) {
b := gcw.tryGetFast() // 從工作隊列拿對象
scanobject(b, gcw)
...
}
...
}
流程不考慮中斷、數據統計和校驗的話還是很簡單的，就是先標記掃描的起點，然後從gcw這個工作隊列里拿東西出來處理，直到工作隊列里再也沒數據了為止。
markroot也很簡單，根據root對象的種類，它會調用scanblock或者markrootSpans。其中scanblock會調用greyobject來標記待處理的對象。因此稍微看看markrootSpans即可。
markrootSpans是用來處理那些存放設置了終結器的對象的記憶體的：
// runtime/mgcmark.go
func markrootSpans(gcw *gcWork, shard int) {
...
for i := range specialsbits {
...
for j := uint(0); j < 8; j++ {
// 找到要處理的span（go記憶體使用的單位，你就當是“一塊記憶體空間”就行）
s := ha.spans[arenaPage+uint(i)*8+j]
...
lock(&s.speciallock)
for sp := s.specials; sp != nil; sp = sp.next {
if sp.kind != _KindSpecialFinalizer {
continue
}
// don't mark finalized object, but scan it so we
// retain everything it points to.
// spf是終結器本身
spf := (*specialfinalizer)(unsafe.Pointer(sp))
// A finalizer can be set for an inner byte of an object, find object beginning.
p := s.base() + uintptr(spf.special.offset)/s.elemsize*s.elemsize
// p是設置了終結器的對象
// 這裡檢查這個對象占用的記憶體上是否設置了跳過掃描的標記
// 設置了的話就不要繼續掃描對象自己的子對象了
if !s.spanclass.noscan() {
scanobject(p, gcw)
}
// 這個span本身就是root對象，所以剩下的直接用scanblock處理
scanblock(uintptr(unsafe.Pointer(&spf.fn)), goarch.PtrSize, &oneptrmask[0], gcw, nil)
}
unlock(&s.speciallock)
}
}
}
其實很簡單，依舊是找到所有的對象，然後進行處理。然而我們看到了有意思的東西：s.spanclass.noscan()。
看起來這和是否跳過掃描有關。
但我們先不深入這個方法，為什麼？因為終結器是被特殊處理的，沒看完scanobject和greyobject之前我們不能斷言這個方法是否控制著對對象的掃描。（其實註釋上我已經告訴你就是這個東西控制的了，但如果你自己跟蹤代碼的話頭一次看到這段代碼的時候是不知道的）
所以我們接著看scanobject，這個函數是掃描對象的子對象的：
// runtime/mgcmark.go
func scanobject(b uintptr, gcw *gcWork) {
// 先拿到還沒掃描過的記憶體
s := spanOfUnchecked(b)
n := s.elemsize
// n 表示mspan里有幾個對象，在被這個函數檢查的時候肯定不能是0
if n == 0 {
throw("scanobject n == 0")
}
if s.spanclass.noscan() {
// 如果記憶體設置了noscan標誌，就報錯
throw("scanobject of a noscan object")
}
var tp typePointers
if n > maxObletBytes {
// 大記憶體分割成不同的塊放進工作隊列，這樣能被並行處理
if b == s.base() {
// 分割後入隊
for oblet := b + maxObletBytes; oblet < s.base()+s.elemsize; oblet += maxObletBytes {
if !gcw.putFast(oblet) {
gcw.put(oblet)
}
}
}
// 獲取類型信息
} else {
// 這裡不重要
}
var scanSize uintptr
for {
var addr uintptr
// 獲取子對象
// 整個迴圈的退出條件就是next不再返回子對象的時候（沒東西可繼續掃描了）
if tp, addr = tp.nextFast(); addr == 0 {
if tp, addr = tp.next(); addr == 0 {
break
}
}
// 拿到要處理的對象
scanSize = addr - b + goarch.PtrSize
obj := *(*uintptr)(unsafe.Pointer(addr))
// 排除nil和指向當前對象自身的指針
// 後者屬於可以被回收的迴圈引用，當前對象能不能回收不受這個指針影響
// 因為如果當前對象不可訪問了，那麼它的欄位自然也是不可能被訪問到的，兩者均從root不可達
// 而如果這個指針是可達的，那麼當前對象的欄位被引用，當前對象也是不需要回收的
// 所以指向當前對象本身的指針欄位不需要處理
if obj != 0 && obj-b >= n {
if obj, span, objIndex := findObject(obj, b, addr-b); obj != 0 {
greyobject(obj, b, addr-b, span, gcw, objIndex)
}
}
}
...
}
這個函數長歸長，條理還是清晰的：
- 首先看看對象是否太大要把對象的記憶體分割成小塊交給工作隊列里的其他協程並行處理
- 接著掃描所有子對象，用
greyobject標記這些對象
因為這個函數本身已經是在掃描了，所以不太會有“跳過”的相關的邏輯，而且你也看到了把這個函數放在不需要掃描子對象的對象上調用時會觸發throw，throw會導致程式報錯並退出執行。
所以秘密就在greyobject里了。看看代碼：
// runtime/mgcmark.go
func greyobject(obj, base, off uintptr, span *mspan, gcw *gcWork, objIndex uintptr) {
...
if useCheckmark {
if setCheckmark(obj, base, off, mbits) {
// Already marked.
return
}
} else {
...
// If marked we have nothing to do.
if mbits.isMarked() {
return
}
mbits.setMarked()
...
// 如果記憶體被標記為不需要進一步掃描，則會跳過後續的流程（記憶體會被放進gc掃描的工作隊列里等著被取出來掃描）
if span.spanclass.noscan() {
...
return
}
}
// 對象被放進工作隊列等待掃描
}
這個函數會先檢查對象是否已經被處理過，然後標記對象，接著檢查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這個函數：
// runtime/mheap.go
type spanClass uint8
func makeSpanClass(sizeclass uint8, noscan bool) spanClass {
return spanClass(sizeclass<<1) | spanClass(bool2int(noscan))
}
現在問題簡單了，我們只要追蹤誰調用了這個函數就行，以及我們還知道額外的信息：這些調用者還需要從mcache或者系統申請記憶體獲得mspan結構。這樣一下範圍就收縮了。
按上面的思路，我們很快就找到了go分配記憶體給對象的入口之一mallocgc：
// runtime/malloc.go
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
...
// size是指類型的大小
// typ是需要創建的對象的類型信息，如果只是分配記憶體，typ要傳nil
// typ是否是空的或者typ是否包含有指針
noscan := typ == nil || !typ.Pointers()
if 如果size足夠小可以從mspan上分配 {
if size滿足要求可以用tinyallocator分配 {
} else {
// 計算sizeclass（size對應到哪一類span）
spc := makeSpanClass(sizeclass, noscan) // noscan是這裡傳進去的
span = c.alloc[spc] // 從mcache拿mspan
v := nextFreeFast(span) // 從mspan真正拿到可用的記憶體
// 後面是把記憶體內容清零和維護gc信息等代碼
}
} else {
// 大對象分配
// mcache.allocLarge也調用makeSpanClass(0, noscan)，然後用mheap.alloc根據span的信息從系統申請記憶體
span = c.allocLarge(size, noscan) // noscan是這裡傳進去的
// 後面是把記憶體內容清零和維護gc信息等代碼
}
}
即使sizeclass是一樣的，因為noscan的值不一樣，兩個spanClass的值也是不一樣的。對於可跳過掃描的大對象來說，會把為這個對象分配的記憶體標記為noscan；對於可跳過的小對象來說，會直接把這個小對象放在mcache提前分配的不需要深入掃描的記憶體區域上。
那麼這個mallocgc又是誰調用的？答案太多了，因為new，make都會用到它。我們用slice和map做例子看看。
首先是slice。這個非常簡單，創建slice的入口是makeslice：
// runtime/slice.go
func makeslice(et *_type, len, cap int) unsafe.Pointer {
mem, overflow := math.MulUintptr(et.Size_, uintptr(cap))
if overflow || mem > maxAlloc || len < 0 || len > cap {
// NOTE: Produce a 'len out of range' error instead of a
// 'cap out of range' error when someone does make([]T, bignumber).
// 'cap out of range' is true too, but since the cap is only being
// supplied implicitly, saying len is clearer.
// See golang.org/issue/4085.
mem, overflow := math.MulUintptr(et.Size_, uintptr(len))
if overflow || mem > maxAlloc || len < 0 {
panicmakeslicelen()
}
panicmakeslicecap()
}
return mallocgc(mem, et, true)
}
slice中的元素的類型信息被傳給了mallocgc。如果slice的元素不包含指針，那麼slice是可以跳過掃描的。
map比較特殊，跳過掃描的是它的bucket，而bucket外界是看不到的：
// runtime/map.go
// 調用鏈：makemap -> makeBucketArray -> newarray -> mallocgc
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
base := bucketShift(b)
nbuckets := base
// For small b, overflow buckets are unlikely.
// Avoid the overhead of the calculation.
if b >= 4 {
// Add on the estimated number of overflow buckets
// required to insert the median number of elements
// used with this value of b.
nbuckets += bucketShift(b - 4)
sz := t.Bucket.Size_ * nbuckets
up := roundupsize(sz, !t.Bucket.Pointers())
if up != sz {
nbuckets = up / t.Bucket.Size_
}
}
if dirtyalloc == nil {
// t.Bucket.Pointers() 返回鍵值對中是否包含指針
buckets = newarray(t.Bucket, int(nbuckets))
} else {
// dirtyalloc was previously generated by
// the above newarray(t.Bucket, int(nbuckets))
// but may not be empty.
buckets = dirtyalloc
size := t.Bucket.Size_ * nbuckets
if t.Bucket.Pointers() {
memclrHasPointers(buckets, size)
} else {
memclrNoHeapPointers(buckets, size)
}
}
if base != nbuckets {
// We preallocated some overflow buckets.
// To keep the overhead of tracking these overflow buckets to a minimum,
// we use the convention that if a preallocated overflow bucket's overflow
// pointer is nil, then there are more available by bumping the pointer.
// We need a safe non-nil pointer for the last overflow bucket; just use buckets.
nextOverflow = (*bmap)(add(buckets, base*uintptr(t.BucketSize)))
last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.BucketSize)))
last.setoverflow(t, (*bmap)(buckets))
}
return buckets, nextOverflow
}
func newarray(typ *_type, n int) unsafe.Pointer {
if n == 1 {
return mallocgc(typ.Size_, typ, true)
}
mem, overflow := math.MulUintptr(typ.Size_, uintptr(n))
if overflow || mem > maxAlloc || n < 0 {
panic(plainError("runtime: allocation size out of range"))
}
return mallocgc(mem, typ, true)
}
可以看到要是鍵值對里都不包含指針的話，map就可以被跳過。
所以總結下，只要創建的對象不包含指針（例如數組/切片成員都是不包含指針的類型，map的鍵值對都不包含指針，結構體所有欄位不包含指針）或者只是單純分配塊記憶體（makeslicecopy里分配一塊記憶體然後再把數據copy進去的時候會判斷element里包不包含指針，不包含的時候會傳nil給mallocgc），noscan就會被設置。
現在所有的疑問都解決了：noscan是記憶體分配時根據類型信息來設置的；能跳過掃描的不只是map，符合條件的類型不管是slice、map還是struct都可以。
優化帶來的提升
說了這麼多，這個優化帶來的提升有多少呢？
看個例子：
var a int64 = 1000
func generateIntSlice(n int64) []int64 {
ret := make([]int64, 0, n)
for i := int64(0); i < n; i++ {
ret = append(ret, a)
}
return ret
}
func generatePtrSlice(n int64) []*int64 {
ret := make([]*int64, 0, n)
for i := int64(0); i < n; i++ {
ret = append(ret, &a)
}
return ret
}
func BenchmarkGCScan1(b *testing.B) {
defer debug.SetGCPercent(debug.SetGCPercent(-1)) // 測試期間禁止自動gc
for i := 0; i < b.N; i++ {
for j := 0; j < 20; j++ {
generatePtrSlice(10000)
}
runtime.GC()
}
}
func BenchmarkGCScan2(b *testing.B) {
defer debug.SetGCPercent(debug.SetGCPercent(-1))
for i := 0; i < b.N; i++ {
for j := 0; j < 20; j++ {
generateIntSlice(10000)
}
runtime.GC()
}
}
我們分別創建20個包含10000個int64或者*int64的slice（兩個類型在x64系統上都是8位元組大小），然後手動觸發一次GC。為了讓結果更準確，我們還在測試開始前禁用了自動觸發的gc，而且我們創建的slice的長度和slice里元素的大小都是一樣的，所以總體來說結果應該比較接近真實的gc回收記憶體時的性能。
這是結果：
goos: windows
goarch: amd64
cpu: Intel(R) Core(TM) i5-10200H CPU @ 2.40GHz
│ old.txt │ new.txt │
│ sec/op │ sec/op vs base │
GCScan-8 379.0µ ± 2% 298.0µ ± 2% -21.51% (p=0.000 n=10)
│ old.txt │ new.txt │
│ B/op │ B/op vs base │
GCScan-8 1.563Mi ± 0% 1.563Mi ± 0% ~ (p=0.438 n=10)
│ old.txt │ new.txt │
│ allocs/op │ allocs/op vs base │
GCScan-8 20.00 ± 0% 20.00 ± 0% ~ (p=1.000 n=10) ¹
¹ all samples are equal
記憶體用量大家都一樣，但存指針的時候速度慢了五分之一。slice越大差距也會越大。可見跳過掃描帶來的提升還是很大的。
另外少用指針還有助於增加數據的局部性，不僅僅是惠及gc掃描。
如何利用這一優化
最後我們看看如何利用這一優化。
少用指針可以減輕gc壓力大家都知道，但有一些“不得不用”指針的時候。
以一個本地cache為例：
type Cache[K comparable, V any] struct {
m map[K]*V
}
func (c *Cache[K, V]) Get(key K) *V {
return c.m[key]
}
func (c *Cache[K, V]) Set(key Key, value *V) {
c.m[key] = value
}
值需要用指針是有兩個原因，一是map的元素不能取地址，如果我們想要cache里的數據可以自由使用的話那就不得不用臨時變數加複製，這樣如果我們想更新值的時候就會很麻煩；二是如果值很大的話複製帶來的開銷會很大，用cache就是想提升性能呢反過來下降了怎麼行。
但這麼做就會導致Cache.m里的每一個鍵值對要被掃描，如果鍵值對很多的話性能會十分感人。
這樣看起來是“不得不用指針”的場景。真的是這樣嗎？考慮到cache本身就是空間換時間的做法，我們不妨再多用點空間：
type index = int
type Cache[K comparable, V any] struct {
buf []V
m map[K]index
}
func (c *Cache[K, V]) Get(key K) *V {
idx, ok := c.m[key]
if !ok {
return nil
}
return &c.buf[idx] // 可以對slice里存的數據取地址
}
func (c *Cache[K, V]) Set(key Key, value V) {
idx, ok := c.m[key]
if !ok {
// 新建
c.m[key] = len(c.buf)
c.buf = append(c.buf, value)
return
}
// 覆蓋已添加的
c.buf[idx] = value
}
我們用一個slice來存所有的值，然後再把key映射到值在slice中的索引上。對於slice的元素，我們是可以取地址的，因此可以簡單拿到值的指針，對於值的更新也可以基於這個Get拿到的指針，時間複雜度不變，簡單又方便。
然後我們再來看，現在buf和m都沒有指針了，只要K和V不包含指針，那麼不管我們的cache里存了多少東西對gc來說都只要看看外層的Cache對象是否存活就夠了。
但是這麼做會有代價：
- Get會稍微慢一點，因為不僅要做額外的檢查，還需要從兩個不同的數據結構里拿數據，對緩存不友好
- 存數據進Cache的時候不可避免地需要一次複製
- Get返回的指針沒有穩定性，在底層的buf擴容後就會失效
- 刪除元素會很慢，這怪我們用了slice而且需要維護map里的映射關係，解決方法倒是不少，比如你可以把待刪除元素和slice結尾的元素交換這樣slice里的其他元素不用移動map也只要遍歷一次，又比如你可以再多浪費點記憶體用墓碑標誌來模擬刪除或者乾脆不提供刪除功能（不好做就乾脆不做，這是非常golang的做法
