Go
GoDay 4

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

この記事は、Go Advent Calendar 2018の4日目の記事です。実は5日目も投稿したのですが、カレンダーが空いてた&貯めてた記事あったのでここで投稿します!

3日目はkechakoさんの UDP サーバーでクライアント毎に net.Conn を作る #golang でした!

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

LT;DL

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

strings.Builder の中を確認する

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

strings.Builder

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

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

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

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

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...)
    }
}

$ 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 の実装をもう一度みてみましょう。

// 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
}

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

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

strings.Builder.Grow

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

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

// 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...)
    }
}
$ 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 は使いまわせる。特定の文字列を作成したら、ビルダーをリセットして新しい文字列を作成することもできます。

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