Goのスライスの作り方によるパフォーマンスの違い
前提
本当は -cpuprofile flag を用いてなぜこの差が出るのかまで明らかにしたほうが良いですが一旦ここまでにします。
package main // index func fill(a []int, n int) { for i := range a { a[i] = i } }
package main // append func fill(a []int, n int) { a = a[:0] for i := range n { a = append(a, i) } }
の２つの実装で 30 % 程度 index の方が速いという結果でした。
何故かというのを明らかにします。
本題
それぞれ -cpuprofile を有効にした状態でベンチマークを実行し pprof の web ui で結果を確認してみます。
今回 Go のソースコードレベルでは理由がわかりません。pprof の disasm を見る必要があります。
Go のアセンブリを読むときはまずその時点の ABIInternal を理解することが大事です。(書くときは今だと ABI0 を理解する必要があります)
まずは index の方の実装の結果を見てみます。
go test -bench Fill -cpuprofile=index.pb.gz go tool pprof -http : ./foo.test index.pb.gz
Total: 3s
ROUTINE ======================== foo.fill
2.78s 2.95s (flat, cum) 98.33% of Total
. . 10010bee0: MOVD R0, 8(RSP) ;main.go:3
. . 10010bee4: MOVD ZR, R2 ;main.go:4
. . 10010bee8: JMP 3(PC)
2.69s 2.84s 10010beec: MOVD R2, (R0)(R2<<3) ;foo.fill main.go:5
. . 10010bef0: ADD $1, R2, R2 ;main.go:4
30ms 30ms 10010bef4: CMP R2, R1 ;foo.fill main.go:4
. . 10010bef8: BGT -3(PC) ;main.go:4
60ms 80ms 10010befc: ? ;foo.fill main.go:7
ABIInternal から第1引数のスライス a のデータが格納されている領域のポインタが R0, スライスの長さが R1, スライスのキャパシティが R2, 第2引数の n が R3 です。
index の方ではキャパシティ(R2)と n(R3) を使ってないため別の用途で使われています。
生成されたアセンブリは至極単純で i が R2 になって添字と代入する値の両方として使われて、それが1づつ ADD されてスライスの長さ R1 になるまで繰り返されるというものです。
(Boundary Check Elimination によって範囲外かどうかの処理が含まれていないことがわかります。)
Go による擬似コードは以下です。
package main func fill(a []int, n int) { r0 := &a[0:] r2 := 0 loop: if r2 >= len(a) { return } r0[r2] = r2 r2 += 1 goto loop }
ほぼすべてのサンプルが MOVD のタイミングだという事がわかります。
次に append に実装を切り替えます。
go test -bench Fill -cpuprofile=append.pb.gz go tool pprof -http : ./foo.test append.pb.gz
Total: 3.02s
ROUTINE ======================== foo.fill
2.78s 2.86s (flat, cum) 94.70% of Total
20ms 30ms 10010bee0: MOVD 16(R28), R16 ;foo.fill main.go:3
. . 10010bee4: CMP R16, RSP ;main.go:3
. . 10010bee8: BLS 31(PC)
. . 10010beec: MOVD.W R30, -96(RSP)
. . 10010bef0: MOVD R29, -8(RSP)
. . 10010bef4: SUB $8, RSP, R29
. . 10010bef8: MOVD R0, 104(RSP)
. . 10010befc: MOVD R3, 128(RSP) ;main.go:5
. . 10010bf00: MOVD ZR, R1
. . 10010bf04: MOVD ZR, R4
. . 10010bf08: JMP 5(PC)
. . 10010bf0c: SUB $1, R5, R6 ;main.go:6
920ms 940ms 10010bf10: MOVD R1, (R0)(R6<<3) ;foo.fill main.go:6
80ms 80ms 10010bf14: ADD $1, R1, R1 ;foo.fill main.go:5
60ms 60ms 10010bf18: MOVD R5, R4 ;foo.fill main.go:6
. . 10010bf1c: CMP R1, R3 ;main.go:5
90ms 100ms 10010bf20: BLE 14(PC) ;foo.fill main.go:5
1.46s 1.49s 10010bf24: ADD $1, R4, R5 ;foo.fill main.go:6
10ms 10ms 10010bf28: CMP R5, R2
30ms 40ms 10010bf2c: BCS -8(PC)
. . 10010bf30: MOVD R1, 80(RSP) ;main.go:5
. . 10010bf34: MOVD R5, R1 ;main.go:6
. . 10010bf38: ORR $1, ZR, R3
. . 10010bf3c: ADRP 348160(PC), R4
. . 10010bf40: ADD $1312, R4, R4
. . 10010bf44: CALL runtime.growslice(SB)
. . 10010bf48: MOVD 128(RSP), R3 ;main.go:5
. . 10010bf4c: MOVD R1, R5 ;main.go:6
. . 10010bf50: MOVD 80(RSP), R1
. . 10010bf54: JMP -18(PC)
100ms 100ms 10010bf58: MOVD -8(RSP), R29 ;foo.fill main.go:8
10ms 10ms 10010bf5c: MOVD.P 96(RSP), R30
. . 10010bf60: RET ;main.go:8
. . 10010bf64: STP (R0, R1), 8(RSP) ;main.go:3
. . 10010bf68: STP (R2, R3), 24(RSP)
. . 10010bf6c: MOVD R30, R3
. . 10010bf70: CALL runtime.morestack_noctxt.abi0(SB)
. . 10010bf74: LDP 8(RSP), (R0, R1)
. . 10010bf78: LDP 24(RSP), (R2, R3)
. . 10010bf7c: ?
index と比較して出力されている命令が多いです。
i が R1, len(a) が R4 にマッピングされてそれぞれ1づつ ADD をしています。 R5 (R4+1) と R2 (cap(a)) を比較してキャパシティを超える場合 runtime.growslice を呼ぶ処理が生成されています。 ただ今回のベンチマークのケースにおいては決して実行されることはありません。
若干謎なのが R4 が offset として使えるはずなのにわざわざ SUB をして R6 (R5-1) として新たに求めています。
Go による擬似コードは以下です。
package main func fill(a []int, n int) { r0 := &a[0:] r1 := 0 r4 := 0 loop: if r1 >= n { return } { r5 := r4 + 1 if r5 > cap(a) { // grow slice } r6 := r5 - 1 r0[r6] = r1 r1 += 1 r4 = r5 } goto loop }
append の方はサンプルが MOVD, ADD のタイミングの２つに分かれています。 ADD に 1.46 秒と書いてあるので ADD が問題だと思われるかもしれませんがこの結果は ADD が重い処理であることを指しません。
スタックをサンプリングしたときに PC がその命令を指していることが多いというだけです。パイプライン実行がストールしているなどのケースも多分にあります。
結論
append の方が生成されているコードが非効率だから index の方が速いです。
しかしこんなに実行される命令数が異なっていても 30% 程度の差で済むというのはパイプライン実行や投機的実行の凄さがわかる結果となりました。
