最近在看左神新書 《Go 語言設(shè)計(jì)與實(shí)現(xiàn)》的垃圾收集器時(shí)產(chǎn)生一個(gè)疑惑，花了點(diǎn)時(shí)間搞清楚了記錄一下。
創(chuàng)新互聯(lián)建站專業(yè)為企業(yè)提供扎魯特旗網(wǎng)站建設(shè)、扎魯特旗做網(wǎng)站、扎魯特旗網(wǎng)站設(shè)計(jì)、扎魯特旗網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計(jì)與制作、扎魯特旗企業(yè)網(wǎng)站模板建站服務(wù)，十余年扎魯特旗做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。
Go 語言垃圾回收的實(shí)現(xiàn)使用了標(biāo)記清除算法，將對(duì)象的狀態(tài)抽象成黑色（活躍對(duì)象）、灰色（活躍對(duì)象中間狀態(tài)）、白色（潛在垃圾對(duì)象也是所有對(duì)象的默認(rèn)狀態(tài)）三種，注意沒有具體的字段標(biāo)記顏色。
整個(gè)標(biāo)記過程就是把白色對(duì)象標(biāo)黑的過程：
1.首先將 ROOT 根對(duì)象（包括全局變量、goroutine 棧上的對(duì)象等）放入到灰色集合
2.選一個(gè)灰色對(duì)象，標(biāo)成黑色，將所有可達(dá)的子對(duì)象放入到灰色集合
3.重復(fù)2的步驟，直到灰色集合中為空
下圖是書上的插圖，看上去是一個(gè)典型的深度優(yōu)先搜索的算法。
下圖是劉丹冰寫的《Golang 修養(yǎng)之路》的插圖，看上去是一個(gè)典型的廣度優(yōu)先搜索的算法。
我疑惑的點(diǎn)在于這個(gè)標(biāo)記過程是深度優(yōu)先算法還是廣度優(yōu)先算法，因?yàn)楹芏辔恼虏┛蛯?duì)此都沒有很清楚的說明，作為學(xué)習(xí)者這種細(xì)節(jié)其實(shí)也不影響對(duì)整個(gè) GC 流程的理解，但是這種細(xì)節(jié)我非常喜歡扣：）
對(duì)著書和源碼摸索著大致找到了一個(gè)結(jié)果是深度優(yōu)先。下面看下大致的過程，源碼基于1.15.2版本：
gcStart 是 Go 語言三種條件觸發(fā) GC 的共同入口
啟動(dòng)后臺(tái)標(biāo)記任務(wù)
為每個(gè)處理器創(chuàng)建用于執(zhí)行后臺(tái)標(biāo)記任務(wù)的 Goroutine
上面休眠的 G 會(huì)在調(diào)度循環(huán)中檢查并喚醒執(zhí)行
執(zhí)行標(biāo)記
gcw 是每個(gè) P 獨(dú)有的所以不用擔(dān)心并發(fā)的問題 和 GMP、mcache 一樣設(shè)計(jì)，減少鎖競(jìng)爭
嘗試在全局列表中獲取一個(gè)不為空的 buf
這是官方實(shí)現(xiàn)的無鎖隊(duì)列：）漲見識(shí)了，for 循環(huán)加原子操作實(shí)現(xiàn)棧的 pop
到這里從灰色集合中獲取待掃描的對(duì)象邏輯說完了。找到對(duì)象了接著就是 scanobject(b, gcw) 了，里面有兩段邏輯要注意
根據(jù)索引位置找到對(duì)象進(jìn)行標(biāo)色
嘗試存入 gcwork 的緩存中，或全局隊(duì)列中
無鎖隊(duì)列，for 循環(huán)加原子操作實(shí)現(xiàn)棧的 push
到這里把灰色對(duì)象標(biāo)黑就完成了，又放回灰色集合接著掃下一個(gè)指針。
Go 語言設(shè)計(jì)與實(shí)現(xiàn) 垃圾收集器
Golang三色標(biāo)記+混合寫屏障GC模式全分析
Go 由于不支持泛型而臭名昭著，但最近，泛型已接近成為現(xiàn)實(shí)。Go 團(tuán)隊(duì)實(shí)施了一個(gè)看起來比較穩(wěn)定的設(shè)計(jì)草案，并且正以源到源翻譯器原型的形式獲得關(guān)注。本文講述的是泛型的最新設(shè)計(jì)，以及如何自己嘗試泛型。
例子
FIFO Stack
假設(shè)你要?jiǎng)?chuàng)建一個(gè)先進(jìn)先出堆棧。沒有泛型，你可能會(huì)這樣實(shí)現(xiàn)：
type?Stack?[]interface{}func?(s?Stack)?Peek()?interface{}?{
return?s[len(s)-1]
}
func?(s?*Stack)?Pop()?{
*s?=?(*s)[:
len(*s)-1]
}
func?(s?*Stack)?Push(value?interface{})?{
*s?=?
append(*s,?value)
}
但是，這里存在一個(gè)問題：每當(dāng)你 Peek 項(xiàng)時(shí)，都必須使用類型斷言將其從 interface{} 轉(zhuǎn)換為你需要的類型。如果你的堆棧是 *MyObject 的堆棧，則意味著很多 s.Peek().(*MyObject)這樣的代碼。這不僅讓人眼花繚亂，而且還可能引發(fā)錯(cuò)誤。比如忘記 * 怎么辦？或者如果您輸入錯(cuò)誤的類型怎么辦？s.Push(MyObject{})` 可以順利編譯，而且你可能不會(huì)發(fā)現(xiàn)到自己的錯(cuò)誤，直到它影響到你的整個(gè)服務(wù)為止。
通常，使用 interface{} 是相對(duì)危險(xiǎn)的。使用更多受限制的類型總是更安全，因?yàn)榭梢栽诰幾g時(shí)而不是運(yùn)行時(shí)發(fā)現(xiàn)問題。
泛型通過允許類型具有類型參數(shù)來解決此問題：
type?Stack(type?T)?[]Tfunc?(s?Stack(T))?Peek()?T?{
return?s[len(s)-1]
}
func?(s?*Stack(T))?Pop()?{
*s?=?(*s)[:
len(*s)-1]
}
func?(s?*Stack(T))?Push(value?T)?{
*s?=?
append(*s,?value)
}
這會(huì)向 Stack 添加一個(gè)類型參數(shù)，從而完全不需要 interface{}。現(xiàn)在，當(dāng)你使用 Peek() 時(shí)，返回的值已經(jīng)是原始類型，并且沒有機(jī)會(huì)返回錯(cuò)誤的值類型。這種方式更安全，更容易使用。（譯注：就是看起來更丑陋，^-^）
此外，泛型代碼通常更易于編譯器優(yōu)化，從而獲得更好的性能（以二進(jìn)制大小為代價(jià)）。如果我們對(duì)上面的非泛型代碼和泛型代碼進(jìn)行基準(zhǔn)測(cè)試，我們可以看到區(qū)別：
type?MyObject?struct?{
X?
int
}
var?sink?MyObjectfunc?BenchmarkGo1(b?*testing.B)?{
for?i?:=?0;?i??b.N;?i++?{
var?s?Stack
s.Push(MyObject{})
s.Push(MyObject{})
s.Pop()
sink?=?s.Peek().(MyObject)
}
}
func?BenchmarkGo2(b?*testing.B)?{
for?i?:=?0;?i??b.N;?i++?{
var?s?Stack(MyObject)
s.Push(MyObject{})
s.Push(MyObject{})
s.Pop()
sink?=?s.Peek()
}
}
結(jié)果：
BenchmarkGo1BenchmarkGo1-16?????12837528?????????87.0?ns/op???????48?B/op????????2?allocs/opBenchmarkGo2BenchmarkGo2-16?????28406479?????????41.9?ns/op???????24?B/op????????2?allocs/op
在這種情況下，我們分配更少的內(nèi)存，同時(shí)泛型的速度是非泛型的兩倍。
合約（Contracts）
上面的堆棧示例適用于任何類型。但是，在許多情況下，你需要編寫僅適用于具有某些特征的類型的代碼。例如，你可能希望堆棧要求類型實(shí)現(xiàn) String() 函數(shù)
隊(duì)列的概念在 順序隊(duì)列 中，而使用循環(huán)隊(duì)列的目的主要是規(guī)避假溢出造成的空間浪費(fèi)，在使用循環(huán)隊(duì)列處理假溢出時(shí)，主要有三種解決方案
本文提供后兩種解決方案。
順序隊(duì)和循環(huán)隊(duì)列是一種特殊的線性表，與順序棧類似，都是使用一組地址連續(xù)的存儲(chǔ)單元依次存放自隊(duì)頭到隊(duì)尾的數(shù)據(jù)元素，同時(shí)附設(shè)隊(duì)頭(front)和隊(duì)尾(rear)兩個(gè)指針，但我們要明白一點(diǎn)，這個(gè)指針并不是指針變量，而是用來表示數(shù)組當(dāng)中元素下標(biāo)的位置。
本文使用切片來完成的循環(huán)隊(duì)列，由于一開始使用三個(gè)參數(shù)的make關(guān)鍵字創(chuàng)建切片，在輸出的結(jié)果中不包含nil值(看起來很舒服)，而且在驗(yàn)證的過程中發(fā)現(xiàn)使用append()函數(shù)時(shí)切片內(nèi)置的cap會(huì)發(fā)生變化，在消除了種種障礙后得到了一個(gè)四不像的循環(huán)隊(duì)列，即設(shè)置的指針是順序隊(duì)列的指針，但實(shí)際上進(jìn)行的操作是順序隊(duì)列的操作。最后是對(duì)make()函數(shù)和append()函數(shù)的一些使用體驗(yàn)和小結(jié)，隊(duì)列的應(yīng)用放在鏈隊(duì)好了。
官方描述(片段)
即切片是一個(gè)抽象層，底層是對(duì)數(shù)組的引用。
當(dāng)我們使用
構(gòu)建出來的切片的每個(gè)位置的值都被賦為interface類型的初始值nil，但是nil值也是有大小的。
而使用
來進(jìn)行初始化時(shí)，雖然生成的切片中不包含nil值，但是無法通過設(shè)置的指針變量來完成入隊(duì)和出隊(duì)的操作，只能使用append()函數(shù)來進(jìn)行操作
在go語言中，切片是一片連續(xù)的內(nèi)存空間加上長度與容量的標(biāo)識(shí)，比數(shù)組更為常用。使用 append 關(guān)鍵字向切片中追加元素也是常見的切片操作
正是基于此，在使用go語言完成循環(huán)隊(duì)列時(shí)，首先想到的就是使用make(type, len, cap)關(guān)鍵字方式完成切片初始化，然后使用append()函數(shù)來操作該切片，但這一方式出現(xiàn)了很多問題。在使用append()函數(shù)時(shí)，切片的cap可能會(huì)發(fā)生變化，用不好就會(huì)發(fā)生擴(kuò)容或收縮。最終造成的結(jié)果是一個(gè)四不像的結(jié)果，入隊(duì)和出隊(duì)操作變得與指針變量無關(guān)，失去了作為循環(huán)隊(duì)列的意義，用在順序隊(duì)列還算合適。
參考博客：
Go語言中的Nil
Golang之nil
Go 語言設(shè)計(jì)與實(shí)現(xiàn)
基本設(shè)計(jì)思路：
類型轉(zhuǎn)換、類型斷言、動(dòng)態(tài)派發(fā)。iface，eface。
反射對(duì)象具有的方法：
編譯優(yōu)化：
內(nèi)部實(shí)現(xiàn)：
實(shí)現(xiàn) Context 接口有以下幾個(gè)類型（空實(shí)現(xiàn)就忽略了）：
互斥鎖的控制邏輯：
設(shè)計(jì)思路：
（以上為寫被讀阻塞，下面是讀被寫阻塞）
總結(jié)，讀寫鎖的設(shè)計(jì)還是非常巧妙的：
設(shè)計(jì)思路：
WaitGroup 有三個(gè)暴露的函數(shù):
部件：
設(shè)計(jì)思路：
結(jié)構(gòu)：
Once 只暴露了一個(gè)方法：
實(shí)現(xiàn)：
三個(gè)關(guān)鍵點(diǎn)：
細(xì)節(jié)：
讓多協(xié)程任務(wù)的開始執(zhí)行時(shí)間可控（按順序或歸一）。（Context 是控制結(jié)束時(shí)間）
設(shè)計(jì)思路： 通過一個(gè)鎖和內(nèi)置的 notifyList 隊(duì)列實(shí)現(xiàn)，Wait() 會(huì)生成票據(jù)，并將等待協(xié)程信息加入鏈表中，等待控制協(xié)程中發(fā)送信號(hào)通知一個(gè)（Signal()）或所有（Boardcast()）等待者（內(nèi)部實(shí)現(xiàn)是通過票據(jù)通知的）來控制協(xié)程解除阻塞。
暴露四個(gè)函數(shù)：
實(shí)現(xiàn)細(xì)節(jié)：
部件：
包： golang.org/x/sync/errgroup
作用：開啟 func() error 函數(shù)簽名的協(xié)程，在同 Group 下協(xié)程并發(fā)執(zhí)行過程并收集首次 err 錯(cuò)誤。通過 Context 的傳入，還可以控制在首次 err 出現(xiàn)時(shí)就終止組內(nèi)各協(xié)程。
設(shè)計(jì)思路：
結(jié)構(gòu)：
暴露的方法：
實(shí)現(xiàn)細(xì)節(jié)：
注意問題：
包： "golang.org/x/sync/semaphore"
作用：排隊(duì)借資源（如錢，有借有還）的一種場(chǎng)景。此包相當(dāng)于對(duì)底層信號(hào)量的一種暴露。
設(shè)計(jì)思路：有一定數(shù)量的資源 Weight，每一個(gè) waiter 攜帶一個(gè) channel 和要借的數(shù)量 n。通過隊(duì)列排隊(duì)執(zhí)行借貸。
結(jié)構(gòu)：
暴露方法：
細(xì)節(jié)：
部件：
細(xì)節(jié)：
包： "golang.org/x/sync/singleflight"
作用：防擊穿。瞬時(shí)的相同請(qǐng)求只調(diào)用一次，response 被所有相同請(qǐng)求共享。
設(shè)計(jì)思路：按請(qǐng)求的 key 分組（一個(gè) *call 是一個(gè)組，用 map 映射存儲(chǔ)組），每個(gè)組只進(jìn)行一次訪問，組內(nèi)每個(gè)協(xié)程會(huì)獲得對(duì)應(yīng)結(jié)果的一個(gè)拷貝。
結(jié)構(gòu)：
邏輯：
細(xì)節(jié)：
部件：
如有錯(cuò)誤，請(qǐng)批評(píng)指正。
重慶分公司
重慶分公司
