2.6.0とより高速なcsv2018-12-25Rubyの標準添付ライブラリーのcsvをメンテナンスしている須藤です。歴史csvは名前の通りCSVを読み書きするための便利ライブラリーです。1.8.0のときにRuby本体にバンドルするようになりました。dRubyやREXMLがRuby本体にバンドルされたのも同じタイミングです。1.8.0のときにバンドルするライブラリーをすごく増やしたのです。(その頃の様子がわかるURLをここに置いておきたかったけど見つけられなかった。)Rubyではcsvのようにrequireするだけで使えるライブラリーを「標準添付ライブラリー」と呼んでいます。Stringのようにrequireしなくても使えるライブラリーは。組み込みクラスかしら。1.9.0のタイミングで実装をFasterCSVに置き換えました。FasterCSVは名前の通りもともとのcsvよりも速いライブラリーです。csvもFasterCSVもRubyだけで実装してあり、Cを使っていません。Rubyで実装したCSVライブラリーでは最速です。今のcsv(FasterCSVベースのcsv)よりも速いといっているCSVライブラリーはCを使っているはずです。2.6.0に入っています。FasterCSV実装がなぜ速いかFasterCSVがなぜ速いかというと各行をline.split(",")でパースしているからです。String#splitはCで実装されているので速いのです。世の中にはline.split(",")でパースできないCSVがたくさんあります。次のようなCSVです。a,"b,c",dこのCSVではダブルクォートで囲んでいる中にコンマがあるのでline.split(",")では次のようにパースしてしまいます。"d",]このようなケースにも対応するために、FasterCSVはline.split(",")した後の各要素のダブルクォートの数を数えます。ダブルクォートの数が偶数ならダブルクォートの対応が取れていて、奇数なら取れていないというわけです。ダブルクォートの対応が取れていない場合は後続する要素と連結します。このようにして速さを維持したまま複雑なCSVもパースできるようになっています。複雑なCSVをパースするときは速度が落ちてしまいます。次の表はcsvが使っているベンチマークを使ったパース性能の計測結果です。複雑になるほど性能が落ちている(単位時間あたりでのパース回数が減っている)ことがわかります。2.6.0に入っているcsvでは次のようになります。「ダブルクォートあり」の場合は少し性能が落ちています(207から194に減っている)が、ダブルクォート内が複雑になっても「ダブルクォートあり」と性能が変わりません。(「コンマあり」と「改行あり」が193と192で194とほとんど変わらない。)「ダブルクォートなし」の場合は少し性能があがっています。2.6.0のcsvがなぜ速いか「最速」だったcsvがどうやってさらに速くなったかというとStringScannerを使うようになったからです。StringScannerは標準添付ライブラリーの1つで、正規表現を使って高速に文字列をスキャンできます。StringScannerを使っても「最速」だったcsvよりも速くはなりません。line.split(",")は強敵です。requestでも全体的に遅くなっています。これでも高速にするための工夫をした後の結果です。Toolsの開発の集まりなどで@284kmと一緒に高速にするための書き方を模索していました。その結果、次の知見を得ました。どの正規表現を使ってどの順番でスキャンするかが重要StringScannerを使ったコードは次のようなコードになります。ポイントは「次はこういう値が来るはず、来なかったらエラー」というのをつなげていくところです。rowCSVのように複雑なものだと、「次はこういう値が来るはず、来なかったら別のこの値なはず」というようにフォールバックしていきます。「ダブルクォートで囲まれていない値があるはず、なかったらダブルクォートで囲まれた値のはず」といった具合です。line.split(",")を超える性能を出すためにはフォールバックをいかに減らすかが大事になります。フォールバックのオーバーヘッドがあるとline.split(",")に負けてしまうのです。フォールバックを減らすには「次はこういう値が来るはず」ができるだけ当たるような順番にします。カラムの値の次はコンマがきやすいので、次の2つでは後者の方がフォールバックの回数が減ります。rowline.split(",")に勝つには正規表現のマッチ回数をいかに減らすかを頑張る必要があります。これが基本的なコンセプトです。それではさらに具体的な方法を説明していきます。行ごとの処理をやめるline.split(",")ベースのアプローチでは次のようにダブルクォート中が複雑になる処理で性能劣化が大きかったです。82これを解決するために行に分割してから処理することをやめました。行に分割せずに、ダブルクォート中がどうなっていても(たとえば改行文字を含んでいても)統一的に処理することで性能劣化を防ぎました。192これが一番大変でした。いうのは、パースするロジックをすべてStringScannerらしく書き換える必要があるからです。書き換えた後は次のようなコードになりました。endendこれでダブルクォートを使っていても性能劣化しなくなりました。(ダブルクォート中に改行がある方が速くなっているのはなぜだ。187これを実現することによりコードをメンテナンスしやすくなり、最適化や機能追加をしやすくなりました。line.split(",")ベースのコードも200行未満の実装なのでそんなに長すぎるわけではないのですが、状態が多くて適切な場所に適切な処理を入れるのが難しかったのです。以前と同じくらいの性能にできればStringScannerベースのパーサーで開発を進められます。trueにする性能改善の大きなポイントは正規表現のマッチ回数を減らすことですが、それ以外の部分でも少しずつ性能改善できます。endでループするようにすることです。endを使いたいので私は普段は次のようにループを書きます。endを使った方が高速です。endの中でスコープが変わるのでその準備をしないといけないのに対し、whileはスコープが変わらないのでその準備が必要ないからです。trueの方が15%ほど高速です。start]にするStringには文字列データの一部を共有する機能があるため、既存のStringの一部で必要なStringを作れる場合は共有機能を使うことで高速になります。文字列データを共有するにはString#[]を使います。String#[]は便利なメソッドでいろんな引数を受けつけます。次の2つは同じ結果を返します。これは、引数が2つの場合は特別扱いされているためです。5]のスタイルを使った場合の性能改善の度合いは軽微です。409必要になるまで処理を遅らせるみなさんはCSV#lineというメソッドがあるのを知っていますか?私は知りませんでした。このメソッドは最後に処理した行そのもの(パース前の行)を返します。普通はパース結果だけを使うので、この処理のために通常のパース処理が遅くなるのは微妙です。そのため、このための情報を必要になったときにはじめて取得するように変更しました。416微妙に速くなっています。通常は必要ない処理を必要になるまで処理しないことによる高速化はCSVの書き込み処理で顕著です。CSVはCSVを読み書きできるのでインスタンスを作るときに読み書き両方用の初期化をしていました。そのため、CSVを読むだけ、書くだけのときに余計な処理をしていました。この読む用の初期化・書く用の初期化を必要になるまで遅延するようにしました。これにより、読むだけのときは書く用の初期化を一切しなくなり、高速になります。以下は書き込み処理のベンチマーク結果です。35062倍ほど速くなっています。CSV.generate_lineはCSVオブジェクトを作らずに1行生成する便利機能ですが、たくさんの行を生成する時はCSVオブジェクトを作った方が高速です。これは、CSV.generate_lineの場合は1行生成する度に書く用の初期化を毎回しなければいけないためです。次のように書くのは遅いということです。CSV.generate_line(row)endそれよりは次のように書いた方が速いです。outputString#each_charではなくString#indexを使う読む用の初期化時に改行文字を自動検出しているのですが、そこも高速化できた処理でした。従来はString#each_charで一文字ずつ確認していたのですが、そこをString#indexを使って書き換えました。:autoendString#indexを使うとCレベルで文字チェックをできるので速くなりました。(後でどのくらい速くなったか追記できるといいな。)なんか野暮ったいコードなのでもう少しシュッとできるといいですね。効果がなかった高速化これで速くなるんじゃないかと試したものの逆に遅くなったアイディアもありました。特化メソッドを持つモジュールをextendcsvにはまじめにパースするモードとゆるくパースするモードがあります。従来はメソッド内でifで分岐していました。インスタンス作成時にモードにあわせたモジュールをextendしてパース時はメソッド内のifを減らすと速くなるのではないか、という案です。LiberalMode#parse実際にやってみてところむしろ遅くなりました。メソッド内でifで分岐する方が速かったです。速いCSVパーサーcsvはRubyレベルで実装してあるCSVパーサーでは最速です。速くするにはCで実装する必要があります。Cを使っているfastest-csvはcsvよりも数倍高速です。ArrowはCSV用のライブラリーではありませんが、CSVパーサーもついています。ArrowのCSVパーサーを使うとfastest-csvよりもさらに数倍高速です。223使い方も簡単です。次のコードでCSVをロードできます。次のような改良をしていきたいです。興味がある人は一緒に開発しましょう。2.6.0にあわせてcsvのコードを整理して高速化しました。開発しやすいコードベースになったので一緒に開発していきましょう。リリース直前にいろいろ変更をぶちこんでごめんなさい。フリーソフトウェア開発での開発の仕方をベースに、成果や知識を公開し共有しながら業務に携われます。クリアコードのYouTubeチャンネルです。メンバーの登壇動画や、開発プロダクトに関する動画を公開しています。2023をシルバースポンサーとして支援します。DBs」と題して須藤が5月13日に登壇する内容をククログで確認いただけます。Liveで開催しています。4.0とGFDLのデュアルライセンスで自由に利用できます。クリアコードはプログラミングが楽しいソフトウェア開発者を1名募集しています。クリアコードは「クリアコードをいい感じにする人」を1名募集しています。クリアコードはフリーソフトウェア開発で培った技術力を提供しています。Thunderbird)とRubyとGroonga(全文検索)に関連した開発を得意としています。株式会社クリアコード。