golang1.5.1のappendのパフォーマンス計測

http://mattn.kaoriya.net/software/lang/go/20150928144704.htm
こちらの記事を参考にベンチマークをいくつか追加して計測してみました。

## makeせずにスライスの先頭に追加を繰り返すとO(N^2)かかる

```go:banck1_test.go
package foo

import(
    "testing"
)

type comment struct {
    ID int
}

var (
    comments []comment
)

func ready() {
    comments = make([]comment, 60000)
    for i := 0; i < len(comments); i++ {
        comments[i].ID = i
    }
}

func BenchmarkTest1(b *testing.B) {
    ready()

    b.ResetTimer()
    hoge := []int{}
    for _, comment := range comments {
        hoge = append([]int{comment.ID}, hoge...)
    }
}

func BenchmarkTest2(b *testing.B) {
    ready()

    b.ResetTimer()
    hoge := []int{}
    for _, comment := range comments {
        hoge = append(hoge, comment.ID)
    }
}

func BenchmarkTest3(b *testing.B) {
    ready()

    b.ResetTimer()
    hoge := make([]int, len(comments))
    for _, comment := range comments {
        hoge = append(hoge, comment.ID)
    }
}

func BenchmarkTest4(b *testing.B) {
    ready()

    b.ResetTimer()
    hoge := make([]int, len(comments))
    l := len(comments)
    for i, j := l-1, 0; i >= 0;i-- {
        hoge[i] = comments[j].ID
        j++
    }
}
```

```zsh:結果1
testing: warning: no tests to run
PASS
BenchmarkTest1-4               1        4000805357 ns/op        14635456312 B/op          122698 allocs/op
BenchmarkTest2-4        2000000000               0.00 ns/op            0 B/op          0 allocs/op
BenchmarkTest3-4        2000000000               0.00 ns/op            0 B/op          0 allocs/op
BenchmarkTest4-4        2000000000               0.00 ns/op            0 B/op          0 allocs/op
```

参考にさせていただいた記事の通り、60000個の処理を行うと、2000000000倍(2億倍)の差が付きました。
理由は
> ループ毎に新しいスライスが作られ、それに対して増えつつある hoge を追加し、さらに hoge を壊して代入する形になります。つまり O(N^2) 回処理されます。

ということです。

## O(N^2)以外の3つの比較

Nを60000000にして、BenchmarkTest1をコメントアウトして実行してみました。

```go:bench2_test.go
package foo

import(
    "testing"
)

type comment struct {
    ID int
}

var (
    comments []comment
)

func ready() {
    comments = make([]comment, 60000000)
    for i := 0; i < len(comments); i++ {
        comments[i].ID = i
    }
}

// func BenchmarkTest1(b *testing.B) {
    // ready()

    // b.ResetTimer()
    // hoge := []int{}
    // for _, comment := range comments {
        // hoge = append([]int{comment.ID}, hoge...)
    // }
// }

func BenchmarkTest2(b *testing.B) {
    ready()

    b.ResetTimer()
    hoge := []int{}
    for _, comment := range comments {
        hoge = append(hoge, comment.ID)
    }
}

func BenchmarkTest3(b *testing.B) {
    ready()

    b.ResetTimer()
    hoge := make([]int, len(comments))
    for _, comment := range comments {
        hoge = append(hoge, comment.ID)
    }
}

func BenchmarkTest4(b *testing.B) {
    ready()

    b.ResetTimer()
    hoge := make([]int, len(comments))
    l := len(comments)
    for i, j := l-1, 0; i >= 0;i-- {
        hoge[i] = comments[j].ID
        j++
    }
}
```

```zsh:結果2
BenchmarkTest2-4               1        1301906279 ns/op        2526498184 B/op       69 allocs/op
BenchmarkTest3-4               1        2040929539 ns/op        3939434752 B/op        9 allocs/op
BenchmarkTest4-4        2000000000               0.08 ns/op            0 B/op          0 allocs/op
```

makeしてもしなくても、末尾でも、appendを60000000回繰り返すと2億倍の差がでました。

## b.Nを使って全部比較

```go:bench3_test.go
package foo

import(
    "testing"
)

type comment struct {
    ID int
}

var (
    comments []comment
)

func ready(n int) {
    comments = make([]comment, n)
    for i := 0; i < len(comments); i++ {
        comments[i].ID = i
    }
}

func BenchmarkTest1(b *testing.B) {
    ready(b.N)

    b.ResetTimer()
    hoge := []int{}
    for _, comment := range comments {
        hoge = append([]int{comment.ID}, hoge...)
    }
}

func BenchmarkTest2(b *testing.B) {
    ready(b.N)

    b.ResetTimer()
    hoge := []int{}
    for _, comment := range comments {
        hoge = append(hoge, comment.ID)
    }
}

func BenchmarkTest3(b *testing.B) {
    ready(b.N)

    b.ResetTimer()
    hoge := make([]int, len(comments))
    for _, comment := range comments {
        hoge = append(hoge, comment.ID)
    }
}

func BenchmarkTest4(b *testing.B) {
    ready(b.N)

    b.ResetTimer()
    hoge := make([]int, len(comments))
    l := len(comments)
    for i, j := l-1, 0; i >= 0;i-- {
        hoge[i] = comments[j].ID
        j++
    }
}

func BenchmarkTest5(b *testing.B) {
    ready(b.N)

    b.ResetTimer()
    hoge := make([]int, len(comments))
    l := len(comments)
    for i, j := l-1, 0; i >= 0;i-- {
        hoge[i] = comments[i].ID
        j++
    }
}
```
```zsh:結果3
BenchmarkTest1-4          200000            303425 ns/op          804081 B/op          2 allocs/op
BenchmarkTest2-4        50000000                24.1 ns/op            40 B/op          0 allocs/op
BenchmarkTest3-4        100000000               44.7 ns/op            65 B/op          0 allocs/op
BenchmarkTest4-4        300000000                4.81 ns/op            8 B/op          0 allocs/op
BenchmarkTest5-4        500000000                4.67 ns/op            8 B/op          0 allocs/op
```

appendでスライスの先頭に繰り返し追加するのはやめたほうがいい。
末尾に追加するならあんまり変わらないけど、makeでallocateしておいてforループで追加していくのが良さそう。