右上↗

プログラミングに関するメモをのこしていきます

Golang での文字列連結に関するベンチマーク

まず結論

append しよう. bytes.Buffer はそんなに速くない.

きっかけ

こんな記事を見かけました.
Goでは文字列連結はコストの高い操作 - Qiita

buf += "abc" はコストが高いよーっていうお話ですね. これは golang にかぎらず, Javaとかでもよく話題になる一般的な問題だと思います.
Java だと StringBuilder を使うのが良いとされていたと思いますが, golang だと解法がいくつかあるようです.

そこで, 解法をそれぞれ紹介した後, ベンチマーク結果を載せてみたいと思います.

1. 普通に +=

まずは普通に += で連結していく方法です.

func AddString(n int) string {
    base := "abc"
    buf := ""
    for i := 0; i < n; i++ {
        buf += base
    }
    return buf
}

こんな感じですね.
これだと, 確実に n 回メモリ割り当てが発生するので遅いというのが問題となります.

2. append する

golang の string は, メモリ上では []byte と同等の表現を持ちます.
そこで, string を []byte として扱い, golang のスライスを伸長する append 関数を用いるという方法があります.

func AppendString(n int) string {
    base := "abc"
    buf := make([]byte, 0)
    for i := 0; i < n; i++ {
        buf = append(buf, base...)
    }
    return string(buf)
}

make([]byte, 0) によって, 長さ0のスライスを作って, それを伸長していく方法となっています.
このあたりは golang のスライスの表現について知っていないとわかりづらいと思うのですが, わかりやすい説明がいろいろなところで読めるので, ここでは説明しません. append 関数は, スライスの len を必要な分だけ大きくします. また, その結果 len が スライスの cap を超える長さになる場合は, スライスの cap を必要以上に大きくすします.
これは, append を繰り返し適用するような場合(今回のように)に, メモリ割り当ての回数を最小にするためです. 一度の append で大きめにメモリを確保しておくことで, 次の append ではメモリ割り当てをしなくても済む可能性が生まれます.
イメージとしては,

append の回数 0 1 2 3
len 0 3 6 9
cap 0 8 8 16

こんな感じでしょうか(あくまでイメージですが)
append は3回呼ばれていますが, メモリ割り当ては2回に抑えられています.
その分, += よりも速いだろうということですね.

2'. cap を十分量確保しておく

make によるスライスの作成の際には, 長さだけでなくキャパシティを指定することが出来ます.
したがって, はじめから append していった後の最終的なスライスの長さがわかっているのであれば, それをキャパシティに指定することで, メモリ割り当てを最小限に抑えることが可能になります.

func AppendStringWithCap(n int) string {
    base := "abc"
    buf := make([]byte, 0, 3*n)
    for i := 0; i < n; i++ {
        buf = append(buf, base...)
    }
    return string(buf)
}

3. bytes.Buffer を使う

Java の StringBuilder に近い解法ですね.
bytes.Buffer は文字通りバイト列のバッファリングを行ってくれます.
bytes.Buffer に文字列やバイト列を書き込んでいくと, 自動的にメモリ割り当てを減らすように計らってくれます.

func BufferString(n int) string {
    base := "abc"
    var buf bytes.Buffer
    for i := 0; i < n; i++ {
        buf.WriteString(base)
    }
    return buf.String()
}

こんな感じです.

ベンチマーク結果

golang にはベンチマークをとる機能も標準で付いているので, それを利用しました.

package main

import "testing"

const N = 1000

func BenchmarkAddString(b *testing.B) {
    for i := 0; i < b.N; i++ {
        AddString(N)
    }
}

func BenchmarkAppendString(b *testing.B) {
    for i := 0; i < b.N; i++ {
        AppendString(N)
    }
}

func BenchmarkAppendStringWithCap(b *testing.B) {
    for i := 0; i < b.N; i++ {
        AppendStringWithCap(N)
    }
}

func BenchmarkBufferString(b *testing.B) {
    for i := 0; i < b.N; i++ {
        BufferString(N)
    }
}

func TestEquality(t *testing.T) {
    base := AddString(N)
    tests := []string{
        AppendString(N),
        AppendStringWithCap(N),
        BufferString(N),
    }
    for _, test := range tests {
        if base != test {
            t.Fatal("not fair")
        }
    }
}

TestEquality は, すべての方法で正しく文字列を生成できていることを確認するためのテストです. ベンチマークには関係ありません.

結果

上記のファイルを用意した後, go test -bench . -benchmem とした結果を以下に示します.

PASS
BenchmarkAddString-8                5000        348347 ns/op     1592481 B/op        999 allocs/op
BenchmarkAppendString-8           200000          7346 ns/op       13056 B/op         12 allocs/op
BenchmarkAppendStringWithCap-8    300000          5461 ns/op        6144 B/op          2 allocs/op
BenchmarkBufferString-8           100000         16847 ns/op       12256 B/op          8 allocs/op
ok      github.com/agatan/bench 6.881s

というわけで, make の時点で十分なメモリを確保しておく 2' の方法が最も速く最もメモリを消費しないことがわかりました.
まぁ当たり前ですねｗｗ

より注目すべきは, 2 と 4 の結果です. 今回の結果だと, 最終的な文字列の長さがわからない場合, bytes.Buffer よりも append を使ったほうが速いという結果になっています (メモリ使用量は若干 bytes.Buffer のほうが小さい)

メモリ割り当ての回数も bytes.Buffer のほうが少なく済んでいるため, []byte と string の変換など, 文字列連結以外の部分でのオーバーヘッドが大きいため, このような結果になった可能性があります. そこで, N の値を変えて実行してみました.

N = 10 の場合

PASS
BenchmarkAddString-8             2000000           613 ns/op         224 B/op          9 allocs/op
BenchmarkAppendString-8          5000000           270 ns/op          96 B/op          4 allocs/op
BenchmarkAppendStringWithCap-8  10000000           142 ns/op          64 B/op          2 allocs/op
BenchmarkBufferString-8          5000000           251 ns/op         144 B/op          2 allocs/op
ok      github.com/agatan/bench 6.581s

N = 10000 の場合

PASS
BenchmarkAddString-8                  50      28544042 ns/op    160274378 B/op     10039 allocs/op
BenchmarkAppendString-8            20000         71285 ns/op      160768 B/op         20 allocs/op
BenchmarkAppendStringWithCap-8     30000         55262 ns/op       65536 B/op          2 allocs/op
BenchmarkBufferString-8            10000        151665 ns/op      109280 B/op         11 allocs/op
ok      github.com/agatan/bench 7.393s

結論

連結する文字列の長さや連結の回数にもよるが, おおよそ append のほうが速い！！
bytes.Buffer はいつ使えばいいの...