【Go言語】append使い分けのススメ 〜スライスの先頭へ要素を追加するとき、中身の型は固定長?可変長?〜

こんにちは、Pairs事業部の山下です。
 

最近はインフラチームから離れて、Pairs GlobalチームでPMとして日々を送っています。
 

もちろんエンジニアなので、手が空けば実装もします。
 

そんな中、久しぶりにGoを書いていて、
スライスの先頭に要素を追加(Unshift)したい事案が発生しました。
 

公式wikiのSliceTricksの項では下記のように紹介されております。

// Unshift
a = append([]T{x}, a...)

なるほど、スッキリしていますね。
追加したい要素がスライスに1つだけ入っている状態にして、
その後ろに元のスライスをappendすれば良いということですね。
 

ここで山下は思ってしまいました..
appendって遅いんだ、
「俺ならこう書く!」っと

a := make([]T, 0, len(s)+1)
a[0] = T{x}
for k, v := range s {
a[k+1] = v
}
s = a

そしてドヤ顔でプルリクエストをだしたところ
 

(  ̄- ̄) <「なんでループで回す必要があるんだ!?」
 

と、ごもっともな指摘をいただいてしまいました。
 

「推測するな、計測せよ」ということで、
測ってみたら面白いことがわかったのでご紹介いたします。

計測結果

package main
import (
"testing"
)
var intList []int
const defaultSize = 60000
func ready() {
intList = make([]int, defaultSize)
for i := 0; i < defaultSize; i++ {
intList[i] = i
}
}
// スライスの先頭へ要素を追加するベンチマーク(ループインデックス使用)
func BenchmarkIntListLoop(b *testing.B) {
ready()
b.ResetTimer()
for i := 0; i < b.N; i++ {
intListLoop()
}
}
func intListLoop() []int {
tmpIntList := make([]int, len(intList)+1)
tmpIntList[0] = -1
for i := range intList {
tmpIntList[i+1] = intList[i]
}
return tmpIntList
}
// スライスの先頭へ要素を追加するベンチマーク(append使用)
func BenchmarkIntListAppend(b *testing.B) {
ready()
b.ResetTimer()
for i := 0; i < b.N; i++ {
intListAppend()
}
}
func intListAppend() []int {
return append([]int{-1}, intList...)
}
BenchmarkIntListLoop-4                 10000        145200 ns/op      483328 B/op          1 allocs/op
BenchmarkIntListAppend-4 10000 127000 ns/op 483328 B/op 1 allocs/op
appendの方が早いですね..
ドヤ顔してしまった手前...悔しいですし、腑に落ちないので、
スライスの中身が下記の場合でも試してみました。
  • float64型の場合
  • string型の場合
  • 構造体の場合
  • ポインタの場合
float64型の場合(上がループ、下がappend使用)
BenchmarkFloatListLoop-4               20000         94251 ns/op      245760 B/op          1 allocs/op
BenchmarkFloatListAppend-4 20000 60453 ns/op 245760 B/op 1 allocs/op
string型の場合(上がループ、下がappend使用)
BenchmarkStringListLoop-4               3000        448254 ns/op     966656 B/op          1 allocs/op
BenchmarkStringListAppend-4 2000 572029 ns/op 966656 B/op 1 allocs/op
構造体の場合(上がループ、下がappend使用)
BenchmarkUserListLoop-4                 1000       1782710 ns/op    3366912 B/op          1 allocs/op
BenchmarkUserListAppend-4 1000 2316127 ns/op 3366912 B/op 1 allocs/op
ポインタの場合(上がループ、下がappend使用)
BenchmarkUserPointerListLoop-4          5000        256588 ns/op     483392 B/op          2 allocs/op
BenchmarkUserPointerListAppend-4 5000 325977 ns/op 483392 B/op 2 allocs/op
上の「Benchmark..Loop」という方がループでの処理、
下の「Benchmark..Append」という方がappendでの処理です。


さてさて、面白いことがわかりました。


float64型でやってみた場合のみ、int型と同じようにappendを使った方が早い。
それ以外はループで処理した方が早い!
ここまできてようやくスライスの中身の型が、
「固定長なのか、可変長なのかで、実行速度に違いがでるのではないか?」
仮説を立てることができました。
仮説検証
先ほどは、構造体の要素に可変長型が入っていたので、
可変長型を要素に持たない構造体で試してみました。
// 可変長型要素を持った構造体
type User struct {
ID int
a int
b int64
c string // 可変長型要素
d bool
e float64
}
// 固定長型要素のみの構造体
type FixedUser struct {
ID int
a int
b int64
c int // 固定長型要素に変更
d bool
e float64
}
// 可変長型要素を持った構造体
BenchmarkUserListLoop-4 1000 1782710 ns/op 3366912 B/op 1 allocs/op
BenchmarkUserListAppend-4 1000 2316127 ns/op 3366912 B/op 1 allocs/op


// 固定長型要素のみの構造体
BenchmarkFixedUserListLoop-4 1000 1388381 ns/op 2883584 B/op 1 allocs/op
BenchmarkFixedUserListAppend-4 1000 1211779 ns/op 2883584 B/op 1 allocs/op
やはり固定長型の要素のみであれば、appendの方が早いようです。


最後に
「固定長のbyte配列型」

「可変長のbyteスライス型」
でそれぞれ比較してみます。
var (
fixedByteList [][256]byte // 固定長のbyte配列型
byteList [][]byte // 可変長のbyteスライス型
)
// 固定長のbyte配列型
BenchmarkFixedByteListLoop-4 300 4787843 ns/op 15368201 B/op 1 allocs/op
BenchmarkFixedByteListAppend-4 300 4198040 ns/op 15368195 B/op 1 allocs/op


// 可変長のbyteスライス型
BenchmarkByteListLoop-4 2000 785443 ns/op 1441793 B/op 1 allocs/op
BenchmarkByteListAppend-4 1000 1146921 ns/op 1441792 B/op 1 allocs/op
綺麗に違いがでました。
結論
スライスの先頭に要素を追加(Unshift)したい場合は、
中身が固定長型の時 → append関数で処理をした方が早い
中身が可変長型の時 → ループで処理するようにした方が早い
まとめ
本記事の内容は、ベストプラクティスという訳ではなく、
あくまでも細かいTipsではありますが、
この記事を書いて見て下記の3つのことを思いました。
  • やっぱり実際に計測することが重要
  • Goではマイクロベンチマークが「しやすい・書きやすい」のでどんどん書くと良い
  • 速度は大切だけどコードの可読性と比較にかけて、それでもなお高速化する必要がある場合に最適化するのが良い
以上、ありがとうございました。


「今回検証した Go のバージョンは go1.7.4 darwin/amd64 です。」
計測に使用したコード全文は下記に置いておきます。
package main
import (
"testing"
)
// 可変長型要素を持った構造体
type User struct {
ID int
a int
b int64
c string
d bool
e float64
}
// 固定長型要素のみの構造体
type FixedUser struct {
ID int
a int
b int64
c int
d bool
e float64
}
// 各スライス定義
var (
intList []int
floatList []float64
stringList []string
UserList []User
UserPointerList []*User
FixedUserList []FixedUser
byteList [][]byte
fixedByteList [][256]byte
fixedByteVal [256]byte
byteVal []byte
)
const defaultSize = 60000
// ==============================
// 1. int スライスの比較
// ==============================
// readyIntList setup int slice for benchmark.
// int のスライスの初期設定
func readyIntList() {
intList = make([]int, defaultSize)
for i := 0; i < defaultSize; i++ {
intList[i] = i
}
}
// BenchmarkIntListLoop runs benchmark for int by loop index assignment.
// intスライスの先頭へ要素を追加するベンチマーク(ループインデックス使用)
func BenchmarkIntListLoop(b *testing.B) {
readyIntList()
b.ResetTimer()
for i := 0; i < b.N; i++ {
intListLoop()
}
}
func intListLoop() []int {
tmpIntList := make([]int, len(intList)+1)
tmpIntList[0] = -1
for i := range intList {
tmpIntList[i+1] = intList[i]
}
return tmpIntList
}
// BenchmarkIntListAppend runs benchmark for int by append assignment.
// intスライスの先頭へ要素を追加するベンチマーク(append使用)
func BenchmarkIntListAppend(b *testing.B) {
readyIntList()
b.ResetTimer()
for i := 0; i < b.N; i++ {
intListAppend()
}
}
func intListAppend() []int {
return append([]int{-1}, intList...)
}
// ==============================
// 2. float64 スライスの比較
// ==============================
// readyFloatList setup float64 slice for benchmark.
// float64 のスライスの初期設定
func readyFloatList() {
floatList = make([]float64, defaultSize)
for i := 0; i < defaultSize; i++ {
floatList[i] = float64(i)
}
}
// BenchmarkFloatListLoop runs benchmark for float64 by loop index assignment.
// floatスライスの先頭へ要素を追加するベンチマーク(ループインデックス使用)
func BenchmarkFloatListLoop(b *testing.B) {
readyFloatList()
b.ResetTimer()
for i := 0; i < b.N; i++ {
floatListLoop()
}
}
func floatListLoop() []float64 {
tmpFloatList := make([]float64, len(floatList)+1)
tmpFloatList[0] = 1.1
for i := range floatList {
tmpFloatList[i+1] = floatList[i]
}
return tmpFloatList
}
// BenchmarkFloatListAppend runs benchmark for float64 by append assignment.
// float64スライスの先頭へ要素を追加するベンチマーク(append使用)
func BenchmarkFloatListAppend(b *testing.B) {
readyFloatList()
b.ResetTimer()
for i := 0; i < b.N; i++ {
floatListAppend()
}
}
func floatListAppend() []float64 {
return append([]float64{1.1}, floatList...)
}
// ==============================
// 3. string スライスの比較
// ==============================
// readyStringList setup string slice for benchmark.
// stringのスライスの初期設定
func readyStringList() {
stringList = make([]string, defaultSize)
for i := 0; i < defaultSize; i++ {
stringList[i] = "hoge"
}
}
// BenchmarkStringListLoop runs benchmark for string by loop index assignment.
// stringスライスの先頭へ要素を追加するベンチマーク(ループインデックス使用)
func BenchmarkStringListLoop(b *testing.B) {
readyStringList()
b.ResetTimer()
for i := 0; i < b.N; i++ {
stringListLoop()
}
}
func stringListLoop() []string {
tmpStringList := make([]string, len(stringList)+1)
tmpStringList[0] = "hoge"
for i := range stringList {
tmpStringList[i+1] = stringList[i]
}
return tmpStringList
}
// BenchmarkStringListAppend runs benchmark for string by append assignment.
// stringスライスの先頭へ要素を追加するベンチマーク(append使用)
func BenchmarkStringListAppend(b *testing.B) {
readyStringList()
b.ResetTimer()
for i := 0; i < b.N; i++ {
stringListAppend()
}
}
func stringListAppend() []string {
return append([]string{"hoge"}, stringList...)
}
// ========================================================
// 4. User構造体(可変長型要素を持った構造体) スライスの比較
// ========================================================
// readyUserList setup User slice for benchmark.
// User のスライスの初期設定
func readyUserList() {
UserList = make([]User, defaultSize)
for i := 0; i < defaultSize; i++ {
UserList[i].ID = i
}
}
// BenchmarkUserListLoop runs benchmark for User by loop index assignment.
// Userスライスの先頭へ要素を追加するベンチマーク(ループインデックス使用)
func BenchmarkUserListLoop(b *testing.B) {
readyUserList()
b.ResetTimer()
for i := 0; i < b.N; i++ {
userListLoop()
}
}
func userListLoop() []User {
tmpUserList := make([]User, len(UserList)+1)
tmpUserList[0] = User{ID: -1}
for i := range UserList {
tmpUserList[i+1] = UserList[i]
}
return tmpUserList
}
// BenchmarkUserListAppend runs benchmark for User by append assignment.
// Userスライスの先頭へ要素を追加するベンチマーク(append使用)
func BenchmarkUserListAppend(b *testing.B) {
readyUserList()
b.ResetTimer()
for i := 0; i < b.N; i++ {
userListAppend()
}
}
func userListAppend() []User {
return append([]User{
User{ID: -1},
}, UserList...)
}
// ==============================
// 5. ポインタ スライスの比較
// ==============================
// readyUserPointerList setup pointer slice for benchmark.
// ポインタのスライスの初期設定
func readyUserPointerList() {
UserPointerList = make([]*User, defaultSize)
for i := 0; i < defaultSize; i++ {
UserPointerList[i] = &User{ID: i}
}
}
// BenchmarkUserPointerListLoop runs benchmark for pointer by loop index assignment.
// ポインタスライスの先頭へ要素を追加するベンチマーク(ループインデックス使用)
func BenchmarkUserPointerListLoop(b *testing.B) {
readyUserPointerList()
b.ResetTimer()
for i := 0; i < b.N; i++ {
userPointerListLoop()
}
}
func userPointerListLoop() []*User {
tmpUserList := make([]*User, len(UserPointerList)+1)
tmpUserList[0] = &User{ID: -1}
for i := range UserPointerList {
tmpUserList[i+1] = UserPointerList[i]
}
return tmpUserList
}
// BenchmarkUserPointerListAppend runs benchmark for pointer by append assignment.
// ポインタスライスの先頭へ要素を追加するベンチマーク(append使用)
func BenchmarkUserPointerListAppend(b *testing.B) {
readyUserPointerList()
b.ResetTimer()
for i := 0; i < b.N; i++ {
userPointerListAppend()
}
}
func userPointerListAppend() []*User {
return append([]*User{
&User{ID: -1},
}, UserPointerList...)
}
// =============================================================
// 6. FixedUser構造体(固定長型要素のみの構造体) スライスの比較
// =============================================================
// readyFixedUserList setup FixedUser slice for benchmark.
// FixedUser のスライスの初期設定
func readyFixedUserList() {
FixedUserList = make([]FixedUser, defaultSize)
for i := 0; i < defaultSize; i++ {
FixedUserList[i].ID = i
}
}
// BenchmarkFixedUserListLoop runs benchmark for FixedUser by loop index assignment.
// FixedUserスライスの先頭へ要素を追加するベンチマーク(ループインデックス使用)
func BenchmarkFixedUserListLoop(b *testing.B) {
readyFixedUserList()
b.ResetTimer()
for i := 0; i < b.N; i++ {
fixedUserListLoop()
}
}
func fixedUserListLoop() []FixedUser {
tmpFixedUserList := make([]FixedUser, len(FixedUserList)+1)
tmpFixedUserList[0] = FixedUser{ID: -1}
for i := range FixedUserList {
tmpFixedUserList[i+1] = FixedUserList[i]
}
return tmpFixedUserList
}
// BenchmarkFixedUserListAppend runs benchmark for FixedUser by append assignment.
// FixedUserスライスの先頭へ要素を追加するベンチマーク(append使用)
func BenchmarkFixedUserListAppend(b *testing.B) {
readyFixedUserList()
b.ResetTimer()
for i := 0; i < b.N; i++ {
fixedUserListAppend()
}
}
func fixedUserListAppend() []FixedUser {
return append([]FixedUser{
FixedUser{ID: -1},
}, FixedUserList...)
}
// ==============================
// 7. [256]byte スライスの比較
// ==============================
// readyFixedByteList setup [256]byte slice for benchmark.
// [256]byte のスライスの初期設定
func readyFixedByteList() {
fixedByteVal = [256]byte{10, 20, 30, 40}
fixedByteList = make([][256]byte, defaultSize)
for i := 0; i < defaultSize; i++ {
fixedByteList[i] = fixedByteVal
}
}
// BenchmarkFixedByteListLoop runs benchmark for [256]byte by loop index assignment.
// [256]byteスライスの先頭へ要素を追加するベンチマーク(ループインデックス使用)
func BenchmarkFixedByteListLoop(b *testing.B) {
readyFixedByteList()
b.ResetTimer()
for i := 0; i < b.N; i++ {
fixedByteListLoop()
}
}
func fixedByteListLoop() [][256]byte {
tmpFixedByteList := make([][256]byte, len(fixedByteList)+1)
tmpFixedByteList[0] = fixedByteVal
for i, _ := range fixedByteList {
tmpFixedByteList[i+1] = fixedByteList[i]
}
return tmpFixedByteList
}
// BenchmarkFixedByteListAppend runs benchmark for [256]byte by append assignment.
// [256]byteスライスの先頭へ要素を追加するベンチマーク(append使用)
func BenchmarkFixedByteListAppend(b *testing.B) {
readyFixedByteList()
b.ResetTimer()
for i := 0; i < b.N; i++ {
fixedByteListAppend()
}
}
func fixedByteListAppend() [][256]byte {
return append([][256]byte{fixedByteVal}, fixedByteList...)
}
// ==============================
// 8. []byte スライスの比較
// ==============================
// readyFixedByteList setup []byte slice for benchmark.
// []byte のスライスの初期設定
func readyByteList() {
byteVal = []byte{10, 20, 30, 40}
byteList = make([][]byte, defaultSize)
for i := 0; i < defaultSize; i++ {
byteList[i] = byteVal
}
}
// BenchmarkByteListLoop runs benchmark for []byte by loop index assignment.
// []byteスライスの先頭へ要素を追加するベンチマーク(ループインデックス使用)
func BenchmarkByteListLoop(b *testing.B) {
readyByteList()
b.ResetTimer()
for i := 0; i < b.N; i++ {
byteListLoop()
}
}
func byteListLoop() [][]byte {
tmpByteList := make([][]byte, len(byteList)+1)
tmpByteList[0] = byteVal
for i, _ := range byteList {
tmpByteList[i+1] = byteList[i]
}
return tmpByteList
}
// BenchmarkByteListAppend runs benchmark for []byte by append assignment.
// []byteスライスの先頭へ要素を追加するベンチマーク(append使用)
func BenchmarkByteListAppend(b *testing.B) {
readyByteList()
b.ResetTimer()
for i := 0; i < b.N; i++ {
byteListAppend()
}
}
func byteListAppend() [][]byte {
return append([][]byte{byteVal}, byteList...)
}
$ go test -bench=. -benchmem
testing: warning: no tests to run
BenchmarkIntListLoop-4 10000 119101 ns/op 483328 B/op 1 allocs/op
BenchmarkIntListAppend-4 10000 103139 ns/op 483328 B/op 1 allocs/op
BenchmarkFloatListLoop-4 10000 116772 ns/op 483328 B/op 1 allocs/op
BenchmarkFloatListAppend-4 10000 101672 ns/op 483328 B/op 1 allocs/op
BenchmarkStringListLoop-4 2000 750787 ns/op 966656 B/op 1 allocs/op
BenchmarkStringListAppend-4 1000 2270381 ns/op 966656 B/op 1 allocs/op
BenchmarkUserListLoop-4 500 2710541 ns/op 3366912 B/op 1 allocs/op
BenchmarkUserListAppend-4 300 4205370 ns/op 3366912 B/op 1 allocs/op
BenchmarkUserPointerListLoop-4 3000 358370 ns/op 483392 B/op 2 allocs/op
BenchmarkUserPointerListAppend-4 2000 519961 ns/op 483392 B/op 2 allocs/op
BenchmarkFixedUserListLoop-4 1000 1576456 ns/op 2883584 B/op 1 allocs/op
BenchmarkFixedUserListAppend-4 1000 1457033 ns/op 2883584 B/op 1 allocs/op
BenchmarkFixedByteListLoop-4 200 6049206 ns/op 15368192 B/op 1 allocs/op
BenchmarkFixedByteListAppend-4 300 5573678 ns/op 15368192 B/op 1 allocs/op
BenchmarkByteListLoop-4 2000 801115 ns/op 1441792 B/op 1 allocs/op
BenchmarkByteListAppend-4 2000 902661 ns/op 1441792 B/op 1 allocs/op
PASS
ok _/path/to/slice_bench 25.385s
Like what you read? Give eureka_developers a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.