文字列連結はどれが速い?

(初出: Golang の文字列連結はどちらが速い? - Qiita

前回につづき string の話題。 Go 言語で文字列の連結を行う際にどうやるのが一番速いか,という話。

【2019-10-13 追記】 改訂版を公開しました。

文字列連結を行う4つの方法

Go 言語で文字列の連結を行う際には概ね以下の4つの方法がある。

  1. +” 演算子で連結する
  2. strings.Join で連結する
  3. bytes.Buffer に追記する
  4. []byteappend する

string は「不変(immutable)」なので,最初の2つが高コストになるだろうことはすぐに想像がつく。

では残りの2つはどうなのかというと

によると最後のが一番速いらしい。ほんじゃまぁ,確かめてみるか。

サンプルコードを用意

以下のコード join.go を使って評価してみる。

package main

import (
    "bufio"
    "bytes"
    "io"
)

//Read content (text data) from buffer
func ContentText(inStream io.Reader) ([]string, error) {
    scanner := bufio.NewScanner(inStream)
    list := make([]string, 0)
    for scanner.Scan() {
        list = append(list, scanner.Text())
    }
    if err := scanner.Err(); err != nil {
        return nil, err
    }
    return list, nil
}

//Write content (text data) to buffer
func WriteBuffer1(lines []string) []byte {
    //write to byte buffer
    content := make([]byte, 0)
    recode := "\r\n"
    for _, line := range lines {
        content = append(content, line...)
        content = append(content, recode...)
    }
    return content
}

//Write content (text data) to buffer
func WriteBuffer1Cap128(lines []string) []byte {
    //write to byte buffer
    content := make([]byte, 0, 128) //128 bytes capacity
    recode := "\r\n"
    for _, line := range lines {
        content = append(content, line...)
        content = append(content, recode...)
    }
    return content
}

//Write content (text data) to buffer
func WriteBuffer1Cap1K(lines []string) []byte {
    //write to byte buffer
    content := make([]byte, 0, 1024) //1K bytes capacity
    recode := "\r\n"
    for _, line := range lines {
        content = append(content, line...)
        content = append(content, recode...)
    }
    return content
}

//Write content (text data) to buffer (buffered I/O)
func WriteBuffer2(lines []string) []byte {
    //write to byte buffer
    content := bytes.NewBuffer(make([]byte, 0))
    recode := "\r\n"
    for _, line := range lines {
        content.WriteString(line)
        content.WriteString(recode)
    }
    return content.Bytes()
}

//Write content (text data) to buffer (buffered I/O)
func WriteBuffer2Cap128(lines []string) []byte {
    //write to byte buffer
    content := bytes.NewBuffer(make([]byte, 0, 128)) //128 bytes capacity
    recode := "\r\n"
    for _, line := range lines {
        content.WriteString(line)
        content.WriteString(recode)
    }
    return content.Bytes()
}

//Write content (text data) to buffer (buffered I/O)
func WriteBuffer2Cap1K(lines []string) []byte {
    //write to byte buffer
    content := bytes.NewBuffer(make([]byte, 0, 1024)) //1K bytes capacity
    recode := "\r\n"
    for _, line := range lines {
        content.WriteString(line)
        content.WriteString(recode)
    }
    return content.Bytes()
}

テストコード join_test.go はこんな感じ。

package main

import (
    "os"
    "testing"
)

func readFile() []string {
    file, err := os.Open("CollisionsForHashFunctions.txt") //maybe file path
    if err != nil {
        panic(err)
    }
    defer file.Close()
    list, err := ContentText(file)
    if err != nil {
        panic(err)
    }
    return list
}

func BenchmarkWriteBuffer1(b *testing.B) {
    list := readFile()
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        content := WriteBuffer1(list)
        _ = string(content)
    }
}

func BenchmarkWriteBuffer1Cap128(b *testing.B) {
    list := readFile()
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        content := WriteBuffer1Cap128(list)
        _ = string(content)
    }
}

func BenchmarkWriteBuffer1Cap1K(b *testing.B) {
    list := readFile()
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        content := WriteBuffer1Cap1K(list)
        _ = string(content)
    }
}

func BenchmarkWriteBuffer2(b *testing.B) {
    list := readFile()
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        content := WriteBuffer2(list)
        _ = string(content)
    }
}

func BenchmarkWriteBuffer2Cap128(b *testing.B) {
    list := readFile()
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        content := WriteBuffer2Cap128(list)
        _ = string(content)
    }
}

func BenchmarkWriteBuffer2Cap1K(b *testing.B) {
    list := readFile()
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        content := WriteBuffer2Cap1K(list)
        _ = string(content)
    }
}

Go 言語のテストについては以前紹介したが,同じ要領で Benchmark から始まる名前の関数を作るとベンチマーク用のコードとして認識される。 引数には b *testing.B を指定する。

ベンチマークの内訳は以下のとおり。

ベンチマーク名 処理内容
BenchmarkWriteBuffer1 []byteappend する
BenchmarkWriteBuffer1Cap128 []byteappend する( capacity 128B)
BenchmarkWriteBuffer1Cap1K []byteappend する( capacity 1KB)
BenchmarkWriteBuffer2 bytes.Buffer に追記する
BenchmarkWriteBuffer2Cap128 bytes.Buffer に追記する( capacity 128B)
BenchmarkWriteBuffer2Cap1K bytes.Buffer に追記する( capacity 1KB)

入力テキストだが,小さいファイルではテストにならない気がしたので,大昔に書いたテキスト CollisionsForHashFunctions.txt を使うことにした。 サイズは70行,7KB ほど。

テスト結果

結果は以下のとおり。

C:>go test -bench WriteBuffer -benchmem
testing: warning: no tests to run
PASS
BenchmarkWriteBuffer1-8           100000         17831 ns/op       37056 B/op     12 allocs/op
BenchmarkWriteBuffer1Cap128-8     100000         20321 ns/op       36992 B/op     11 allocs/op
BenchmarkWriteBuffer1Cap1K-8      100000         19301 ns/op       36096 B/op      8 allocs/op
BenchmarkWriteBuffer2-8           100000         17300 ns/op       33760 B/op     10 allocs/op
BenchmarkWriteBuffer2Cap128-8     100000         19451 ns/op       34992 B/op      9 allocs/op
BenchmarkWriteBuffer2Cap1K-8      100000         15490 ns/op       25712 B/op      6 allocs/op
ok      join    12.659s

ありゃりゃ。 bytes.Buffer を使ったほうが速いみたい(capacity を大きくとれば)。

それなら,入力テキストを切り詰めて10行,0.3KB にしてやってみる。

C:>go test -bench WriteBuffer -benchmem
testing: warning: no tests to run
PASS
BenchmarkWriteBuffer1-8          2000000           859 ns/op        1312 B/op      5 allocs/op
BenchmarkWriteBuffer1Cap128-8    2000000           707 ns/op        1248 B/op      4 allocs/op
BenchmarkWriteBuffer1Cap1K-8     2000000           796 ns/op        1376 B/op      2 allocs/op
BenchmarkWriteBuffer2-8          1000000          1686 ns/op        1600 B/op      6 allocs/op
BenchmarkWriteBuffer2Cap128-8    1000000          1411 ns/op        1680 B/op      5 allocs/op
BenchmarkWriteBuffer2Cap1K-8     2000000           980 ns/op        1488 B/op      3 allocs/op
ok      join    13.589s

今度は []byte の方が速くなった。

まぁでも予想通りかな。 データのサイズが大きくなればバッファ操作のほうが有利になるのは分かりやすいっちゃあ分かりやすい。

注目すべきは BenchmarkWriteBuffer1Cap128BenchmarkWriteBuffer1Cap1K で, capacity を 1KB 取ったほうが若干遅くなっている。この辺のチューニングをどうするか,というところなのだろう(実はこれ,環境によって微妙に順位が変わるんだよなぁ)。

ブックマーク

参考図書

photo
プログラミング言語Go (ADDISON-WESLEY PROFESSIONAL COMPUTING SERIES)
Alan A.A. Donovan (著), Brian W. Kernighan (著), 柴田 芳樹 (翻訳)
丸善出版 2016-06-20
単行本(ソフトカバー)
4621300253 (ASIN), 9784621300251 (EAN), 4621300253 (ISBN), 9784621300251 (ISBN)
評価     

著者のひとりは(あの「バイブル」とも呼ばれる)通称 “K&R” の K のほうである。この本は Go 言語の教科書と言ってもいいだろう。

reviewed by Spiegel on 2016-07-13 (powered by PA-APIv5)