速いしスケールする並列CSVパーサ作った紆余曲折話
年の瀬にどうしてもCSVを並列にパースしたくなって、PartialCsvParserというC++のライブラリを作った。
- 1スレッドでも高速だし複数スレッドで使うとちゃんとスケールする
- ヘッダファイルだけインクルードすればコンパイルなしで使える
- パブリックドメインなので自分のリポジトリに
git addとかしてもおk
という3拍子揃ったやつです。
細かいことはプロジェクトのページを見ていただくとして、ブログには頑張ってベンチマークとった話と、全然スケールしなかったのに2行追加しただけでグンと並列性能が上がった話を書く。
作る前の勝算
CSVの並列パーサライブラリって、ちゃんとスケールするものが割と簡単に作れると思って作り始めた。
例えば2並列にしたいなら、CSVファイルを前半と後半に2分割してあげて、それぞれのスレッドで別々にパースしてあげれば良いだけ。
なぜスケールさせられると思ったかというと、
- 確かにCSVのパーズという(比較的)単純な処理は、ディスクIOが並列性能のボトルネックになりがち
- とはいえこれからはSSDの時代だし、SSDなら並列読込はスケールするって色んなとこで見た気がする
という感じ。
最初からHDDでの並列性能は無視して、SSDで戦おうと思ってた。
作ったらスケールしなかった
バージョン 0.1.0 を作ってみてSSD環境でベンチマークを取ってみたら全然スケールしなかった。寝た。
起きて悔しくなったのでもう一度色々測定してみると、
CSVファイルがページキャッシュに乗っている時、つまりオンメモリな処理をしているときは割とちゃんとスケールすることが分かった。
となるとやっぱりSSDアクセスがボトルネックになっていそう。
少し頭を巡らせパーサの気持ちになって考えてみた。
そもそもPartialCsvParserは、パース対象のCSVファイルをどかんと丸ごとmmap(2)している。
で、複数のスレッドが同じタイミングで離れた領域(ページ)を触りに行く。
このとき、基本的には要求したページがまだメモリに乗っていなくてページフォルトを起こし、ディスクまで取りに行くことになるのだけど、複数のスレッドから同タイミングで「そこそこ離れているけどそんなに離れてはいない」ページを取りに行くことになる。
SSDの気持ちになるとこれはつらい。そもそもSSDが並列性能出るのって、SSDはフラッシュメモリ(板)の集合であって、別々の板のページを同時に要求されたら同時に返せるからってのが基本…なはず。
(SSDチップにもよるけど、)CSVファイルなんてものはサイズもたかが知れているし、同一の板にちょい離れたページを同タイミングで要求しているような気がして、そうするとSSDアクセスがボトルネックになっても仕方がないなという気持ちになった。
じゃあどうしたか
やっぱり複数スレッドから同時にCSVなんて小さいファイルにアクセスしに行くのは大変だろうと思ったので、CSVファイルをドカンと1スレッドでメモリに乗せたくなった。
1スレッドでドカンとやると、ランダムアクセスじゃなくてシーケンシャルアクセスになる。
いくらランダムアクセスに強いと言われるSSDといえど、シーケンシャルアクセスのほうが1桁は速い。
とはいえmmap(2)を捨ててread(2)使うのは、コーディング上面倒くさい。とても面倒くさい。
mmap(2)でシーケンシャルに読みたい、つまりプリフェッチできないもんかなぁ。
と思って探したらmadvise(2)が見つかった。
madvise(2)はカーネルに「この領域はプリフェッチしておいてほしいなぁ(ﾁﾗｯﾁﾗｯ」となんとなーくお願いするためのシステムコール、らしい。
ダメ元で使ってみたプルリクエストがこちら。
たった2行。コメント入れても3行。
これがうまくいって、グンとスケールするようになった。
結局のところ、まだスレッド作ってない段階でガツッとシーケンシャルアクセスしてメモリに乗せるので、
図らずもHDDでもちゃんとスケールするようになった。
ベンチマークを頑張ってとった話
年末で実家にこもれたので、まとまった時間とってそこそこしっかりベンチマークをとれた。
どんな風にベンチマークとったかなどは、ここ にかなりしっかり書いた(つもり)。
ここではすぐに役立ちそうなことを2点ほど。
Google SpreadSheetはデータ集計に超便利
学生時代はExcelとかGnuplot (ｳｯｱﾀﾏｶﾞ) とか使ってベンチマーク結果を集計してたけど、会社でGoogle Drive使うこと増えてきたし、
試しにGoogle SpreadSheetでデータ集計してみた。
これが大当たりで、
- 実験結果の集計に使うレベルならExcelと遜色なく使える
- グラフウィザードがExcelよりなんとなく分かりやすい気がするし、デフォルトのデザインも悪くない
- 生データやグラフを簡単に公開できる。特にグラフは自動で画像ファイルにしてくれたりする
と最高だった。
ディスクのパフォーマンス計測にはがよかった
hdparmとかbonnie++とか、世の中には色々とディスクのベンチマークをとるためのツールが存在している。
そんな中でfioはダントツで使いやすかった。
こんな感じで、短い設定ファイル作ってコマンドライン引数にそれだけ渡せば何かそれっぽい結果が出てくる。
1 | $ vim random-read-mem.fio |
root権限いらないのもポイント高い。
まとめ
2014年も終わろうとしてるのにCSVなんて使う人少ないでしょうけど、どうしてもCSVをパースしたくなったらPartialCsvParserのことを思い出してください。