Go初学者が学んだことまとめ〜appendがどのくらい遅いか検証してみた〜

#はじめに
Goの参照型であるスライス(可変長配列)は、appendすることで要素数を拡張できます。
しかし、容量をオーバーした場合、メモリ上のデータを新しい領域にコピーするという処理が走り、動作コストが高いとされています。
そこで、どのくらい実行性能に影響があるのか、実際にコードを書いて試してみました。

なお、appendの仕様はこちらにまとめてあります。
Go初学者が学んだことまとめ〜その２〜（参照型）

#測定
Goのバージョンはこちら。

$ go version
go version go1.11 darwin/amd64

1万〜10億回、配列に値を格納する処理の実行時間を計測しました。
条件は下記の通り。

関数名	型	初期の長さ	初期の容量	ループ処理
sliceTime	スライス	0	0	append
allocatedSliceTime	スライス	0	1万〜10億	append
initializedSliceTime	スライス	1万〜10億	1万〜10億	代入
arrayTime	配列	1万〜10億	1万〜10億	代入

検証コード

main.go

package main

import (
	"fmt"
	"time"
)

const maxLoopCount = 1000000000

func sliceTime(loopCount int) {
	beforeTime := time.Now()
	slice := make([]int, 0)
	for i := 0; i < loopCount; i++ {
		slice = append(slice, i)
	}
	afterTime := time.Now()
	diff := afterTime.Sub(beforeTime)
	fmt.Printf("slice time(loop %d):%s\n", loopCount, diff)
}

func allocatedSliceTime(loopCount int) {
	beforeTime := time.Now()
	slice := make([]int, 0, loopCount)
	for i := 0; i < loopCount; i++ {
		slice = append(slice, i)
	}
	afterTime := time.Now()
	diff := afterTime.Sub(beforeTime)
	fmt.Printf("allocated slice time(loop %d):%s\n", loopCount, diff)
}

func initializedSliceTime(loopCount int) {
	beforeTime := time.Now()
	slice := make([]int, loopCount)
	for i := 0; i < loopCount; i++ {
		slice[i] = i
	}
	afterTime := time.Now()
	diff := afterTime.Sub(beforeTime)
	fmt.Printf("initialized slice time(loop %d):%s\n", loopCount, diff)
}

func arrayTime() {
	beforeTime := time.Now()
	ary := [maxLoopCount]int{}
	for i := 0; i < maxLoopCount; i++ {
		ary[i] = i
	}
	afterTime := time.Now()
	diff := afterTime.Sub(beforeTime)
	fmt.Printf("array time(loop %d):%s\n", maxLoopCount, diff)
}

func main() {
	for i := 10000; i <= maxLoopCount; i *= 10 {
		sliceTime(i)
		allocatedSliceTime(i)
		initializedSliceTime(i)
	}
	//arrayTime() //maxLoopCountを10000〜1000000000に変更し、ビルドして実行した
}

#結果

実行時間

loop	sliceTime	allocatedSliceTime	initializedSliceTime	arrayTime
10000	231.196µs	39.464µs	38.007µs	3.015µs
100000	2.349229ms	135.933µs	95.347µs	28.81µs
1000000	13.2845ms	1.303881ms	1.059979ms	278.565µs
10000000	109.442382ms	12.975474ms	13.98987ms	32.87561ms
100000000	1.313008414s	136.082698ms	135.611302ms	330.41205ms
1000000000	50.543104006s	9.616915173s	1.730548321s	3.340341675s

容量0で毎回appendした場合(sliceTime)がダントツで遅いです。やはり容量の拡張は時間がかかる処理なのでしょう。

事前に容量の確保だけした場合(allocatedSliceTime)と、事前に容量の確保と初期化をした場合(initializedSliceTime）では、10億回ループを回すとようやく差が出てきました。
配列(arrayTime)とinitializedSliceTimeを比較すると、以外にもループの数が大きくなると、initializedSliceTimeの方が実行速度が速いという結果になりました。内部的にはどちらも固定長配列に値を代入しているだけだと思うのですが、何が違うのでしょうか。

全体的に見れば、事前に容量を確保したスライスと配列の速度はさほど変わりはないので、スライスと配列の選択をする際は、基本的に速度のことは意識せず、状況によって使いやすい方を使えばいいかと思います。

#まとめ

• 容量拡張が発生するappendはそれなりに実行性能に影響がでるので、スライスを使うときは、なるべく事前に容量を確保しておいた方がいい。
• 上記さえ気を付けていれば、スライスと固定長配列のどちらを使うか選択する場面では、実行性能のことはあまり意識しなくてもいい。

さて、この結論で正しいのでしょうか。

#関連
Go初学者が学んだことまとめ〜その２〜（参照型）