曹大帶我學(xué) Go之從 Map 的 Extra 字段談起
本文轉(zhuǎn)載自微信公眾號(hào)「碼農(nóng)桃花源」，作者小X 。轉(zhuǎn)載本文請(qǐng)聯(lián)系碼農(nóng)桃花源公眾號(hào)。
你好，我是小X。
曹大最近開(kāi) Go 課程了，小X 正在和曹大學(xué) Go。
這個(gè)系列會(huì)講一些從課程中學(xué)到的讓人醍醐灌頂?shù)臇|西，撥云見(jiàn)日，帶你重新認(rèn)識(shí) Go。
熟悉 map 結(jié)構(gòu)體的讀者應(yīng)該知道，hmap 由很多 bmap(bucket) 構(gòu)成，每個(gè) bmap 都保存了 8 個(gè) key/value 對(duì)：
hmap
有時(shí)落在同一個(gè) bmap 中的 key/value 太多了，超過(guò)了 8 個(gè)，就會(huì)由溢出 bmap 來(lái)承接，即 overflow bmap(后面我們叫它 bucket)。溢出的 bucket 和原來(lái)的 bucket 形成一個(gè)“拉鏈”。
對(duì)于這些 overflow 的 bucket，在 hmap 結(jié)構(gòu)體和 bmap 結(jié)構(gòu)體里分別有一個(gè) extra.overflow 和 overflow 字段指向它們。
如果我們仔細(xì)看 mapextra 結(jié)構(gòu)體里對(duì) overflow 字段的注釋?zhuān)瑫?huì)發(fā)現(xiàn)這里有“文章”。
- type mapextra struct {
- overflow *[]*bmap
- oldoverflow *[]*bmap
- nextOverflow *bmap
- }
其中 overflow 這個(gè)字段上面有一大段注釋?zhuān)覀儊?lái)看看前兩行：
- // If both key and elem do not contain pointers and are inline, then we mark bucket
- // type as containing no pointers. This avoids scanning such maps.
意思是如果 map 的 key 和 value 都不包含指針的話(huà)，在 GC 期間就可以避免對(duì)它的掃描。在 map 非常大(幾百萬(wàn)個(gè) key)的場(chǎng)景下，能提升不少性能。
那具體是怎么實(shí)現(xiàn)“不掃描”的呢?
我們知道，bmap 這個(gè)結(jié)構(gòu)體里有一個(gè) overflow 指針，它指向溢出的 bucket。因?yàn)樗且粋€(gè)指針，所以 GC 的時(shí)候肯定要掃描它，也就要掃描所有的 bmap。
而當(dāng) map 的 key/value 都是非指針類(lèi)型的話(huà)，掃描是可以避免的，直接標(biāo)記整個(gè) map 的顏色(三色標(biāo)記法)就行了，不用去掃描每個(gè) bmap 的 overflow 指針。
但是溢出的 bucket 總是可能存在的，這和 key/value 的類(lèi)型無(wú)關(guān)。
于是就利用 hmap 里的 extra 結(jié)構(gòu)體的 overflow 指針來(lái) “hold” 這些 overflow 的 bucket，并把 bmap 結(jié)構(gòu)體的 overflow 指針類(lèi)型變成一個(gè) unitptr 類(lèi)型(這些是在編譯期干的)。于是整個(gè) bmap 就完全沒(méi)有指針了，也就不會(huì)在 GC 期間被掃描。
- overflow *[]*bmap
另一方面，當(dāng) GC 在掃描 hmap 時(shí)，通過(guò) extra.overflow 這條路徑(指針)就可以將 overflow 的 bucket 正常標(biāo)記成黑色，從而不會(huì)被 GC 錯(cuò)誤地回收。
當(dāng)我們知道上面這些原理后，就可以利用它來(lái)對(duì)一些場(chǎng)景進(jìn)行性能優(yōu)化：
- map[string]int -> map[[12]byte]int
因?yàn)?string 底層有指針，所以當(dāng) string 作為 map 的 key 時(shí)，GC 階段會(huì)掃描整個(gè) map;而數(shù)組 [12]byte 是一個(gè)值類(lèi)型，不會(huì)被 GC 掃描。
我們用兩種方法來(lái)驗(yàn)證優(yōu)化效果。
主動(dòng)觸發(fā) GC
這里的測(cè)試代碼來(lái)自文章《盡量不要在大 map 中保存指針》[1]：
- func MapWithPointer() {
- const N = 10000000
- m := make(map[string]string)
- for i := 0; i < N; i++ {
- n := strconv.Itoa(i)
- m[n] = n
- }
- now := time.Now()
- runtime.GC()
- fmt.Printf("With a map of strings, GC took: %s\n", time.Since(now))
- // 引用一下防止被 GC 回收掉
- _ = m["0"]
- }
- func MapWithoutPointer() {
- const N = 10000000
- m := make(map[int]int)
- for i := 0; i < N; i++ {
- str := strconv.Itoa(i)
- // hash string to int
- n, _ := strconv.Atoi(str)
- m[n] = n
- }
- now := time.Now()
- runtime.GC()
- fmt.Printf("With a map of int, GC took: %s\n", time.Since(now))
- _ = m[0]
- }
- func TestMapWithPointer(t *testing.T) {
- MapWithPointer()
- }
- func TestMapWithoutPointer(t *testing.T) {
- MapWithoutPointer()
- }
直接用了 2 個(gè)不同類(lèi)型的 map：前者 key 和 value 都是 string 類(lèi)型，后者 key 和 value 都是 int 類(lèi)型。整個(gè) map 大小為 1kw。
測(cè)試結(jié)果：
- === RUN TestMapWithPointer
- With a map of strings, GC took: 150.078ms
- --- PASS: TestMapWithPointer (4.22s)
- === RUN TestMapWithoutPointer
- With a map of int, GC took: 4.9581ms
- --- PASS: TestMapWithoutPointer (2.33s)
- PASS
于是驗(yàn)證了 string 相對(duì)于 int 這種值類(lèi)型對(duì) GC 的消耗更大。正如這篇文章的標(biāo)題所說(shuō)：
Go語(yǔ)言使用 map 時(shí)盡量不要在 big map 中保存指針。
用 pprof 看對(duì)象數(shù)
第二種方式就是直接開(kāi)個(gè) pprof 來(lái)看 heap profile。這次我們將 string 類(lèi)型的 key 優(yōu)化成數(shù)組類(lèi)型：
- package main
- import (
- "fmt"
- "io"
- "net/http"
- _ "net/http/pprof"
- )
- // var m = map[[12]byte]int{}
- var m = map[string]int{}
- func init() {
- for i := 0; i < 1000000; i++ {
- // var arr [12]byte
- // copy(arr[:], fmt.Sprint(i))
- // m[arr] = i
- m[fmt.Sprint(i)] = i
- }
- }
- func sayHello(wr http.ResponseWriter, r *http.Request) {
- io.WriteString(wr ,"hello")
- }
- func main() {
- http.HandleFunc("/", sayHello)
- err := http.ListenAndServe(":8000", nil)
- if err != nil {
- fmt.Println(err)
- }
- }
注意，去掉代碼里的注釋即可將 key 從 string 優(yōu)化成數(shù)組類(lèi)型。
直接在 init 里構(gòu)建 map，然后開(kāi) pprof 看 profile：
key 為 string
key 為數(shù)組
對(duì)象數(shù)從 33w 下降到 1.5w，效果非常明顯。
map 的 key 和 value 要不要在 GC 里掃描，和類(lèi)型是有關(guān)的。數(shù)組類(lèi)型是個(gè)值類(lèi)型，string 底層也是指針。
不過(guò)要注意，key/value 大于 128B 的時(shí)候，會(huì)退化成指針類(lèi)型。
那么問(wèn)題來(lái)了，什么是指針類(lèi)型呢?**所有顯式 *T 以及內(nèi)部有 pointer 的對(duì)像都是指針類(lèi)型。
——來(lái)自董神的 map 優(yōu)化文章
關(guān)于超過(guò) 128 字節(jié)的情況，源碼里也有說(shuō)明：
- // Maximum key or elem size to keep inline (instead of mallocing per element).
- maxKeySize = 128
- maxElemSize = 128
總結(jié)
當(dāng) map 的 key/value 是非指針類(lèi)型時(shí)，GC 不會(huì)對(duì)所有的 bucket 進(jìn)行掃描。如果線上服務(wù)使用了一個(gè)超大的 map ，會(huì)因此提升性能。
為了不讓 overflow 的 bucket 被 GC 錯(cuò)誤地回收掉，在 hmap 里用 extra.overflow 指針指向它，從而在三色標(biāo)記里將其標(biāo)記為黑色。
如果你用了 key 是 string 類(lèi)型的 map，并且恰好這些 string 是定長(zhǎng)的，那么就可以用 key 為數(shù)組類(lèi)型的 map 來(lái)優(yōu)化它。
通過(guò)主動(dòng)調(diào)用 GC 以及開(kāi) pprof 都可觀察優(yōu)化效果。
好了，這就是今天全部的內(nèi)容了~ 我是小X，我們下期再見(jiàn)~
歡迎關(guān)注曹大的 TechPaper 以及碼農(nóng)桃花源~
參考資料
[1]《盡量不要在大 map 中保存指針》: https://www.jianshu.com/p/5903323a7110
