GoCon 2014 Autumn では Why my go program is slow というタイトルで話してきました。
その最後で Go が C より遅くなる原因についてざっくりと説明していたのですが、もっと具体的に、実際に Go が C にボロ負けしているベンチマークを調べて、なぜ Go が遅いのか理由を調べてみたり、あわよくば高速化してしまいましょう。
題材は The Computer Language Benchmarks Game で、 x64 Quad Core 環境で C 言語と比較 したときに負けているワースト3を選びます。
| Benchmark | C CPU | C Elapsed | Go CPU | Go Elapsed |
|---|---|---|---|---|
| Fasta | 5.72 | 1.94 | 7.26 | 7.27 |
| binary-trees | 10.37 | 3.33 | 68.41 | 18.42 |
| regex-dna | 5.81 | 2.44 | 47.40 | 16.27 |
なお、この Benchmark Game は、同じアルゴリズムをそれぞれの言語で実装して速度を測るゲームです。そのため、同一の出力を生成するより速い方法があっても、採用できるとは限りません。
regex-dna
これは、後述する Fasta が出力する大きいファイルに対して、
- 入力のサイズを測る
- 入力から改行やコメント行を削除する
-
2 の結果に対して、以下のそれぞれの正規表現のマッチ数を数える
"agggtaaa|tttaccct", "[cgt]gggtaaa|tttaccc[acg]", "a[act]ggtaaa|tttacc[agt]t", "ag[act]gtaaa|tttac[agt]ct", "agg[act]taaa|ttta[agt]cct", "aggg[acg]aaa|ttt[cgt]ccct", "agggt[cgt]aa|tt[acg]accct", "agggta[cgt]a|t[acg]taccct", "agggtaa[cgt]|[acg]ttaccct", -
2 の結果に対して、以下の左から右への置換をシーケンシャルにかける
{"B", "(c|g|t)"}, {"D", "(a|g|t)"}, {"H", "(a|c|t)"}, {"K", "(g|t)"}, {"M", "(a|c)"}, {"N", "(a|c|g|t)"}, {"R", "(a|g)"}, {"S", "(c|g)"}, {"V", "(a|c|g)"}, {"W", "(a|t)"}, {"Y", "(c|t)"},
このベンチマークは正規表現の速度を測るマイクロベンチになっていて、2~4は同じ正規表現を使わないといけないというルールになっています。
特に単純置換である2と4は普通文字列処理で書くと思うのですが、正規表現を使うことが要求されています。
まず、並列化ができてなくて遅いのか、それとも単純に1コア当たりの性能が悪いのかですが、これは CPU Time (全コアの計算時間を合計した時間) と Elapsed Time (開始から終了までの実時間) を比べれば予測できます。 CPU Time の時点で 7 倍以上の差があり、 Elapsed Time も同じ比率になっているので、純粋な速度が7倍遅くて、並列化は同じくらいされているのでしょう。 (並列化の仕方が悪くて同期コストで CPU を浪費しているという可能性も残っていますが)
利用している正規表現ライブラリを確認すると、 C言語の実装 は、 2 と 4 の置換には glib の正規表現を、 3 のカウントには TCL の正規表現を使っていることが解ります。一方 Go は pcre のバインディングである "github.com/tuxychandru/golang-pkg-pcre/src/pkg/pcre" を使っています。(これは Go の標準ライブラリの regexp がとても遅いからです。。。)
glib や tcl の正規表現の実装を知らないので同じ pcre なのかもしれませんが、場面によって正規表現ライブラリを使い分けてるのを見てるだけで、選択肢の少ない Go では勝ち目がなさそうな気がしてきます。
さらに調べてみると、 pcre には JIT 機能があるのですが、利用している binding では JIT を利用できていません。 glib や tcl が pcre を使っていたとしても、JITが効いているならやはり勝ち目がないでしょう。
pcre binding の改造に手を付けたのですが、APIから変えたいので、ちょっと今回は堪忍してつかーさい。
あと、Windows でも go get しやすい、ポータブルなCで書かれた高速な正規表現エンジンをご存知の方がおられましたら教えてください。
将来的には、 Go のコンパイラと regexp パッケージのチューニングが進んでくれると嬉しいのですが、 JIT を実現するための機能が Go に入らない限りは JIT ありの正規表現エンジンには敵わないでしょう。
binary-trees
これは2分木を作って、トラバースして、捨てる、というベンチマークで、メモリの確保・開放性能を測っています。ルールで自前プールの実装や、GCのチューニングが禁止されています。 とりあえずプログラム上ではどうしようもありません。
(現在の Go の実装ではノードを作成するときに1000個分を一気にスライスとして確保するようなチューニングが入っていますが、再利用はしてないのでギリギリで自前プールに入らないのでしょう。)
ルールに抵触するので提出はできないものの、 GOGC を設定すると GC をチューニングすることができます。 (環境変数だけでなく runtime/debug.SetGCPercent() を使ってコードからも設定可能です。)
$ /usr/bin/time ./bintree 20
...
47.30user 0.29system 0:12.51elapsed 380%CPU (0avgtext+0avgdata 254272maxresident)k
0inputs+0outputs (0major+68892minor)pagefaults 0swaps
$ GOGC=400 /usr/bin/time ./bintree 20
...
23.75user 0.35system 0:06.44elapsed 374%CPU (0avgtext+0avgdata 622124maxresident)k
0inputs+0outputs (0major+164527minor)pagefaults 0swaps
実行速度とメモリ使用量が倍くらいになっているのが解ります。
Fasta
指定された線形合同法で乱数を作り、それを元に重み付けされたアルファベットを選んでDNA列を作れという問題です。
速度をみると、CPU Timeは1.25倍程度しか違わないのに、Elapsed TimeはGoが完全にシングルコアしか使えてないために差が広がって3.75倍の時間がかかっていることが解ります。
Go の実装では乱数の生成とDNA列の生成を同じ関数、同じループで行っているので、行単位のプロファイルを取らないとどれくらい重いのかが分かりにくいです。 GoCon 2014 Autumn で発表した 通り、 "github.com/davecheney/profile" を使ってプロファイルを取ります。
--- a/fasta.go
+++ b/fasta.go
@@ -12,6 +12,7 @@ package main
import (
"bufio"
"flag"
+ "github.com/davecheney/profile"
"os"
"strconv"
)
@@ -100,6 +101,7 @@ func RandomFasta(genelist []AminoAcid, count int) {
}
func main() {
+ defer profile.Start(profile.CPUProfile).Stop()
out = bufio.NewWriter(os.Stdout)
defer out.Flush()
442 448 Total samples (flat / cumulative)
---
. . 82: func RandomFasta(genelist []AminoAcid, count int) {
. . 83: buf := make([]byte, WIDTH+1)
. . 84: for count > 0 {
. . 85: line := min(WIDTH, count)
1 1 86: for pos := 0; pos < line; pos++ {
75 75 87: lastrandom = (lastrandom*IA + IC) % IM
. . 88: // Integer to float conversions are faster if the integer is signed.
38 38 89: r := float64(int(lastrandom)) / IM
235 235 90: for _, v := range genelist {
28 28 91: if v.p >= r {
62 62 92: buf[pos] = v.c
. . 93: break
. . 94: }
. . 95: }
. . 96: }
. . 97: buf[line] = '\n'
3 9 98: out.Write(buf[0 : line+1])
. . 99: count -= line
. . 100: }
. . 101: }
---
このサンプルを完全に信頼できるわけではありませんが、ざっくりとした傾向は分かるはずです。
| 処理 | サンプル数 | 割合(%) |
|---|---|---|
| 線形合同法の計算 | 75 | 16.8 |
| float 型の乱数への変換 | 38 | 8.5 |
| 乱数からDNAの生成 | 325 | 72.7 |
| 出力 | 9 | 2.0 |
さて、この数字を元に並列化を考えてみましょう。DNA生成が3/4近くを占めていて、マシンは4コアなので、線形合同法の部分と float 型への変換は分けなくても4コアを使い切れそうですね。
ただし、乱数生成の順序と出力の順序を壊さないように注意が必要です。
また、このプロファイルは >/dev/null しているので出力が高速ですが、ファイルにリダイレクトしたら、並列化した乱数生成より出力が遅くなる可能性があります。その場合もメモリを食いつぶさないように、出力側が詰まったら生成側の速度が抑制されるようにしておきましょう。
まず、乱数生成と、乱数からDNAを生成するところをそれぞれ関数に切り出します。
const (
IM = 139968
IA = 3877
IC = 29573
)
var lastrandom uint32 = 42
func generateRandom(buf []float64) {
for i := 0; i < len(buf); i++ {
lastrandom = (lastrandom*IA + IC) % IM
buf[i] = float64(lastrandom) / IM
}
}
func generateDna(genelist []AminoAcid, rb []float64, wb []byte) int {
count := len(rb)
i := 0
o := 0
for count > 0 {
line := min(WIDTH, count)
count -= line
for j := 0; j < line; j++ {
r := rb[i]
for _, v := range genelist {
if v.p >= r {
wb[o] = v.c
break
}
}
i++
o++
}
wb[o] = '\n'
o++
}
return o
}
そして元の関数を、チャンク単位に generateRandom() しては、 go generateDna() するように書き換えます。
const (
RANDOM_BUF_SIZE = WIDTH * 1000
OUT_BUF_SIZE = (WIDTH + 1) * 1000
// 1 for output, 4 for generateDna, 1 for generateRandom and 2 spaces
SLOT = 8
)
func RandomFasta(genelist []AminoAcid, count int) {
rbufs := make([][]float64, SLOT)
wbufs := make([][]byte, SLOT)
for i := 0; i < SLOT; i++ {
rbufs[i] = make([]float64, RANDOM_BUF_SIZE)
wbufs[i] = make([]byte, OUT_BUF_SIZE)
}
// Use `chan []byte` as future object. och is queue of future.
och := make(chan chan []byte, 4)
done := make(chan bool)
go func() {
for bc := range och {
buf := <-bc
out.Write(buf)
}
done <- true
}()
for i := 0; count > 0; i++ {
chunk := min(count, RANDOM_BUF_SIZE)
count -= chunk
rb := rbufs[i%SLOT][:chunk]
wb := wbufs[i%SLOT]
generateRandom(rb)
c := make(chan []byte)
och <- c
go func(rb []float64, wb []byte, c chan []byte) {
o := generateDna(genelist, rb, wb)
c <- wb[:o]
}(rb, wb, c)
}
close(och)
<-done
}
出力の順序を維持するために、 chan []byte を future オブジェクトとして扱い、出力 goroutine は och chan chan []byte から chan []byte を受け取って、さらにそこから []byte を受け取るという構造にしています。
この och を大きさ4のバッファードチャンネルにすることで、出力中のチャンク以外に4チャンク分の future オブジェクトを突っ込めます。出力が詰まった場合は、この部分がブロックすることで、乱数生成も止まります。
さて、肝心の性能はというと、
$ time ./fasta-c 25000000 > /dev/null
real 0m1.440s
user 0m4.250s
sys 0m0.012s
$ time ./fasta-go 25000000 > /dev/null
real 0m1.559s
user 0m4.444s
sys 0m0.072s
C言語の速度にかなり近づきました。
ちなみに、C言語の実装では、少しズルい最適化 が行われていて、線形合同法の結果の整数から float の値を作る部分で IM での除算が消えています。これがルール的にOKかどうかは分からないので今回は真似しません。数%の違いはCとGoの速度差ではなくこの最適化のためだと思っておいてください。
まとめ
- Go の正規表現は遅い。 簡単に go get できる pcre JIT か同じくらい高速な正規表現エンジンが欲しい。
- GC は、Cには負けるのは仕方ないにしても、Java並の速度が出ると嬉しい。
- 純粋な計算は、SSEとか出てこない限り C に近い速度が出るし、それを並列化するのはCよりずっと簡単。
追記
Fasta の改良が登録されました
http://benchmarksgame.alioth.debian.org/u64q/program.php?test=fasta&lang=go&id=2