オーバーフローの理解から入る前に、Goが扱っている整数型について軽くまとめておきたいと思います。
Goは10つの整数型を定義しており、以下の通りです。
1番最初に「u」がついているものは符号なし整数型で、ついていないものは符号あり整数型です。
符号なし整数は負の数を扱わず全ビットを数値として扱え、符号あり整数は最初のビットが符号を表しており負の数も扱うことができます。
ちなみに、int型とuint型はシステムに依存した数を持っており、32ビット環境の場合は32ビット、64ビット環境の場合は64ビットになりますね。
そしてオーバーフローに関してですが、以下のような場合だとコンパイルエラーは起きませんがオーバーフローします。
1package main
2
3import (
4 "fmt"
5 "math"
6)
7
8func main() {
9 var counter int64 = math.MaxInt64
10 fmt.Println(counter)
11 counter++
12 fmt.Println(counter)
13}19223372036854775807
2-9223372036854775808なぜこうなるのか？
int64型は符号あり整数型であり、1番最初のビットが符号を表現しています。
19223372036854775807は2進数で
101111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111であり、これに1を足すことで以下のようになります。
110000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000先ほども言ったように、1番最初のビットは符号を表しており、1は負を、0は正を表しているのでこうなります。
1-9223372036854775808これは純然たるオーバーフローの挙動ですがコンパイルエラーにはなりません。ゆえに、扱いには注意が必要です。
スライスは初期化の方法によってかなりパフォーマンスに差が出てきます。
例えばこれ。
1func buildWithAppend(n int) []int {
2 l := make([]int, 0)
3 for i := 0; i < n; i++ {
4 l = append(l, i)
5 }
6 return l
7}このコードは長さを0としてスライスを初期化し、n回分iをスライスにappendしています。
このコードだと容量は0なので基底配列がいっぱいになるたびに容量を2倍にして別の配列を作成する動きをします。
1最初のスライス： l = [] （len=0, cap=0）
2append(0) → cap不足 → 新しい配列 cap=1 を作り、[0] にする
3append(1) → cap不足 → 新しい配列 cap=2 を作り、[0,1] にコピー
4append(2) → cap不足 → 新しい配列 cap=4 を作り、[0,1,2] にコピー
5append(3) → cap不足 → 新しい配列 cap=8 を作り、[0,1,2,3] にコピー
6append(4) → cap=8 に余裕あり → そのまま追加 [0,1,2,3,4]こんな感じで、容量がいっぱいになるたびにコピーが発生します。コピーの負荷もそうですし、古い基底配列を開放するためのGCのコストもnが大きくなればなるほど辛くなってきます。
じゃあどうすればいいか？
最初のアプローチとしては容量を指定してコピーが起きないようにします。
1func buildWithAppendLen(n int) []int {
2 l := make([]int, 0, n)
3 for i := 0; i < n; i++ {
4 l = append(l, i)
5 }
6 return l
7}容量にnを指定し、事前にn分の要素を持つ基底配列を割り当てます。今回のケースだと、こうすることでコピーが発生しなくなります。
ほんとにこれでパフォーマンスがよくなるのかベンチを取ってみました。計測しないとなんともなので。
1func BenchmarkBuildWithAppend(b *testing.B) {
2 for i := 0; i < b.N; i++ {
3 _ = buildWithAppend(100000)
4 }
5}
6
7func BenchmarkBuildWithAppendLen(b *testing.B) {
8 for i := 0; i < b.N; i++ {
9 _ = buildWithAppendLen(100000)
10 }
11}1BenchmarkBuildWithAppend-11 4479 270299 ns/op 4101409 B/op 28 allocs/op
2BenchmarkBuildWithAppendLen-11 19514 60740 ns/op 802821 B/op 1 allocs/opかなり改善されたことがわかります。
1回ごとの処理時間もそうですし、メモリ割り当ての回数も良くなりましたね。
ちなみに
1func buildWithAppendLen(n int) []int {
2 l := make([]int, n, n)
3 for i := 0; i < n; i++ {
4 l = append(l, i)
5 }
6 return l
7}の長さをnにすると一気にパフォーマンスが落ちます。
というのも今回は100000をnに指定していますが、長さをnにすると100000個の0が初期値として基底配列の要素として与えられるからですね。
結果、ループ内でappendする際に基底配列がいっぱいになるとコピーが発生してしまいます。なので長さは0にする必要があります。
次のアプローチは長さと容量共にn分の要素を割り当てるものです。
1func buildWithAppendAssign(n int) []int {
2 l := make([]int, n)
3 for i := 0; i < n; i++ {
4 l[i] = i
5 }
6 return l
7}こうすると、長さにnを割り当てられ、容量にもnが割り当てられます。
appendすると基底配列に対し要素が増えていくので、l[i]で愚直に要素を設定していきます。
ベンチを取るとこうなりました。
1BenchmarkBuildWithAppend-11 4473 270348 ns/op 4101408 B/op 28 allocs/op
2BenchmarkBuildWithAppendLen-11 19362 60940 ns/op 802822 B/op 1 allocs/op
3BenchmarkBuildWithAppendAssign-11 21277 55701 ns/op 802826 B/op 1 allocs/opBenchmarkBuildWithAppendAssign関数が地味にですが1番パフォーマンスが出ていました。
おそらくappendが持つ小さなオーバーヘッドがないのでその分処理が早くなったんだと思います。
こんな感じでスライスを初期化するときに適当にやっていると、パフォーマンスがかなり悪化することもあるので気をつけたいところです。
appendは予期せぬ動作をする時があります。
例えばこのコード。
1func main() {
2 l := []int{2, 4, 6}
3 r := f(l[1:2])
4 fmt.Println("l:", l)
5 fmt.Println("r:", r)
6}
7
8func f(l []int) []int {
9 _l := append(l, 8)
10 return _l
11}このコードの出力は以下のようになります。
1l: [2 4 8]
2r: [4 8]main関数の l変数 にf関数でappendした 8 が追加されています。
これはなぜか？
append関数はスライスに空きがあれば、基底配列を更新して要素を追加し長さを1つ増やす動きをするからです。
ちなみに、スライスに空きがあるとはcap（容量）に対して len（長さ）がまだ小さい場合を意味します。
今回の場合、f関数の中のlは[4]であり、長さが1で容量が2です。それに対し 8 をappendすると容量が2なので[4, 8]となります。
_lスライスはmain関数の lスライスの基底配列を参照しているので、lスライスも引っ張られ、基底配列のindex=2の要素が書き換えられ、今回のような出力結果になるわけです。
ではこれを防ぐにはどうすればいいか？
簡単な方法としてはGoランタイムに組み込まれているcopy関数を使うことです。
1func main() {
2 l := []int{2, 4, 6}
3 _l := make([]int, 1, 2)
4 copy(_l, l[1:2])
5 r := f(_l)
6 fmt.Println("l:", l)
7 fmt.Println("r:", r)
8}
9
10func f(l []int) []int {
11 _l := append(l, 8)
12 return _l
13}このコードの出力は以下のようになります。
1l: [2 4 6]
2r: [4 9]コピーしたことによって、f関数で更新した内容がmain関数のlスライスに反映されていません。
また、他の回避選択肢として完全スライス式がありますがここでは割愛しようと思います。
こんな感じで、appendは適当に使ってしまうと予期しない動作をする可能性があるので注意が必要ですね。
スライス同様、マップについても初期化を意識することは大事です。
例えば以下のコード。
1package main
2
3import (
4 "crypto/rand"
5 "fmt"
6 "runtime"
7)
8
9const N = 5000000
10
11// 256バイト配列をランダムで埋める関数
12func randBytes() [256]byte {
13 var arr [256]byte
14 _, err := rand.Read(arr[:])
15 if err != nil {
16 panic(err)
17 }
18 return arr
19}
20
21func printAlloc() {
22 var m runtime.MemStats
23 runtime.ReadMemStats(&m)
24 fmt.Printf("Alloc = %v MB\n", m.Alloc/1024/1024) // 現在のヒープ割り当て
25
26}
27
28func main() {
29 m := make(map[int][256]byte)
30 printAlloc()
31
32 for i := 0; i < N; i++ {
33 m[i] = randBytes()
34 }
35 printAlloc()
36 for i := 0; i < N; i++ {
37 delete(m, i)
38 }
39 // m = nil
40 runtime.GC()
41 printAlloc()
42 runtime.KeepAlive(m)
43}こちらを動かすと以下のような出力が得られました。
1Alloc = 0 MB
2Alloc = 1376 MB
3Alloc = 144 MBruntime.GC()をした後に割り当てられているメモリを確認すると、まだ結構な量(144MB)のメモリが残っています。
今回の場合、5,000,000個という大量の要素を作成しているので、大体バケット数は625,000個。
しかしGoランタイムはバケット数を2の累乗に切り上げるので、実際には 1,048,576 個のバケットが確保されます
このバケットは全ての要素を削除しても縮小されません。なので、GCが全要素を回収しても144MBものメモリが残ったままなんですね。
マップは大きくなってもバケットは増えるだけで縮小はしないということです。
なのでマップをnilなどにする作業が必要です。
こうすると
1func main() {
2 m := make(map[int][256]byte)
3 printAlloc()
4
5 for i := 0; i < N; i++ {
6 m[i] = randBytes()
7 }
8 printAlloc()
9 for i := 0; i < N; i++ {
10 delete(m, i)
11 }
12 m = nil
13 runtime.GC()
14 printAlloc()
15 runtime.KeepAlive(m)
16}こんな感じで、m変数の参照がなくなり全てのメモリが解放されました。
1Alloc = 0 MB
2Alloc = 1365 MB
3Alloc = 0 MB