Goを遅くしないための地味な話

この記事はGunosy Advent Calendar 2017の13日目の記事です。

広告技術部の@harahenikuです。主な業務はGoによる広告配信APIの開発です。たまにPythonとかDjangoとかもやってます。

Goは速いですが遅いコードをかけば当然遅くなってしまいます。この記事ではGoのプログラムを遅くしないために、実際に行ったチューニングを幾つか紹介したいと思います。

スライスの処理

長さを指定する

スライスの初期化は次のようなコードはappendでallocが発生します。

feature := []VectorEntry{}
for i, v := range vec {
    e := VectorEntry{ 
        ID: i+stride,
        Value: v, 
    }
    feature = append(feature, e) 
}

appendでallocされないように、makeでcapsを予め指定するようにします。

feature := make([]VectorEntry, 0, len(vec))
for i, v := range vec {
    e := VectorEntry{ 
        ID: i+stride,
        Value: v, 
    }
    feature = append(feature, e) 
}

あるいは、lengthを指定して添字アクセスで初期化します。

feature := make([]VectorEntry, len(vec))
for i, v := range vec {
    feature[i].ID = i+stride
    feature[i].Value = v
}

ソートが必要なスライスは要素をポインタにする

ソートを実行すると要素の移動のためコピーが行われるので、要素のデータサイズが大きくてコピーのコストが高いとソート処理の性能が劣化します。そのためソートが必要でデータサイズが大きい構造体のスライスは、ポインタ型のスライスにすることを検討します。

appendをやめる

複数の長いスライスを結合したい場合、次のようなコードでコピーのコストがネックになった時がありました。

f = append(f, Ad...)
f = append(f, Frame...)
f = append(f, User...)

// 中略

for _, e := range f {
    // 要素を処理
}

この際は、ソートが不要だったのでappendを諦めて二次配列にしました。可読性が若干犠牲になりましたが、コピーの分のコストが減り速度が改善しました。

f := [][]VectorEntry{Ad, Frame, User}

// 中略

for _, x := range f {
    for _, x := range x {
        // 要素を処理
    }
}

文字列のパース

コロン区切りのidとvalueをペアをタブで区切ったテキスト形式で、疎なベクトルを保存してGoでパースしています。

1265:1.0    17853:1.0   68120:1.0   76293:1.0

バイナリ形式にしてしまえばパースも速いのですが、テキスト形式のほうがデータストアに保存されている値の確認が容易なのと、殆どのベクトルデータはあらかじめキャッシュしてしまうのでパースのコストはある程度無視することができます。とはいえリクエスト時に取得しなければいけないベクトルもあるのでパースのコストを小さいに越したことはありません。

まずはstrings.Splitとfmt.Sscanfで実装しました。

func scanWithSplit(s string) (SparseVector, error) {
    var vec []VectorEntry
    for _, word := range strings.Split(s, "\t") {
        var entry VectorEntry
        if _, err := fmt.Sscanf(word, "%d:%f", &entry.ID, &entry.Value); err != nil {
            return nil, err
        }
        vec = append(vec, entry)
    }
    return vec, nil
}

この実装ではstrings.Splitで一度ペアをスライスに展開しているため、無駄なallocが発生します。そこでstrings.IndexByteとstrings.IndexFuncを使って書き直しました。

func scanWithIndex(s string) (SparseVector, error) {
    // 空文字列の場合はパースせずに空の値を返す
    if len(s) == 0 {
        return vec, nil
    }

    var vec []VectorEntry
    end := false
    for {
        // ID部のパース
        i := strings.IndexByte(s, ':')
        if i < 0 {
            return nil, errors.New("predict: scan error")
        }
        id, err := strconv.Atoi(s[:i])
        if err != nil {
            return nil, err
        }
        s = s[i+1:]

        // 値部のパース
        i = strings.IndexByte(s, '\t')
        var v float64
        if i > 0 {
            v, err = strconv.ParseFloat(s[:i], 64)
            s = s[i+1:]
        } else {
            v, err = strconv.ParseFloat(s, 64)
            // 終端まで探索されたのでパースを終了する
            end = true
        }
        if err != nil {
            return nil, err
        }
        vec = append(vec, VectorEntry{id, v})

        // 終端に達していたら終了
        if end {
            break
        }
        // タブのスキップ
        i = strings.IndexFunc(s, func(c rune) bool { return c != '\t' })
        if i > 0 {
            s = s[i:]
        }
    }
    return vec, nil
}

ベクトルの要素の数によって変わりますが、ベンチマークでは次のような結果がでました。

処理速度は10~15倍
allocの回数が10~400分の1
要素が増えても性能が著しく劣化しなくなった

$ go test -benchmem -bench .
goos: darwin
goarch: amd64
pkg: github.com/aita/gojunks/scan
BenchmarkScanWithSplit-4           10000            189459 ns/op           15458 B/op        434 allocs/op
BenchmarkScanWithIndex-4          100000             12450 ns/op            4080 B/op          8 allocs/op
PASS
ok      github.com/aita/gojunks/scan    3.337s

十分な改善ができたので、前述で述べたように予めcapsを指定しておくなど、まだ改善できる点はありますがこれで一旦OKとしました。

まとめ

一部ですが実際に開発を通して行ったチューニングを紹介しました。

このほかにも広告技術部で行ったキャッシュ戦略について、こちらの記事がグノシーのブログに投稿されているのでご覧いただけたら幸いです。