Go sliceの容量は常に2倍で伸びない
この記事は 2021 Go Advent Calendar 16日目 の記事です。
Introduction
題名をちゃんと補足しておくと、 appendして容量が不足していた時の再確保の話です。
主に slice.go に実装されている、 growslice というsliceの容量を増やす関数の話になります。たまたま slice.go の実装を眺めていたら、その該当箇所を見て気づいたことがあるので、これに関して書こうと思います。
appendの挙動
まずはじめに append の挙動を確認します。
- 容量足りてる時
容量が足りてる場合は、新たな値を追加するだけです。
- 容量が足りてない時
容量が足りないと、元の2倍の容量でメモリを再確保し、次に元のデータを新しい方に全てコピーします。最後に新しい値を追加します。
このためにsliceを宣言する時は make([]T, len, cap) のlenやcapをしっかり指定しましょうというのはよく聞く話だと思います。
次に実際のソースを見てみます。
growslice
ここで容量が不足してる時に呼ばれる growslice関数に関して見ていきます。
mastetr branchの最新のコードを見てみたところ、よく見ると常に2倍になっていませんでした。
要素数が256以上になると、 newcap += (newcap + 3*threshold) / 4 の係数でsliceの容量が大きくなっていく実装となっていました。
反対に要素数が256より小さいと、2倍で増えていくという自分の知ってる仕様となってました。
https://github.com/golang/go/blob/master/src/runtime/slice.go
どうしてこうなっているかを知るためにblameしていったらつい最近の修正でした。つまりこれは今使ってるGo 1.17にも入ってない仕様です。(2021年12月16日時点の話です。)
Go 1.17以前の仕様
今使っているGo 1.17では下記の様な実装となっていました。
要素数が1024より小さいと、2倍で増えていきます。
要素数が1024以上になると、 newcap += newcap / 4 であり、つまり1.25倍で容量が増えていきます。
これに関してはGoのgoogle-groupで話されてました。
「slices grow at 25% after 1024 but why 1024?」
結論から言うと任意な数であり、特に意味はなかったようです。
Rob Pikeさんも「1024は多くのsiliceの長さよりも大きい」とも仰っていて、だいたいのユースケースならたしかに気にならないものかなと思いました。また1024から1.25倍で増えるという仕様は、コミット時に特に議論はなかったようです。
ただこのスレッドで「1024の前後で容量が単調増加してないのでは？」という話になっています。つまり下記のようになるということです。
f(x) = 2x (for x < 1024)f(x) = x + x/4 (otherwise)Thenf(1023) = 2046f(1024) = 1280
(正確に読めてる自信がないので、もし間違っていたら指摘お願いします。)
master branchの最新の仕様
これはGo 1.18に含まれるのかもしれない
ここで再度最新の仕様に戻ります。再掲すると下記の実装になっています。
前述のスレッドで単調性があったほうがいいんじゃないという流れの中で、anodel@gmail.comさんが下記のアルゴリズムを提案しました。これなら1024を境に単調に増えていくというものでした。
https://groups.google.com/g/golang-nuts/c/UaVlMQ8Nz3o/m/aHclL-sZAgAJ
f(x) = 2x (for x < 1024)f(x) = x + x/4 + 768 (otherwise)Thenf(1023) = 2046f(1024) = 2048
そして最終的に下記のpatchで上記に近いアルゴリズムが採用されてmergeされたようです。
https://go-review.googlesource.com/c/go/+/347917
f(x) = 2x (for x < 256)f(x) = x + (x + 768) / 4 (otherwise)Thenf(255) = 510f(256) = 512
- 成長係数は容量が255まで2倍で、容量が256以降は2倍からゆるやかに1.25倍に収束していく
- 容量は256の前後で単調に増加する (f(255)->510, f(256)->512)
コメントにありますが、256という数字は再割当ての総数が大体一緒というので採用された模様です。
また成長係数のグラフも添付されています。
Conclusion
Goの内部実装に関して、このような流れでパッチが当てられていくのだなという流れを見れてよかったです。
sliceに関してはlenやcapをできる限り指定していきましょう。
