Go の append の挙動の確認
スライスに要素を append した際に、もとのスライスが破壊的に変更されるのかどうかの理解が曖昧ではまったので確認したメモ。わりと何周もしているネタだと思われる。
今回はまったケース
今回はまったケースは次のようなもの。
- map の値としてスライスを保持
- map のあるキー A に入っているスライスに append した結果を別のキー B に代入、同じように B のスライスに append して C に…と繰り返す処理をしていた
- この例でキー A の値が、後に書きかわったり、書きかわらなかったりする挙動だった
append が第一引数の配列を破壊的に変更しているのだろうけど、変化がある場合と無い場合があり不思議だった。
append の挙動
これについてはドキュメントで明確に説明されている。
builtin - The Go Programming Language
- そのスライスのキャパシティに余裕があれば、もとの underlying array に追加する
- キャパシティに余裕がなければ新たにメモリを確保する
以前スライスの内部構造をまとめた際にこの挙動は確認済みだったけれど、解決までにちょっと時間がかかってしまった。知識としてはあっても手に馴染んでいない状態だった。
Go の Slice の内部構造 - Please Sleep
試してみる
前提として、スライスは内部的に配列を保持していて、以降はそれを underlying array と記載する。(前述の記事も参照)
go - How to inspect slice header? - Stack Overflow によると、slice のポインタを unsafe.Pointer に変換し、さらにそれを reflect.SliceHeader に変換させることができるらしい。これを使って確認してみる。
package main
import (
"fmt"
"reflect"
"unsafe"
)
func main() {
slice := []int{1, 2, 3}
fmt.Printf("%p, %p, %+v\n", &slice, slice, (*reflect.SliceHeader)(unsafe.Pointer(&slice)))
// => 0xc00000c018, 0xc000014018, &{Data:824633802776 Len:3 Cap:3}
// 初期状態
slice = append(slice, 4)
fmt.Printf("%p, %p, %+v\n", &slice, slice, (*reflect.SliceHeader)(unsafe.Pointer(&slice)))
// => 0xc00000c018, 0xc000078000, &{Data:824634212352 Len:4 Cap:6}
// cap に余裕がなかったのでメモリ再確保、Data のアドレスが変わっている、Cap は 6 まで伸びている
slice = append(slice, 5)
fmt.Printf("%p, %p, %+v\n", &slice, slice, (*reflect.SliceHeader)(unsafe.Pointer(&slice)))
// => 0xc00000c018, 0xc000078000, &{Data:824634212352 Len:5 Cap:6}
// cap に余裕があったので 824634482736 にそのまま append している。Len だけが増え、Cap はそのまま
}
キャパシティを広げるロジックは ここ のようだが、ある程度までは現状の長さの 2 倍ずつ拡張していく。
今回はまったケースについては、繰り返し回数が少ないテストケースで動作確認し、その後繰り返しが多い実際のケースに適用すると問題が発生した。今回の場合は初回の append は必ず underlying array のリアロケートが走るので、テスト時点では問題に気づけなかったというオチだった。
なお append そのものの実装については、コンパイルフェーズで直接アセンブリを生成しているらしく、ハードルが高いので今回は詳細の確認を割愛した。
Where is the implementation of func append in Go? - Stack Overflow
参考
- builtin - The Go Programming Language
- go - How to inspect slice header? - Stack Overflow
- unsafe - The Go Programming Language
- reflect - The Go Programming Language
- go/slice.go at master · golang/go
- Where is the implementation of func append in Go? - Stack Overflow
