// runtime/mgcmark.go

	// 負責gc掃描的函數(shù)，還有個它的兄弟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)

	// 檢查自己是否需要被中斷，需要的場合函數(shù)會直接跳到收尾工作然后返回

	}

	}

	


	// 從工作隊列里拿需要掃描的對象進行處理

	for !(gp.preempt && (preemptible || sched.gcwaiting.Load() || pp.runSafePointFn != 0)) {

	b := gcw.tryGetFast() // 從工作隊列拿對象

	scanobject(b, gcw)

	...

	}

	...

	}

// runtime/mgcmark.go
func markrootSpans(gcw *gcWork, shard int) {
...
for i := range specialsbits {
...
for j := uint(0); j < 8; j++ {
// 找到要處理的span（go內(nèi)存使用的單位，你就當是“一塊內(nèi)存空間”就行）
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是終結(jié)器本身
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是設(shè)置了終結(jié)器的對象
// 這里檢查這個對象占用的內(nèi)存上是否設(shè)置了跳過掃描的標記
// 設(shè)置了的話就不要繼續(xù)掃描對象自己的子對象了
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)
}
}
}

	// runtime/mgcmark.go

	func scanobject(b uintptr, gcw *gcWork) {

	// 先拿到還沒掃描過的內(nèi)存

	s := spanOfUnchecked(b)

	n := s.elemsize

	// n 表示mspan里有幾個對象，在被這個函數(shù)檢查的時候肯定不能是0

	if n == 0 {

	throw("scanobject n == 0")

	}

	if s.spanclass.noscan() {

	// 如果內(nèi)存設(shè)置了noscan標志，就報錯

	throw("scanobject of a noscan object")

	}

	


	var tp typePointers

	if n > maxObletBytes {

	// 大內(nèi)存分割成不同的塊放進工作隊列，這樣能被并行處理

	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

	// 獲取子對象

	// 整個循環(huán)的退出條件就是next不再返回子對象的時候（沒東西可繼續(xù)掃描了）

	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和指向當前對象自身的指針

	// 后者屬于可以被回收的循環(huán)引用，當前對象能不能回收不受這個指針影響

	// 因為如果當前對象不可訪問了，那么它的字段自然也是不可能被訪問到的，兩者均從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)

	}

	}

	}

	...

	}

	// 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()

	


	...

	


	// 如果內(nèi)存被標記為不需要進一步掃描，則會跳過后續(xù)的流程（內(nèi)存會被放進gc掃描的工作隊列里等著被取出來掃描）

	if span.spanclass.noscan() {

	...

	return

	}

	}

	// 對象被放進工作隊列等待掃描

	}

	// runtime/mheap.go

	type spanClass uint8

	


	func makeSpanClass(sizeclass uint8, noscan bool) spanClass {

	return spanClass(sizeclass<<1) | spanClass(bool2int(noscan))

	}

	// runtime/malloc.go

	func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {

	...

	// size是指類型的大小

	// typ是需要創(chuàng)建的對象的類型信息，如果只是分配內(nèi)存，typ要傳nil

	// typ是否是空的或者typ是否包含有指針

	noscan := typ == nil || !typ.Pointers()

	if 如果size足夠小可以從mspan上分配 {

	if size滿足要求可以用tinyallocator分配 {

	} else {

	// 計算sizeclass（size對應(yīng)到哪一類span）

	spc := makeSpanClass(sizeclass, noscan) // noscan是這里傳進去的

	span = c.alloc[spc] // 從mcache拿mspan

	v := nextFreeFast(span) // 從mspan真正拿到可用的內(nèi)存

	// 后面是把內(nèi)存內(nèi)容清零和維護gc信息等代碼

	}

	} else {

	// 大對象分配

	// mcache.allocLarge也調(diào)用makeSpanClass(0, noscan)，然后用mheap.alloc根據(jù)span的信息從系統(tǒng)申請內(nèi)存

	span = c.allocLarge(size, noscan) // noscan是這里傳進去的

	// 后面是把內(nèi)存內(nèi)容清零和維護gc信息等代碼

	}

	}

	// 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)

	}

// runtime/map.go
	// 調(diào)用鏈：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)
	}

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()
	}
	}

	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) 1

	1 all samples are equal

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
	}

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里存的數(shù)據(jù)取地址
	}
	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
	}