Golang 的 string interning 技巧

Posted by Kakashi on 2020-12-14

String Interning

最近在 twitter 上面看到一篇推文

具體在討論這個 CL 要加入 string interning profile,而利用這個可以測量是否該加入 string interning,原本不知道這個是幹嘛的,後來看了一下 comments 內的一些解釋和文章,才知道原來 String interning 是個可以拿來有效減少 memory 使用量的技巧,原理相當簡單,而在其他語言裡面也有這種東西,像是 python 在一些小的數字和文字上面,都是會指向同一組記憶體,藉此來減少 memory allocation 的時間和用量,而 string intening 也是這類技巧的名字(https://en.wikipedia.org/wiki/String_interning)。

Golang 裡面的運用

在 golang 裡面在什麼地方被用到,也可以看下面幾篇的解釋,個人覺得已經很清楚

基本上要做實驗可以透過下面的 function 去看 string 的 pointer 位置,看是不是同一份

1
2
3
4
5
6
7
8
9
10
11
12
func pointer(s string) uintptr {
p := unsafe.Pointer(&s)
h := *(*reflect.StringHeader)(p)
return h.Data
}

func main() {
b := []byte("hello")
s := string(b)
t := string(b)
fmt.Println(pointer(s), pointer(t))
}

相關的 playgound 連結在這邊,從這個實驗中,我們可以很快發現,兩個字串指向的記憶體不同,而在 golang 裡面比對 string 如果是同一個 pointer 而且 Len 都一樣,就可以加速比對的過程,而不用一個 byte 一個 byte 的去比較,所謂的 interning,也就是如果我們能夠不重複 allocate 記憶體,都用同一個字串。

  • 而有另外一個有趣的點是,這個 playground 裡面可以把 hello 改成 h, 可以看到 pointer 都指向同一個位置,這是透過 compile time constant 的結果,具體可以看這個CL的解釋,透過 benchmark 提前先 allocate 一個字元在效率上面可以提升很多。

自幹 string interning

而在 golang 裡面其實並沒有很多地方有做 interning,但是我們在處理一些資料的時候,其實有機會用到這個技巧,像是第一篇文章裡面有寫到,如果我們要處理大量的 text,如果沒有 interning,可能就需要 allocate 很大量的記憶體去儲存這些資料,另外是像從資料庫讀取東西時,也可以有些數據是一直重複出現的,這時也可以應用同樣的技巧。

而一般來說透過類似 cache 的方式可以自幹 string interning,像是第二篇文章的 code

1
2
3
4
5
6
7
8
9
10
func intern(m map[string]string, b []byte) string { 
// look for an existing string to re-use
c, ok := m[string(b)]
if ok {
// found an existing string return c
}
// didn't find one, so make one and store it
s := string(b)
m[s] = s return s
}

但是麻煩的地方跟自己維護 LRU cache 一樣,如果有不需要用到的字串需要被 evict 掉,要不然也會佔據記憶體,另外是要做一個能夠 concurrent 存取的 LRU cache 也是不容易,所以這個東西沒處理也會變成反效果,而大家都會談論到這個 project https://github.com/josharian/intern,裡面是用 sync.map 實作 interning,但是還是要斟酌一下是不是真的該用。

順帶一提是透過這個 CL,我又追到這個 CL,裡面的討論也蠻不錯的,也讓我了解到設計系統需要考量的一些東西,我蠻建議看下 dsnet 對做 memorize stirngs during decode 的一些看法和實驗,很多地值得借鑒,像是

  • String 越長,對於 cache 越不友善,有可能 cache hit rate 會下降的很快,而太長的 sring 也需要花更多時間去比對和做 hash,所以只需要選擇 cache 小一點的資料(e.g < 16B)
  • Go men allocator 其實速度很快,配置 16B 的字串只需要 35ns,所以 cache 的 lookup 和比較應該要快於 35ns 才有賺
  • JSON 的 object name 有 high degree of locality,所以有個很小的 cache 去存這段東西很值得
  • 而 JSON 的 value 可能就沒那麼值得去 cache,因為 locality 不好

結論

總的來說,string interning 也許不是很常會使用的技巧,但是如果真的有極端的 case,也許拿來使用減少記憶體和 gc 壓力也是不錯的途徑,當然前提還是要經過縝密的 benchmark。

Reference

Photo by jesse orrico on Unsplash