Software Engineer Blog

エンジニアブログです。技術情報(Go/TypeScript/k8s)や趣味の話も書くかもです。

Go実装の最適化ゲームをしてみた

概要

同僚が「このコード書ける Java のライブラリない?」 と言ってきたので、
Go で実装し返しました。(遊び)
書いたコードがひどそうだったので、最適化をするゲームをしてみました。
結論、あまりいい感じではないですね。

お題

配列が与えられた際に、 指定した最小/最大サイズの文字列を前から順に結合して取得したい とのことでした。(何言ってるかわからない)

例を挙げるとわかりやすいかと思います。

input: [a, b, c, d, e]  
=> output: [ab, abc, abcd, abcde, bc, bcd, bcde, cd, cde, de]  

実装

パート1

まず、最初に思いついて書いたコードが下記になります。
なんかこう色々まずそうです。
Go Playground

func initialShingle(min, max int, arr []string) []string {
    res := []string{}
    if min > max {
        return res
    }

    for i := 0; i < len(arr); i++ {
        cmin := min
        for j := i; j+cmin < len(arr)+1; j++ {
            if len(arr[i:j+cmin]) > max {
                break
            }
            var s string
            for _, v := range arr[i : j+cmin] {
                s += v
            }
            res = append(res, s)
        }
    }
    return res
}

閑話休題

とりあえず、動作確認のためテストコードを書きます。
min/maxの値の境界値等を Table Drive Test で記載しました。 https://github.com/midorigreen/shingle/blob/master/main_test.go#L35

var cases = []struct {
    in  in
    out []string
}{
    {
        in:  in{min: 2, max: 1, arr: []string{"a", "b", "c", "d", "e"}},
        out: []string{},
    },
    {
        in:  in{min: 2, max: 2, arr: []string{"a", "b", "c", "d", "e"}},
        out: []string{"ab", "bc", "cd", "de"},
    },
    {
        in:  in{min: 2, max: 3, arr: []string{"a", "b", "c", "d", "e"}},
        out: []string{"ab", "abc", "bc", "bcd", "cd", "cde", "de"},
    },
    {
        in:  in{min: 2, max: 5, arr: []string{"a", "b", "c", "d", "e"}},
        out: []string{"ab", "abc", "abcd", "abcde", "bc", "bcd", "bcde", "cd", "cde", "de"},
    },
    {
        in:  in{min: 2, max: 100, arr: []string{"a", "b", "c", "d", "e"}},
        out: []string{"ab", "abc", "abcd", "abcde", "bc", "bcd", "bcde", "cd", "cde", "de"},
    },
}

func TestInitialShingle(t *testing.T) {
    for _, c := range cases {
        res := initialShingle(c.in.min, c.in.max, c.in.arr)
        equal(t, res, c.out)
    }
}

ベンチマークも書いたので、この結果が元になります。

% go test -benchmem -run=^$ github.com/midorigreen/shingle -bench ^BenchmarkInitialShingle$

goos: darwin
goarch: amd64
pkg: github.com/midorigreen/shingle
BenchmarkInitialShingle-4              3         388369200 ns/op        354791952 B/op   4621681 allocs/op
PASS
ok      github.com/midorigreen/shingle  1.513s

パート2

alloc回数を減らすために、返却値の初期化を1回にします。
Go Playground

func shingle2(min, max int, arr []string) []string {
    // 省略

    // for alloc array
    maxLen := len(arr)
    resLen := 0
    for maxLen > 0 {
        resLen += maxLen
        maxLen--
    }
    res := make([]string, resLen)

    // 省略
}

ベンチマーク結果

% go test -bench . -benchmem
goos: darwin
goarch: amd64
pkg: github.com/midorigreen/shingle
BenchmarkInitialShingle-4              3         364788315 ns/op        354790757 B/op   4621679 allocs/op
BenchmarkShingle2-4                    3         484458838 ns/op        355455082 B/op   4621651 allocs/op
PASS
ok      github.com/midorigreen/shingle  4.093s

悪くなってますね..

パート3

slice->stringの処理で文字列結合をしている部分を修正しました。
strings.Join([]string, string) を使ってます。
Go Playground

func shingle3(min, max int, arr []string) []string {
    // 省略

            res = append(res, strings.Join(arr[i:j+cmin], ""))

    // 省略
}

ベンチマーク

% go test -bench . -benchmem
goos: darwin
goarch: amd64
pkg: github.com/midorigreen/shingle
BenchmarkInitialShingle-4              5         330830989 ns/op        354791379 B/op   4621680 allocs/op
BenchmarkShingle2-4                    5         332415947 ns/op        355455014 B/op   4621651 allocs/op
BenchmarkShingle3-4                   20          59744819 ns/op        27479328 B/op     186132 allocs/op
PASS
ok      github.com/midorigreen/shingle  7.958s

速度もalloc回数も改善されました。

(補足) strings.Join()関数

実際の実装を見ると、以下の形になってます。

  • len(array)<=3 までは+で結合している
  • それ以降は、まずスライス長を確保している
    • 結合するのではなくstringをbyte配列にcopyしている
  • copyはstring->[]byteへコピーできる模様 doc
(As a special case, it also will copy bytes from a string to a slice of bytes.) 
// Join concatenates the elements of a to create a single string. The separator string
// sep is placed between elements in the resulting string.
func Join(a []string, sep string) string {
    switch len(a) {
    case 0:
        return ""
    case 1:
        return a[0]
    case 2:
        // Special case for common small values.
        // Remove if golang.org/issue/6714 is fixed
        return a[0] + sep + a[1]
    case 3:
        // Special case for common small values.
        // Remove if golang.org/issue/6714 is fixed
        return a[0] + sep + a[1] + sep + a[2]
    }
    n := len(sep) * (len(a) - 1)
    for i := 0; i < len(a); i++ {
        n += len(a[i])
    }

    b := make([]byte, n)
    bp := copy(b, a[0])
    for _, s := range a[1:] {
        bp += copy(b[bp:], sep)
        bp += copy(b[bp:], s)
    }
    return string(b)
}

感想

あまりいい感じの改善にはならなかったですね。
結局、string結合がボトルネックになっていたのでそこを改善すれば、
速度的にはマシになりました。
strings.Join()の挙動とcopyの挙動を知れたのが収穫です。
(よく考えると、どこがネックになっているかの計測を第一にしないといけなかったですね)

書いたコード

github.com