Go言語のチュートリアルの A Tour of Go の Appending to a slice について、 なんで、
len=5 cap=8 [0 1 2 3 4]
と、capacityが8になるんだー、と悩んでしまったのでちょっと調べてみた。
実験としては、以下のコードを書いて実行したみた感じです。
package main
import "fmt"
func main() {
s := make([]int, 0)
printSlice(s)
for i := 0; i < 100; i++ {
s = append(s, i)
printSlice(s)
}
s = make([]int, 0)
printSlice(s)
for i := 0; i < 100; i++ {
new_s := make([]int, len(s)+1)
copy(new_s, s)
new_s[i] = i + 1
s = new_s
printSlice(s)
}
}
func printSlice(s []int) {
fmt.Printf("len:%d cap:%d\n", len(s), cap(s))
}
で、結果は、
len:0 cap:0
len:1 cap:1
len:2 cap:2
len:3 cap:4
len:4 cap:4
len:5 cap:8
len:6 cap:8
len:7 cap:8
len:8 cap:8
len:9 cap:16
... snip ...
len:16 cap:16
len:17 cap:32
... snip ...
len:32 cap:32
len:33 cap:64
... snip ...
len:64 cap:64
len:65 cap:128
... snip ...
len:100 cap:128
len:0 cap:0
len:1 cap:1
len:2 cap:2
len:3 cap:3
len:4 cap:4
len:5 cap:5
... snip...
len:31 cap:31
len:32 cap:32
len:33 cap:33
len:34 cap:34
len:35 cap:35
len:36 cap:36
... snip...
len:98 cap:98
len:99 cap:99
len:100 cap:100
となりました。
どうも、Cで malloc() とか使うときよろしく、Goでも二倍ずつ(?)余裕をもたせてメモリを確保していく感じみたい。
と、上の内容をQiitaででも書いてやろうかと思ったのですが、 こちらのページ にて以下の記述が!!
まずはnewcapの計算から見てみよう。newcapは拡張後の新しいcapの値になる。newcapの計算処理は次の様なロジックだ。
- 現在のcapの2倍の値が求められているcapよりも小さければ、求められているcapをnewcapにする
- lenが1024より短い場合は現在のcapを2倍にしていき、求められているcapよりも大きくなったらその値をnewcapにする
- lenが1024よりも長ければ1/4ずつ増やしていく
つまり、1024より短い時は今のcapの2倍以上、1024よりも長ければ1.25倍以上にするようになっている。これが良く聞くGoのsliceは2倍ずつ増えていく、の実装である。
ということで、Goのsliceが2倍ずつ増えていくというのは、とてもメジャーなお話らしい。 そんなわけで、Qiitaに書かずにこちらに記載しておきました……。