Goでスライスに要素を追加する方法を比較してみた

こんにちは！昨年の12月からレスキューナウにジョインした竹内と申します。
現在は既存サービスのリプレースプロジェクトに参加して主にバックエンドを担当しています。

今回は良く使うスライスへの要素追加で気になった箇所があったので調査してみました🔍️

背景

現在バックエンドはGo言語を使いDDD＋オニオンアーキテクチャで実装しているのですが、レイヤー間を跨ぐ場合にデータの変換処理をすることが多くあります。そのためスライスのデータを他のデータに変換して詰め直すケースが頻繁に発生します。

スライスに値を詰め直す方法はいくつかあるのですが、どの方法が効率よくスライスを扱えるのか分かっていなかったので計測して比較してみたいと思います。

今回は以下の３つの方法を計測して比較してみたいと思います。
「推測するな、計測しろ」といいますしね👍

前提として対象の要素数が事前に分かっているケースに絞って計測します。

1. slice := []int{}でlen、capを指定せずにスライスを宣言して値をappendする場合
2. slice := make([]int, 0, len(n))でlen=0、cap=要素数のスライスを宣言して値をappendする場合
3. slice := make([]int, len(n))でlen,cap共に要素数のスライスを宣言して添字で値を置き換える場合

1. slice := []int{}でlen、capを指定せずにスライスを宣言して値をappendする場合

知りたかったのは2,3なのですがまず初めによくやってしまう宣言で計測してみようと思います。

hoge := []int{}
fmt.Printf("長さ(length):%d, 容量(capacity):%d", len(hoge), cap(hoge))

この方式で宣言した場合はスライスの長さ（length）が0、容量（capacity）が0になります。

長さ(length):0, 容量(capacity):0

ちなみにこの宣言はhoge := make(int[], 0)と同じです。
この宣言方式でベンチマークをとってみようと思います。
コードは引数xの数だけappendするサンプルです。

main.go

func Empty(x int) {
	hoge := []int{}
	for i := 0; i < x; i++ {
		hoge = append(hoge, i)
	}
}

main_test.go

func BenchmarkEmpty(b *testing.B) {
	Empty(b.N)
}

実行結果

% go test -bench . -benchtime 10s 
goos: darwin
goarch: arm64
pkg: hoge
BenchmarkEmpty-10       1000000000              13.02 ns/op
PASS
ok      hoge    14.180s

項目	値
CPU数	10
実行回数	1,000,000,000
1回あたりの処理時間	13.02ナノ秒

ということがわかりました。
実際に実行する回数が引数xで渡されているにもかかわらず、lenもcapも指定せずに変数を宣言しているのでこれが一番遅いと思っています。

調べてみると・・・。
Go1.17の段階ではキャパシティが1,024未満の場合は2倍にし、それ以降は25%以上増やすというルールのようです。そのため今回のケースではcapが0から始まっているため要素を追加する毎に以下のようにキャパシティが変化していきます。

moge := []int{} // len:0 cap:0
moge = append(moge, 1) // len:1 cap:1
moge = append(moge, 2) // len:2 cap:2
moge = append(moge, 3) // len:3 cap:4
moge = append(moge, 4) // len:4 cap:4
moge = append(moge, 5) // len:5 cap:8

スライスの実体は固定長の配列であり、スライスはそれを参照する窓として使われてメモリの読み書きをします。
裏の配列に要素を追加し続けて割り当てられたサイズを使い切ってしまった場合、Goのランタイムは新しくメモリを確保してそちらに配列の内容をコピーして移動させます。スライスのappend関数の裏では以下の操作が行われています。

1. 確保済みのメモリが不足したらOSに要求する
2. 既存のものから新しい配列用にメモリを割り当てる
3. 新しい配列に前の配列の内容をコピー
4. 前の配列にアクセスするスライスやヘンスがなくなったらメモリを解放

このような操作が行われているため今回のケースはメモリの再確保とコピーの回数が多く、実行速度が低下したと考えられます。

あらかじめ必要な要素数がわかっているならちゃんとcapを指定しないと無駄が多いことがわかりますね。

2. slice := make([]int, 0, len(n))でlen=0、cap=要素数のスライスを宣言して値をappendする場合

次は実行回数がわかっているのできちんと　lenとcapを指定して変数を宣言したうえでappend関数で値を追加していくケースです。

main.go

func SliceAppend(x int) {
	hoge := make([]int, 0, x)
	for i := 0; i < x; i++ {
		hoge = append(hoge, i)
	}
}

main_test.go

func BenchmarkSliceAppend(b *testing.B) {
	SliceAppend(b.N)
}

% go test -bench . -benchtime 10s
goos: darwin
goarch: arm64
pkg: hoge
BenchmarkSliceAppend-10         1000000000               0.9884 ns/op
PASS
ok      hoge    1.627s

項目	値
CPU数	10
実行回数	1,000,000,000
1回あたりの処理時間	0.9884ナノ秒

ということがわかりました。
capを指定するだけでこんなに違うんですね。

3. slice := make([]int, len(n))でlen,cap共に要素数のスライスを宣言して添字で値を置き換える場合

最後に変数宣言時にスライスの要素を確保し、ループ中に添字を使って値を置き換える場合を計測してみたいと思います。
makeでlenだけを指定した場合capも同じ値になります。

main.go

func SliceSubscript(x int) {
	hoge := make([]int, x)
	for i := 0; i < x; i++ {
		hoge[i] = i
	}
}

main_test.go

func BenchmarkSliceSubscript(b *testing.B) {
	SliceSubscript(b.N)
}

% go test -bench . -benchtime 10s
goos: darwin
goarch: arm64
pkg: hoge
BenchmarkSliceSubscript-10      1000000000               1.256 ns/op
PASS
ok      hoge    1.868s

項目	値
CPU数	10
実行回数	1,000,000,000
1回あたりの処理時間	1.256ナノ秒

ということがわかりました。
私としてはappendより遅いのがちょっと意外でした🧐

まとめ

方式	1回あたりの処理時間	比較
1. slice := []int{}でlen、capを指定せずにスライスを宣言して値をappendする場合	13.02ナノ秒	-
2. slice := make([]int, 0, len(n))でlen=0、cap=要素数のスライスを宣言して値をappendする場合	0.9884ナノ秒	1に比べて約13倍の速さ
3. slice := make([]int, len(n))でlen,cap共に要素数のスライスを宣言して添字で値を置き換える場合	1.256ナノ秒	1に比べて約10倍の速さ

以上から要素数がわかっている場合はmakeでcapを指定して変数を宣言しappendするのが一番早いことがわかりました。
うっかりhoge := []int{}としがちなのですが、これだけ差があると考えものですね。。。
基本的な話ではありますが、コード内で何度も出てくるのでしっかり意識して書いていきたいと思います🧑‍💻