13518219792
不知道你有沒有聽過這么一句：在使用 map 時(shí)盡量不要在 big map 中保存指針。好吧，你現(xiàn)在已經(jīng)聽過了：）為什么呢？原因在于 Go 語言的垃圾回收器會掃描標(biāo)記 map 中的所有元素，GC 開銷相當(dāng)大，直接GG。
成都創(chuàng)新互聯(lián)公司長期為成百上千家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為章丘企業(yè)提供專業(yè)的成都網(wǎng)站制作、網(wǎng)站建設(shè)，章丘網(wǎng)站改版等技術(shù)服務(wù)。擁有十年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。
這兩天在《Mastering Go》中看到 GC 這一章節(jié)里面對比 map 和 slice 在垃圾回收中的效率對比，書中只給出結(jié)論沒有說明理由，這我是不能忍的，于是有了這篇學(xué)習(xí)筆記。扯那么多，Show Your Code
這是一個(gè)簡單的測試程序，保存字符串的 map 和 保存整形的 map GC 的效率相差幾十倍，是不是有同學(xué)會說明明保存的是 string 哪有指針？這個(gè)要說到 Go 語言中 string 的底層實(shí)現(xiàn)了，源碼在 src/runtime/string.go里，可以看到 string 其實(shí)包含一個(gè)指向數(shù)據(jù)的指針和一個(gè)長度字段。注意這里的是否包含指針，包括底層的實(shí)現(xiàn)。
Go 語言的 GC 會遞歸遍歷并標(biāo)記所有可觸達(dá)的對象，標(biāo)記完成之后將所有沒有引用的對象進(jìn)行清理。掃描到指針就會往下接著尋找，一直到結(jié)束。
Go 語言中 map 是基于 數(shù)組和鏈表 的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的，通過 優(yōu)化的拉鏈法 解決哈希沖突，每個(gè) bucket 可以保存 8 對鍵值，在 8 個(gè)鍵值對數(shù)據(jù)后面有一個(gè) overflow 指針，因?yàn)橥爸凶疃嘀荒苎b 8 個(gè)鍵值對，如果有多余的鍵值對落到了當(dāng)前桶，那么就需要再構(gòu)建一個(gè)桶（稱為溢出桶），通過 overflow 指針鏈接起來。
因?yàn)?overflow 指針的緣故，所以無論 map 保存的是什么，GC 的時(shí)候就會把所有的 bmap 掃描一遍，帶來巨大的 GC 開銷。官方 issues 就有關(guān)于這個(gè)問題的討論， runtime: Large maps cause significant GC pauses #9477
無腦機(jī)翻如下：
如果我們有一個(gè)map [k] v，其中k和v都不包含指針，并且我們想提高掃描性能，則可以執(zhí)行以下操作。
將“ allOverflow [] unsafe.Pointer”添加到 hmap 并將所有溢出存儲桶存儲在其中。 然后將 bmap 標(biāo)記為noScan。 這將使掃描非常快，因?yàn)槲覀儾粫呙枞魏斡脩魯?shù)據(jù)。
實(shí)際上，它將有些復(fù)雜，因?yàn)槲覀冃枰獜腶llOverflow中刪除舊的溢出桶。 而且它還會增加 hmap 的大小，因此也可能需要重新整理數(shù)據(jù)。
最終官方在 hmap 中增加了 overflow 相關(guān)字段完成了上面的優(yōu)化，這是具體的 commit 地址。
下面看下具體是如何實(shí)現(xiàn)的，源碼基于 go1.15，src/cmd/compile/internal/gc/reflect.go 中
通過注釋可以看出，如果 map 中保存的鍵值都不包含指針（通過 Haspointers 判斷），就使用一個(gè) uintptr 類型代替 bucket 的指針用于溢出桶 overflow 字段，uintptr 類型在 GO 語言中就是個(gè)大小可以保存得下指針的整數(shù)，不是指針，就相當(dāng)于實(shí)現(xiàn)了 將 bmap 標(biāo)記為 noScan， GC 的時(shí)候就不會遍歷完整個(gè) map 了。隨著不斷的學(xué)習(xí)，愈發(fā)感慨 GO 語言中很多模塊設(shè)計(jì)得太精妙了。
差不多說清楚了，能力有限，有不對的地方歡迎留言討論，源碼位置還是問的群里大佬 _
Go語言由Google公司開發(fā)，并于2009年開源，相比Java/Python/C等語言，Go尤其擅長并發(fā)編程，性能堪比C語言，開發(fā)效率肩比Python，被譽(yù)為“21世紀(jì)的C語言”。
Go語言在云計(jì)算、大數(shù)據(jù)、微服務(wù)、高并發(fā)領(lǐng)域應(yīng)用應(yīng)用非常廣泛。BAT大廠正在把Go作為新項(xiàng)目開發(fā)的首選語言。
Go語言應(yīng)用范圍：
1、服務(wù)端開發(fā)：以前你使用C或者C++做的那些事情，用Go來做很合適，例如日志處理、文件系統(tǒng)、監(jiān)控系統(tǒng)等;
2、DevOps：運(yùn)維生態(tài)中的Docker、K8s、prometheus、grafana、open-falcon等都是使用Go語言開發(fā);
3、網(wǎng)絡(luò)編程：大量優(yōu)秀的Web框架如Echo、Gin、Iris、beego等，而且Go內(nèi)置的 net/http包十分的優(yōu)秀;
4、Paas云平臺領(lǐng)域：Kubernetes和Docker Swarm等;
5、分布式存儲領(lǐng)域：etcd、Groupcache、TiDB、Cockroachdb、Influxdb等;
6、區(qū)塊鏈領(lǐng)域：區(qū)塊鏈里面有兩個(gè)明星項(xiàng)目以太坊和fabric都使用Go語言;
7、容器虛擬化：大名鼎鼎的Docker就是使用Go語言實(shí)現(xiàn)的;
8、爬蟲及大數(shù)據(jù)：Go語言天生支持并發(fā)，所以十分適合編寫分布式爬蟲及大數(shù)據(jù)處理。
sync.Map是1.9才推薦的并發(fā)安全的map，除了互斥量以外，還運(yùn)用了原子操作，所以在這之前，有必要了解下 Go語言——原子操作
go1.10\src\sync\map.go
entry分為三種情況：
從read中讀取key，如果key存在就tryStore。
注意這里開始需要加鎖，因?yàn)樾枰僮鱠irty。
條目在read中，首先取消標(biāo)記，然后將條目保存到dirty里。（因?yàn)闃?biāo)記的數(shù)據(jù)不在dirty里）
最后原子保存value到條目里面，這里注意read和dirty都有條目。
總結(jié)一下Store：
這里可以看到dirty保存了數(shù)據(jù)的修改，除非可以直接原子更新read，繼續(xù)保持read clean。
有了之前的經(jīng)驗(yàn)，可以猜測下load流程：
與猜測的 區(qū)別 ：
由于數(shù)據(jù)保存兩份，所以刪除考慮：
先看第二種情況。加鎖直接刪除dirty數(shù)據(jù)。思考下貌似沒什么問題，本身就是臟數(shù)據(jù)。
第一種和第三種情況唯一的區(qū)別就是條目是否被標(biāo)記。標(biāo)記代表刪除，所以直接返回。否則CAS操作置為nil。這里總感覺少點(diǎn)什么，因?yàn)闂l目其實(shí)還是存在的，雖然指針nil。
看了一圈貌似沒找到標(biāo)記的邏輯，因?yàn)閯h除只是將他變成nil。
之前以為這個(gè)邏輯就是簡單的將為標(biāo)記的條目拷貝給dirty，現(xiàn)在看來大有文章。
p == nil，說明條目已經(jīng)被delete了，CAS將他置為標(biāo)記刪除。然后這個(gè)條目就不會保存在dirty里面。
這里其實(shí)就跟miss邏輯串起來了，因?yàn)閙iss達(dá)到閾值之后，dirty會全量變成read，也就是說標(biāo)記刪除在這一步最終刪除。這個(gè)還是很巧妙的。
真正的刪除邏輯：
很繞。。。。
由于go語言是一個(gè)強(qiáng)類型的語言，因此hashmap也是有類型的，具體體現(xiàn)在key和value都必須指定類型，比如聲明一個(gè)key為string，value也是string的map，
需要這樣做
大部分類型都能做key，某些類型是不能的，共同的特點(diǎn)是： 不能使用== 來比較，包括: slice, map, function
在迭代的過程中是可以對map進(jìn)行刪除和更新操作的，規(guī)則如下：
golang的map是hash結(jié)構(gòu)的，意味著平均訪問時(shí)間是O(1)的。同傳統(tǒng)的hashmap一樣，由一個(gè)個(gè)bucket組成:
那我們怎么訪問到對應(yīng)的bucket呢，我們需要得到對應(yīng)key的hash值
各個(gè)參數(shù)的意思：
目前采用的是這一行:
| 6.50 | 20.90 | 10.79 | 4.25 | 6.50 |
map 是Go語言中基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，在日常的使用中經(jīng)常被用到。但是它底層是如何實(shí)現(xiàn)的呢？
總體來說golang的map是hashmap，是使用數(shù)組+鏈表的形式實(shí)現(xiàn)的，使用拉鏈法消除hash沖突。
golang的map由兩種重要的結(jié)構(gòu)，hmap和bmap(下文中都有解釋)，主要就是hmap中包含一個(gè)指向bmap數(shù)組的指針，key經(jīng)過hash函數(shù)之后得到一個(gè)數(shù)，這個(gè)數(shù)低位用于選擇bmap(當(dāng)作bmap數(shù)組指針的下表)，高位用于放在bmap的[8]uint8數(shù)組中，用于快速試錯(cuò)。然后一個(gè)bmap可以指向下一個(gè)bmap(拉鏈)。
Golang中map的底層實(shí)現(xiàn)是一個(gè)散列表，因此實(shí)現(xiàn)map的過程實(shí)際上就是實(shí)現(xiàn)散表的過程。在這個(gè)散列表中，主要出現(xiàn)的結(jié)構(gòu)體有兩個(gè)，一個(gè)叫 hmap (a header for a go map)，一個(gè)叫 bmap (a bucket for a Go map，通常叫其bucket)。這兩種結(jié)構(gòu)的樣子分別如下所示：
hmap :
圖中有很多字段，但是便于理解map的架構(gòu)，你只需要關(guān)心的只有一個(gè)，就是標(biāo)紅的字段： buckets數(shù)組 。Golang的map中用于存儲的結(jié)構(gòu)是bucket數(shù)組。而bucket(即bmap)的結(jié)構(gòu)是怎樣的呢？
bucket ：
相比于hmap，bucket的結(jié)構(gòu)顯得簡單一些，標(biāo)紅的字段依然是“核心”，我們使用的map中的key和value就存儲在這里。“高位哈希值”數(shù)組記錄的是當(dāng)前bucket中key相關(guān)的“索引”，稍后會詳細(xì)敘述。還有一個(gè)字段是一個(gè)指向擴(kuò)容后的bucket的指針，使得bucket會形成一個(gè)鏈表結(jié)構(gòu)。例如下圖：
由此看出hmap和bucket的關(guān)系是這樣的：
而bucket又是一個(gè)鏈表，所以，整體的結(jié)構(gòu)應(yīng)該是這樣的：
哈希表的特點(diǎn)是會有一個(gè)哈希函數(shù)，對你傳來的key進(jìn)行哈希運(yùn)算，得到唯一的值，一般情況下都是一個(gè)數(shù)值。Golang的map中也有這么一個(gè)哈希函數(shù)，也會算出唯一的值，對于這個(gè)值的使用，Golang也是很有意思。
Golang把求得的值按照用途一分為二：高位和低位。
如圖所示，藍(lán)色為高位，紅色為低位。 然后低位用于尋找當(dāng)前key屬于hmap中的哪個(gè)bucket，而高位用于尋找bucket中的哪個(gè)key。上文中提到：bucket中有個(gè)屬性字段是“高位哈希值”數(shù)組，這里存的就是藍(lán)色的高位值，用來聲明當(dāng)前bucket中有哪些“key”，便于搜索查找。 需要特別指出的一點(diǎn)是：我們map中的key/value值都是存到同一個(gè)數(shù)組中的。數(shù)組中的順序是這樣的:
并不是key0/value0/key1/value1的形式，這樣做的好處是：在key和value的長度不同的時(shí)候，可 以消除padding(內(nèi)存對齊)帶來的空間浪費(fèi) 。
現(xiàn)在，我們可以得到Go語言map的整個(gè)的結(jié)構(gòu)圖了：(hash結(jié)果的低位用于選擇把KV放在bmap數(shù)組中的哪一個(gè)bmap中，高位用于key的快速預(yù)覽，用于快速試錯(cuò))
map的擴(kuò)容
當(dāng)以上的哈希表增長的時(shí)候，Go語言會將bucket數(shù)組的數(shù)量擴(kuò)充一倍，產(chǎn)生一個(gè)新的bucket數(shù)組，并將舊數(shù)組的數(shù)據(jù)遷移至新數(shù)組。
加載因子
判斷擴(kuò)充的條件，就是哈希表中的加載因子(即loadFactor)。
加載因子是一個(gè)閾值，一般表示為：散列包含的元素?cái)?shù) 除以 位置總數(shù)。是一種“產(chǎn)生沖突機(jī)會”和“空間使用”的平衡與折中：加載因子越小，說明空間空置率高，空間使用率小，但是加載因子越大，說明空間利用率上去了，但是“產(chǎn)生沖突機(jī)會”高了。
每種哈希表的都會有一個(gè)加載因子，數(shù)值超過加載因子就會為哈希表擴(kuò)容。
Golang的map的加載因子的公式是：map長度 / 2^B(這是代表bmap數(shù)組的長度，B是取的低位的位數(shù))閾值是6.5。其中B可以理解為已擴(kuò)容的次數(shù)。
當(dāng)Go的map長度增長到大于加載因子所需的map長度時(shí)，Go語言就會將產(chǎn)生一個(gè)新的bucket數(shù)組，然后把舊的bucket數(shù)組移到一個(gè)屬性字段oldbucket中。注意：并不是立刻把舊的數(shù)組中的元素轉(zhuǎn)義到新的bucket當(dāng)中，而是，只有當(dāng)訪問到具體的某個(gè)bucket的時(shí)候，會把bucket中的數(shù)據(jù)轉(zhuǎn)移到新的bucket中。
如下圖所示：當(dāng)擴(kuò)容的時(shí)候，Go的map結(jié)構(gòu)體中，會保存舊的數(shù)據(jù)，和新生成的數(shù)組
上面部分代表舊的有數(shù)據(jù)的bucket，下面部分代表新生成的新的bucket。藍(lán)色代表存有數(shù)據(jù)的bucket，橘黃色代表空的bucket。
擴(kuò)容時(shí)map并不會立即把新數(shù)據(jù)做遷移，而是當(dāng)訪問原來舊bucket的數(shù)據(jù)的時(shí)候，才把舊數(shù)據(jù)做遷移，如下圖：
注意：這里并不會直接刪除舊的bucket，而是把原來的引用去掉，利用GC清除內(nèi)存。
map中數(shù)據(jù)的刪除
如果理解了map的整體結(jié)構(gòu)，那么查找、更新、刪除的基本步驟應(yīng)該都很清楚了。這里不再贅述。
值得注意的是，找到了map中的數(shù)據(jù)之后，針對key和value分別做如下操作：
1
2
3
4
1、如果``key``是一個(gè)指針類型的，則直接將其置為空，等待GC清除；
2、如果是值類型的，則清除相關(guān)內(nèi)存。
3、同理，對``value``做相同的操作。
4、最后把key對應(yīng)的高位值對應(yīng)的數(shù)組index置為空。
GO語言由Google公司開發(fā)，并于2009年開源，對比Java、Python、C等語言，GO尤其擅長并發(fā)編程，性能堪比C語言，開發(fā)效率比肩Python，被譽(yù)為21世紀(jì)的C語言。GO語言在云計(jì)算、大數(shù)據(jù)、微服務(wù)、高并發(fā)領(lǐng)域，應(yīng)用非常廣泛。BAT大廠正在把GO作為新項(xiàng)目開發(fā)的首選語言。
