不知道你有沒(méi)有聽(tīng)過(guò)這么一句：在使用 map 時(shí)盡量不要在 big map 中保存指針。好吧，你現(xiàn)在已經(jīng)聽(tīng)過(guò)了：）為什么呢？原因在于 Go 語(yǔ)言的垃圾回收器會(huì)掃描標(biāo)記 map 中的所有元素，GC 開(kāi)銷(xiāo)相當(dāng)大，直接GG。
創(chuàng)新互聯(lián)建站堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：網(wǎng)站設(shè)計(jì)、成都網(wǎng)站設(shè)計(jì)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶(hù)于互聯(lián)網(wǎng)時(shí)代的南樂(lè)網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！
這兩天在《Mastering Go》中看到 GC 這一章節(jié)里面對(duì)比 map 和 slice 在垃圾回收中的效率對(duì)比，書(shū)中只給出結(jié)論沒(méi)有說(shuō)明理由，這我是不能忍的，于是有了這篇學(xué)習(xí)筆記。扯那么多，Show Your Code
這是一個(gè)簡(jiǎn)單的測(cè)試程序，保存字符串的 map 和 保存整形的 map GC 的效率相差幾十倍，是不是有同學(xué)會(huì)說(shuō)明明保存的是 string 哪有指針？這個(gè)要說(shuō)到 Go 語(yǔ)言中 string 的底層實(shí)現(xiàn)了，源碼在 src/runtime/string.go里，可以看到 string 其實(shí)包含一個(gè)指向數(shù)據(jù)的指針和一個(gè)長(zhǎng)度字段。注意這里的是否包含指針，包括底層的實(shí)現(xiàn)。
Go 語(yǔ)言的 GC 會(huì)遞歸遍歷并標(biāo)記所有可觸達(dá)的對(duì)象，標(biāo)記完成之后將所有沒(méi)有引用的對(duì)象進(jìn)行清理。掃描到指針就會(huì)往下接著尋找，一直到結(jié)束。
Go 語(yǔ)言中 map 是基于 數(shù)組和鏈表 的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的，通過(guò) 優(yōu)化的拉鏈法 解決哈希沖突，每個(gè) bucket 可以保存 8 對(duì)鍵值，在 8 個(gè)鍵值對(duì)數(shù)據(jù)后面有一個(gè) overflow 指針，因?yàn)橥爸凶疃嘀荒苎b 8 個(gè)鍵值對(duì)，如果有多余的鍵值對(duì)落到了當(dāng)前桶，那么就需要再構(gòu)建一個(gè)桶（稱(chēng)為溢出桶），通過(guò) overflow 指針鏈接起來(lái)。
因?yàn)?overflow 指針的緣故，所以無(wú)論 map 保存的是什么，GC 的時(shí)候就會(huì)把所有的 bmap 掃描一遍，帶來(lái)巨大的 GC 開(kāi)銷(xiāo)。官方 issues 就有關(guān)于這個(gè)問(wèn)題的討論， runtime: Large maps cause significant GC pauses #9477
無(wú)腦機(jī)翻如下：
如果我們有一個(gè)map [k] v，其中k和v都不包含指針，并且我們想提高掃描性能，則可以執(zhí)行以下操作。
將“ allOverflow [] unsafe.Pointer”添加到 hmap 并將所有溢出存儲(chǔ)桶存儲(chǔ)在其中。 然后將 bmap 標(biāo)記為noScan。 這將使掃描非常快，因?yàn)槲覀儾粫?huì)掃描任何用戶(hù)數(shù)據(jù)。
實(shí)際上，它將有些復(fù)雜，因?yàn)槲覀冃枰獜腶llOverflow中刪除舊的溢出桶。 而且它還會(huì)增加 hmap 的大小，因此也可能需要重新整理數(shù)據(jù)。
最終官方在 hmap 中增加了 overflow 相關(guān)字段完成了上面的優(yōu)化，這是具體的 commit 地址。
下面看下具體是如何實(shí)現(xiàn)的，源碼基于 go1.15，src/cmd/compile/internal/gc/reflect.go 中
通過(guò)注釋可以看出，如果 map 中保存的鍵值都不包含指針（通過(guò) Haspointers 判斷），就使用一個(gè) uintptr 類(lèi)型代替 bucket 的指針用于溢出桶 overflow 字段，uintptr 類(lèi)型在 GO 語(yǔ)言中就是個(gè)大小可以保存得下指針的整數(shù)，不是指針，就相當(dāng)于實(shí)現(xiàn)了 將 bmap 標(biāo)記為 noScan， GC 的時(shí)候就不會(huì)遍歷完整個(gè) map 了。隨著不斷的學(xué)習(xí)，愈發(fā)感慨 GO 語(yǔ)言中很多模塊設(shè)計(jì)得太精妙了。
差不多說(shuō)清楚了，能力有限，有不對(duì)的地方歡迎留言討論，源碼位置還是問(wèn)的群里大佬 _
2021-11-10
列表是一種非連續(xù)的存儲(chǔ)容器，有多個(gè)節(jié)點(diǎn)組成，節(jié)點(diǎn)通過(guò)一些變量記錄彼此之間的關(guān)系
單鏈表和雙鏈表就是列表的兩種方法。
原理：A、B、C三個(gè)人，B懂A的電話，C懂B的電話只是單方知道號(hào)碼，這樣就形成了一個(gè)單鏈表結(jié)構(gòu)。
如果C把自己的號(hào)碼給B，B把自己的號(hào)碼給A，因?yàn)槭请p方都知道對(duì)方的號(hào)碼，這樣就形成了一個(gè)雙鏈表結(jié)構(gòu)
如果B換號(hào)碼了，他需要通知AC，把自己的號(hào)碼刪了，這個(gè)過(guò)程就是列表的刪除操作。
在Go語(yǔ)言中，列表使用 container/list 包來(lái)實(shí)現(xiàn)，內(nèi)部的實(shí)現(xiàn)原理是雙鏈表，列表能夠高效地進(jìn)行任意位置的元素插入和刪除操作。
列表初始化的兩種辦法
列表沒(méi)有給出具體的元素類(lèi)型的限制，所以列表的元素可以是任意類(lèi)型的，
例如給列表中放入了一個(gè) interface{} 類(lèi)型的值，取出值后，如果要將 interface{} 轉(zhuǎn)換為其他類(lèi)型將會(huì)發(fā)生宕機(jī)。
雙鏈表支持從隊(duì)列前方或后方插入元素，分別對(duì)應(yīng)的方法是 PushFront 和 PushBack。
列表插入函數(shù)的返回值會(huì)提供一個(gè) *list.Element 結(jié)構(gòu)，這個(gè)結(jié)構(gòu)記錄著列表元素的值以及與其他節(jié)點(diǎn)之間的關(guān)系等信息，從列表中刪除元素時(shí)，需要用到這個(gè)結(jié)構(gòu)進(jìn)行快速刪除。
遍歷完也能看到最后的結(jié)果
學(xué)習(xí)地址：
golang 中 map的實(shí)現(xiàn)結(jié)構(gòu)為： 哈希表 + 鏈表。 其中鏈表，作用是當(dāng)發(fā)生hash沖突時(shí)，拉鏈法生成的結(jié)點(diǎn)。
可以看到， []bmap 是一個(gè)hash table， 每一個(gè) bmap是我們常說(shuō)的“桶”。 經(jīng)過(guò)hash 函數(shù)計(jì)算出來(lái)相同的hash值， 放到相同的桶中。 一個(gè) bmap中可以存放 8個(gè) 元素， 如果多出8個(gè)，則生成新的結(jié)點(diǎn)，尾接到隊(duì)尾。
以上是只是靜態(tài)文件 src/runtime/map.go 中的定義。 實(shí)際上編譯期間會(huì)給它加料 ，動(dòng)態(tài)地創(chuàng)建一個(gè)新的結(jié)構(gòu)：
上圖就是 bmap的內(nèi)存模型， HOB Hash 指的就是 top hash。 注意到 key 和 value 是各自放在一起的，并不是 key/value/key/value/... 這樣的形式。源碼里說(shuō)明這樣的好處是在某些情況下可以省略掉 padding 字段，節(jié)省內(nèi)存空間。
每個(gè) bmap設(shè)計(jì)成 最多只能放 8 個(gè) key-value 對(duì) ，如果有第 9 個(gè) key-value 落入當(dāng)前的 bmap，那就需要再構(gòu)建一個(gè) bmap，通過(guò) overflow 指針連接起來(lái)。
map創(chuàng)建方法:
我們實(shí)際上是通過(guò)調(diào)用的 makemap ，來(lái)創(chuàng)建map的。實(shí)際工作只是初始化了hmap中的各種字段，如：設(shè)置B的大小， 設(shè)置hash 種子 hash 0.
注意 :
makemap 返回是*hmap 指針， 即 map 是引用對(duì)象， 對(duì)map的操作會(huì)影響到結(jié)構(gòu)體內(nèi)部 。
使用方式
對(duì)應(yīng)的是下面兩種方法
map的key的類(lèi)型，實(shí)現(xiàn)了自己的hash 方式。每種類(lèi)型實(shí)現(xiàn)hash函數(shù)方式不一樣。
key 經(jīng)過(guò)哈希計(jì)算后得到hash值，共 64 個(gè) bit 位。 其中后B 個(gè)bit位置， 用來(lái)定位當(dāng)前元素落在哪一個(gè)桶里， 高8個(gè)bit 為當(dāng)前 hash 值的top hash。 實(shí)際上定位key的過(guò)程是一個(gè)雙重循環(huán)的過(guò)程， 外層循環(huán)遍歷 所有的overflow， 內(nèi)層循環(huán)遍歷 當(dāng)前bmap 中的 8個(gè)元素 。
舉例說(shuō)明： 如果當(dāng)前 B 的值為 5， 那么buckets 的長(zhǎng)度 為 2^5 = 32。假設(shè)有個(gè)key 經(jīng)過(guò)hash函數(shù)計(jì)算后，得到的hash結(jié)果為：
外層遍歷bucket 中的鏈表
內(nèi)層循環(huán)遍歷 bmap中的8個(gè) cell
建議先不看此部分內(nèi)容，看完后續(xù) 修改 map中元素 - 擴(kuò)容 操作后 再回頭看此部分內(nèi)容。
擴(kuò)容前的數(shù)據(jù)：
等量擴(kuò)容后的數(shù)據(jù)：
等量擴(kuò)容后，查找方式和原本相同， 不多做贅述。
兩倍擴(kuò)容后的數(shù)據(jù)
兩倍擴(kuò)容后，oldbuckets 的元素，可能被分配成了兩部分。查找順序如下：
此處只分析 mapaccess1 ,。 mapaccess2 相比 mapaccess1 多添加了是否找到的bool值， 有興趣可自行看一下。
使用方式：
步驟如下：
擴(kuò)容條件 ：
擴(kuò)容的標(biāo)識(shí) ： h.oldbuckets ！= nil
假設(shè)當(dāng)前定位到了新的buckets的3號(hào)桶中，首先會(huì)判斷oldbuckets中的對(duì)應(yīng)的桶有沒(méi)有被搬遷過(guò)。 如果搬遷過(guò)了，不需要看原來(lái)的桶了，直接遍歷新的buckets的3號(hào)桶。
擴(kuò)容前：
等量擴(kuò)容結(jié)果
雙倍擴(kuò)容會(huì)將old buckets上的元素分配到x， y兩個(gè)部key 1 B == 0 分配到x部分，key 1 B == 1 分配到y(tǒng)部分
注意： 當(dāng)前只對(duì)雙倍擴(kuò)容描述， 等量擴(kuò)容只是重新填充了一下元素， 相對(duì)位置沒(méi)有改變。
假設(shè)當(dāng)前map 的B == 5，原本元素經(jīng)過(guò)hash函數(shù)計(jì)算的 hash 值為：
因?yàn)殡p倍擴(kuò)容之后 B = B + 1，此時(shí)B == 6。key 1 B == 1, 即 當(dāng)前元素rehash到高位，新buckets中 y 部分. 否則 key 1 B == 0 則rehash到低位，即x 部分。
使用方式：
可以看到，每一遍歷生成迭代器的時(shí)候，會(huì)隨機(jī)選取一個(gè)bucket 以及 一個(gè)cell開(kāi)始。 從前往后遍歷，再次遍歷到起始位置時(shí)，遍歷完成。
基本設(shè)計(jì)思路：
類(lèi)型轉(zhuǎn)換、類(lèi)型斷言、動(dòng)態(tài)派發(fā)。iface，eface。
反射對(duì)象具有的方法：
編譯優(yōu)化：
內(nèi)部實(shí)現(xiàn)：
實(shí)現(xiàn) Context 接口有以下幾個(gè)類(lèi)型（空實(shí)現(xiàn)就忽略了）：
互斥鎖的控制邏輯：
設(shè)計(jì)思路：
（以上為寫(xiě)被讀阻塞，下面是讀被寫(xiě)阻塞）
總結(jié)，讀寫(xiě)鎖的設(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ù)的開(kāi)始執(zhí)行時(shí)間可控（按順序或歸一）。（Context 是控制結(jié)束時(shí)間）
設(shè)計(jì)思路： 通過(guò)一個(gè)鎖和內(nèi)置的 notifyList 隊(duì)列實(shí)現(xiàn)，Wait() 會(huì)生成票據(jù)，并將等待協(xié)程信息加入鏈表中，等待控制協(xié)程中發(fā)送信號(hào)通知一個(gè)（Signal()）或所有（Boardcast()）等待者（內(nèi)部實(shí)現(xiàn)是通過(guò)票據(jù)通知的）來(lái)控制協(xié)程解除阻塞。
暴露四個(gè)函數(shù)：
實(shí)現(xiàn)細(xì)節(jié)：
部件：
包： golang.org/x/sync/errgroup
作用：開(kāi)啟 func() error 函數(shù)簽名的協(xié)程，在同 Group 下協(xié)程并發(fā)執(zhí)行過(guò)程并收集首次 err 錯(cuò)誤。通過(guò) Context 的傳入，還可以控制在首次 err 出現(xiàn)時(shí)就終止組內(nèi)各協(xié)程。
設(shè)計(jì)思路：
結(jié)構(gòu)：
暴露的方法：
實(shí)現(xiàn)細(xì)節(jié)：
注意問(wèn)題：
包： "golang.org/x/sync/semaphore"
作用：排隊(duì)借資源（如錢(qián)，有借有還）的一種場(chǎng)景。此包相當(dāng)于對(duì)底層信號(hào)量的一種暴露。
設(shè)計(jì)思路：有一定數(shù)量的資源 Weight，每一個(gè) waiter 攜帶一個(gè) channel 和要借的數(shù)量 n。通過(guò)隊(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)行一次訪問(wèn)，組內(nèi)每個(gè)協(xié)程會(huì)獲得對(duì)應(yīng)結(jié)果的一個(gè)拷貝。
結(jié)構(gòu)：
邏輯：
細(xì)節(jié)：
部件：
如有錯(cuò)誤，請(qǐng)批評(píng)指正。
重慶分公司
重慶分公司
