Zenn
🙆

Go における Slice と要素追加のパフォーマンス

2024/03/31に公開
Go
tech

前提

slice 構造体の中に array が包含されているので、array を理解しよう。以下の記事がかなりわかりやすくまとめられている。
Goのarrayとsliceを理解するときがきた - Qiita

Slice と Array

特徴 スライス (Slice) 配列 (Array)
サイズ 動的。長さは実行時に変更可能 静的。宣言時に長さが固定される
タイプ 参照型 値型
初期化 s := []int{1, 2, 3}
s = make([]int, 3) 		a := [3]int{1, 2, 3}
長さと容量 len(s), cap(s)で取得可能 長さはlen(a)で取得可能。容量の概念はない
要素の追加 append() で長さを動的に変更可能 リサイズ不可。新たな配列を作成する必要がある
型定義 他の型定義と同じ 長さが型の一部であるため、[4]int と [5]int は互換性のない別個の型
構成要素 配列へのポインタ、長さ、容量 長さ

長さと容量の違いとは？

長さ：スライスに現在格納されている要素の数
容量：スライスが保持できる最大要素数

スライスはサイズを変更できるため、append関数などで要素を追加すると、そのスライスがもともと持っていた最大の収容数（容量）を超えることがあります。この場合、Go言語は元のスライスの2倍の容量を持つ新しいスライスを作成し、元のスライスのデータを新しいスライスにコピーします

t := make([]byte, len(s), (cap(s)+1)*2) // +1 in case cap(s) == 0
for i := range s {
        t[i] = s[i]
}
s = t

このデータのコピー処理は、パフォーマンスに影響を与える可能性があります。そこで、予め最大の収容数が分かっている場合は、その最大値を元にスライスを初期化することで、パフォーマンスを少し向上させることができます。

Append と代入のどちらを使うか？

スライスで要素を追加したい場合、appendで追加していく方法と、前もって長さの決まった容れ物を作ってから代入する方法があります。どちらでも同じことを実現できますがどちらの方が良いのでしょうか？

結論、長さが確定している場合は代入。それ以外は長さを確保した要素追加が良さそう。

以下がパフォーマンスが高い順

  1. 前もって長さの決まった容れ物を作ってから代入する
  2. 前もって長さの決まった容れ物を作ってから要素を追加する
  3. 単に要素を追加する
// 単に要素を追加する
func WithAppend() []string {
	var l []string
	for i := 0; i < 100; i++ {
		l = append(l, "x")
	}

	return l
}

// 長さを事前に確保してから要素を追加
func WithAppend2() []string {
	l := make([]string, 0, 100)
	for i := 0; i < 100; i++ {
		l = append(l, "x")
	}

	return l
}

// 長さを事前に確保してから代入
func WithAssignAlloc() []string {
	l := make([]string, 100)
	for i := 0; i < 100; i++ {
		l[i] = "x"
	}

	return l
}

// 以下ベンチマーク用のテストコード
func BenchmarkWithAppend(b *testing.B) {
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		WithAppend()
	}
}

func BenchmarkWithAppend2(b *testing.B) {
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		WithAppend2()
	}
}
func BenchmarkWithAssignAlloc(b *testing.B) {
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		WithAssignAlloc()
	}
}

結果

  • 長さを確保しない要素追加と代入を比べると、約43倍の時間差があるので結構大きな差
  • 長さを確保した要素追加は長さを確保しない時と比べると早くなったが、まだ代入の方が早い
  • 長さが確定している場合は代入。それ以外は長さを確保した要素追加が良さそう。
=== RUN   BenchmarkWithAppend
BenchmarkWithAppend
BenchmarkWithAppend-16            893487              1388 ns/op            4080 B/op          8 allocs/op
=== RUN   BenchmarkWithAppend2
BenchmarkWithAppend2
BenchmarkWithAppend2-16          9989192               125.9 ns/op             0 B/op          0 allocs/op
=== RUN   BenchmarkWithAssignAlloc
BenchmarkWithAssignAlloc
BenchmarkWithAssignAlloc-16     39297324                32.02 ns/op            0 B/op          0 allocs/op

長さを確保した append の注意点

長さと要素を理解していれば当たり前の話だが、長さを 5 で設定して、5つの要素を append すると要素数は 10 になる。

type Student struct {
	Name  string
	Grade int
}

students := []*Student{
	{Name: "taro", Grade: 1},
	{Name: "yoshiko", Grade: 1},
	{Name: "naoya", Grade: 2},
	{Name: "toshiko", Grade: 3},
	{Name: "yamato", Grade: 3},
}
names := make([]string, len(students))
for _, student := range students {
	names = append(names, student.Name)
}
fmt.Println(names)      // [     taro yoshiko naoya toshiko yamato]
fmt.Println(len(names)) // 10

https://go.dev/play/p/scjNWlchmdZ

参考

Discussion