Go言語の strings.Builder による文字列の連結の最適化とベンチマーク

この記事は、Go Advent Calendar 2018の4日目の記事です。実は[5日目](https://qiita.com/po3rin/items/a19d96d29284108ad442)も投稿したのですが、カレンダーが空いてた&貯めてた記事あったのでここで投稿します！

3日目はkechakoさんの [UDP サーバーでクライアント毎に net.Conn を作る #golang ](https://blog.kechako.com/entry/create-udp-conn-each-client) でした！

文字列結合が大量に発生すると、Go言語であろうとさすがにコストが高くなる。
そこで Go1.10 から実装された ```strings.Builder``` を試し、ベンチマークをとってみる。

## LT;DL

```strings.Builder``` を使った文字列結合は、普通に ```+=``` 使うよりは断然早い！キャパシティの付加する ```strings.Builder.Grow()``` を使って前もってキャパシティを確保しておく方法が観測上は最速、使い心地も良い。

## strings.Builder の中を確認する

```strings.Builder```は、Writeメソッドを使用して文字列等を効率的に構築するために使用されます。```strings.Builder``` 自体はexportableなフィールドがない構造体です。

[strings.Builder](https://golang.org/pkg/strings/#Builder)

```go
type Builder struct {
    addr *Builder // of receiver, to detect copies by value
	buf  []byte
}
```

内側に []byte が定義されています。

bufにappendしていく為の ```builder.WriteString()```がある。中では単純に```Builder.buf```に対して append が動いている。

[strings.Builder.WriteString](https://golang.org/pkg/strings/#Builder.WriteString)

```go
func (b *Builder) WriteString(s string) (int, error) {
	b.copyCheck()
	b.buf = append(b.buf, s...)
	return len(s), nil
}
```

```Builder.buf``` に append してきたものを最後にstring型にして返せば連結後の文字列が出来上がりという仕様。

[strings.Builder.String](https://golang.org/pkg/strings/#Builder.String)

```go
// String returns the accumulated string.
func (b *Builder) String() string {
	return *(*string)(unsafe.Pointer(&b.buf))
}
```

さて一旦ここでベンチマークも含めて実際の使い方をみてみましょう。

```go
package Builder_test

import (
	"strings"
	"testing"
)

// 愚直に += による実装
func joinWithPlus(strs ...string) string {
	var ret string
	for _, str := range strs {
		ret += str
	}
	return ret
}

// Builder.Builder による実装
func joinWithBuilder(strs ...string) string {
	var sb strings.Builder
	for _, str := range strs {
		sb.WriteString(str)
	}
	return sb.String()
}

// 愚直に += による実装 のベンチマーク
func BenchmarkPlus(b *testing.B) {
	strs := []string{"aaa", "bbb", "ccc", "ddd", "eee", "fff", "ggg", "hhh", "iii"}

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		_ = joinWithPlus(strs...)
	}
}

// Builder.Builder による実装 のベンチマーク
func BenchmarkBuilder(b *testing.B) {
	strs := []string{"aaa", "bbb", "ccc", "ddd", "eee", "fff", "ggg", "hhh", "iii"}

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		_ = joinWithBuilder(strs...)
	}
}

```

```bash
$ go test -bench . -benchmem

goos: darwin
goarch: amd64
pkg: go-playground/benchmark/Builder
BenchmarkPlus-12              	 5000000	       292 ns/op	     176 B/op	       8 allocs/op
BenchmarkBuilder-12           	20000000	       114 ns/op	      56 B/op	       3 allocs/op
```

一番上が += を使った連結。二番目はstrings.Builderを使った方法。
さすがに Builder.Bulder の方が早い！しかし、まだアロケーションが数回起こってる。

## キャパシティ付き[]byteへのappendの方が早いでしょ！

```strings.Builder.WriteString``` の実装をもう一度みてみましょう。

```go
// in src/strings/builder.go

type Builder struct {
    addr *Builder // of receiver, to detect copies by value
	buf  []byte
}

// ...

func (b *Builder) WriteString(s string) (int, error) {
	b.copyCheck()
	b.buf = append(b.buf, s...)
	return len(s), nil
}
```

実態は```[]byte```に```append()```している形なので、キャパシティ付き[]byte の方がアロケーション数も減り、確実にコストは低くできる！

早速 ```strings.Builder.buf``` の容量を設定したいが、```strings.Builder.buf``` には直でアクセスできない。しかし大丈夫。キャパシティを付与する Grow メソッドが提供されている。

[strings.Builder.Grow](https://golang.org/pkg/strings/#Builder.Grow)

```go
func (b *Builder) Grow(n int) {}
```

引数に渡した数だけbufの容量を確保する。これでキャパシティ付き[]byteが設定できる。早速ベンチマークをとってみる。

```go
// Growを使って　capsを確保した文字列結合
func joinWithBuilderAndGrow(strs ...string) string {
	var sb strings.Builder
	sb.Grow(30)
	for _, str := range strs {
		sb.WriteString(str)
	}
	return sb.String()
}

func BenchmarkBuilderAndGrow(b *testing.B) {
	strs := []string{"aaa", "bbb", "ccc", "ddd", "eee", "fff", "ggg", "hhh", "iii"}

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		_ = joinWithBuilderAndGrow(strs...)
	}
}
```

```bash
$ go test -bench . -benchmem

goos: darwin
goarch: amd64
pkg: go-playground/benchmark/Builder
BenchmarkPlus-12              	 5000000	       289 ns/op	     176 B/op	       8 allocs/op
BenchmarkBuilder-12           	20000000	       119 ns/op	      56 B/op	       3 allocs/op
BenchmarkBuilderAndGrow-12    	20000000	        64.7 ns/op	      32 B/op	       1 allocs/op
```

一番上が += を使った連結。二番目は```strings.Builder```を使っているがGrowメソッドを使っていない。三番目はGrowも使っている。結果としてはアロケーションも減り、当然パフォーマンスも上がっている！！にくいね！！strings.Builder！！

### strings.Builder についてちょっと便利なメソッド
1回初期化した ```strings.Builder``` は使いまわせる。特定の文字列を作成したら、ビルダーをリセットして新しい文字列を作成することもできます。

```go
func joinedAndReverse(strs ...string) (string, string) {
	var sb strings.Builder
	for _, str := range strs {
		sb.WriteString(str)
	}
    joined := sb.String()

    // Reset呼んで strings.Builder.buf をnil　にする
	sb.Reset()
	for i := len(strs) - 1; i >= 0; i-- {
		sb.WriteString(strs[i])
	}
	return joined, sb.String()
}
```

## まとめ

strings.Builder便利！

ちょっと古いが、いろんな文字列結合を試した下記の記事も面白いので是非。下の記事で紹介されている最速の方法(キャパシティ指定付き[]byte)と Grow を使った方法はほぼ同等の結果だった（実装がほぼ同じだしね）。
https://qiita.com/ono_matope/items/d5e70d8a9ff2b54d5c37

## 追記

投稿してから気づいたんだけど、過去のtenntennさんの記事とモロ被りしてた。こっちの方がbytes.Bufferと比較してたりと詳しい。こちらもどうぞ！！
[Go1.10で入るstrings.Builderを検証した #golang](https://qiita.com/tenntenn/items/94923a0c527d499db5b9)