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

  • このエントリーをはてなブックマークに追加

こんにちは、pairs事業部の山下です。
 
最近はインフラチームから離れて、pairs GlobalチームでPMとして日々を送っています。
 
もちろんエンジニアなので、手が空けば実装もします。
 
そんな中、久しぶりにGoを書いていて、
スライスの先頭に要素を追加(Unshift)したい事案が発生しました。
 
公式wikiのSliceTricksの項では下記のように紹介されております。

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

なるほど、スッキリしていますね。
追加したい要素がスライスに１つだけ入っている状態にして、
その後ろに元のスライスを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

  • このエントリーをはてなブックマークに追加

エウレカでは、一緒に働いていただける方を絶賛募集中です。募集中の職種はこちらからご確認ください！皆様のエントリーをお待ちしております！

Recommend

goji+xorm: Building web api server in golang (part1)

  • このエントリーをはてなブックマークに追加

pairsのeureka、チケットキャンプのフンザ、両CTOが語る急成長サービスを支えるチーム作りとは？

  • このエントリーをはてなブックマークに追加