[[416124]]

本文轉(zhuǎn)載自微信公眾號「碼農(nóng)桃花源」，作者小X 。轉(zhuǎn)載本文請聯(lián)系碼農(nóng)桃花源公眾號。

你好，我是小X。

曹大最近開 Go 課程了，小X 正在和曹大學(xué) Go。

這個(gè)系列會(huì)講一些從課程中學(xué)到的讓人醍醐灌頂?shù)臇|西，撥云見日，帶你重新認(rèn)識 Go。

熟悉 map 結(jié)構(gòu)體的讀者應(yīng)該知道，hmap 由很多 bmap(bucket) 構(gòu)成，每個(gè) bmap 都保存了 8 個(gè) key/value 對：

hmap

有時(shí)落在同一個(gè) bmap 中的 key/value 太多了，超過了 8 個(gè)，就會(huì)由溢出 bmap 來承接，即 overflow bmap(后面我們叫它 bucket)。溢出的 bucket 和原來的 bucket 形成一個(gè)“拉鏈”。

對于這些 overflow 的 bucket，在 hmap 結(jié)構(gòu)體和 bmap 結(jié)構(gòu)體里分別有一個(gè) extra.overflow 和 overflow 字段指向它們。

如果我們仔細(xì)看 mapextra 結(jié)構(gòu)體里對 overflow 字段的注釋，會(huì)發(fā)現(xiàn)這里有“文章”。

type mapextra struct { 
 overflow    *[]*bmap 
 oldoverflow *[]*bmap 
 
 nextOverflow *bmap 
} 

其中 overflow 這個(gè)字段上面有一大段注釋，我們來看看前兩行：

// 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 都不包含指針的話，在 GC 期間就可以避免對它的掃描。在 map 非常大(幾百萬個(gè) key)的場景下，能提升不少性能。

那具體是怎么實(shí)現(xiàn)“不掃描”的呢?

我們知道，bmap 這個(gè)結(jié)構(gòu)體里有一個(gè) overflow 指針，它指向溢出的 bucket。因?yàn)樗且粋€(gè)指針，所以 GC 的時(shí)候肯定要掃描它，也就要掃描所有的 bmap。

而當(dāng) map 的 key/value 都是非指針類型的話，掃描是可以避免的，直接標(biāo)記整個(gè) map 的顏色(三色標(biāo)記法)就行了，不用去掃描每個(gè) bmap 的 overflow 指針。

但是溢出的 bucket 總是可能存在的，這和 key/value 的類型無關(guān)。

于是就利用 hmap 里的 extra 結(jié)構(gòu)體的 overflow 指針來 “hold” 這些 overflow 的 bucket，并把 bmap 結(jié)構(gòu)體的 overflow 指針類型變成一個(gè) unitptr 類型(這些是在編譯期干的)。于是整個(gè) bmap 就完全沒有指針了，也就不會(huì)在 GC 期間被掃描。

overflow    *[]*bmap 

另一方面，當(dāng) GC 在掃描 hmap 時(shí)，通過 extra.overflow 這條路徑(指針)就可以將 overflow 的 bucket 正常標(biāo)記成黑色，從而不會(huì)被 GC 錯(cuò)誤地回收。

當(dā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è)值類型，不會(huì)被 GC 掃描。

我們用兩種方法來驗(yàn)證優(yōu)化效果。

主動(dòng)觸發(fā) GC

這里的測試代碼來自文章《盡量不要在大 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è)不同類型的 map：前者 key 和 value 都是 string 類型，后者 key 和 value 都是 int 類型。整個(gè) map 大小為 1kw。

測試結(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 相對于 int 這種值類型對 GC 的消耗更大。正如這篇文章的標(biāo)題所說：

Go語言使用 map 時(shí)盡量不要在 big map 中保存指針。

用 pprof 看對象數(shù)

第二種方式就是直接開個(gè) pprof 來看 heap profile。這次我們將 string 類型的 key 優(yōu)化成數(shù)組類型：

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ù)組類型。

直接在 init 里構(gòu)建 map，然后開 pprof 看 profile：

key 為 string

key 為數(shù)組

對象數(shù)從 33w 下降到 1.5w，效果非常明顯。

map 的 key 和 value 要不要在 GC 里掃描，和類型是有關(guān)的。數(shù)組類型是個(gè)值類型，string 底層也是指針。

不過要注意，key/value 大于 128B 的時(shí)候，會(huì)退化成指針類型。

那么問題來了，什么是指針類型呢?**所有顯式 *T 以及內(nèi)部有 pointer 的對像都是指針類型。

——來自董神的 map 優(yōu)化文章

關(guān)于超過 128 字節(jié)的情況，源碼里也有說明：

// Maximum key or elem size to keep inline (instead of mallocing per element). 
maxKeySize  = 128 
maxElemSize = 128 

總結(jié)

當(dāng) map 的 key/value 是非指針類型時(shí)，GC 不會(huì)對所有的 bucket 進(jìn)行掃描。如果線上服務(wù)使用了一個(gè)超大的 map ，會(huì)因此提升性能。

為了不讓 overflow 的 bucket 被 GC 錯(cuò)誤地回收掉，在 hmap 里用 extra.overflow 指針指向它，從而在三色標(biāo)記里將其標(biāo)記為黑色。

如果你用了 key 是 string 類型的 map，并且恰好這些 string 是定長的，那么就可以用 key 為數(shù)組類型的 map 來優(yōu)化它。

通過主動(dòng)調(diào)用 GC 以及開 pprof 都可觀察優(yōu)化效果。

好了，這就是今天全部的內(nèi)容了~ 我是小X，我們下期再見~

歡迎關(guān)注曹大的 TechPaper 以及碼農(nóng)桃花源~

參考資料

[1]《盡量不要在大 map 中保存指針》: https://www.jianshu.com/p/5903323a7110