Rubyの標準添付ライブラリーのcsvをメンテナンスしている須藤です。

歴史

csvは名前の通りCSVを読み書きするための便利ライブラリーです。

もともとRuby本体とは別に開発されていたのですが、Ruby 1.8.0のときにRuby本体にバンドルするようになりました。dRubyやREXMLがRuby本体にバンドルされたのも同じタイミングです。Ruby 1.8.0のときにバンドルするライブラリーをすごく増やしたのです。（その頃の様子がわかるURLをここに置いておきたかったけど見つけられなかった。。。）

Rubyではcsvのようにrequireするだけで使えるライブラリーを「標準添付ライブラリー」と呼んでいます。Stringのようにrequireしなくても使えるライブラリーは。。。なんだろう。組み込みクラスかしら。

その後、Ruby 1.9.0のタイミングで実装をFasterCSVに置き換えました。FasterCSVは名前の通りもともとのcsvよりも速いライブラリーです。もともとのcsvもFasterCSVもRubyだけで実装してあり、Cを使っていません。Rubyで実装したCSVライブラリーでは最速です。今のcsv（FasterCSVベースのcsv）よりも速いといっているCSVライブラリーはCを使っているはずです。

そんなcsvをさらに速くしたものがRuby 2.6.0に入っています。

FasterCSV実装がなぜ速いか

FasterCSVがなぜ速いかというと各行をline.split(",")でパースしているからです。String#splitはCで実装されているので速いのです。

ただ、世の中にはline.split(",")でパースできないCSVがたくさんあります。たとえば、次のようなCSVです。

a,"b,c",d

このCSVではダブルクォートで囲んでいる中にコンマがあるのでline.split(",")では次のようにパースしてしまいます。

[
  "a",
  "\"b",
  "c\"",
  "d",
]

このようなケースにも対応するために、FasterCSVはline.split(",")した後の各要素のダブルクォートの数を数えます。ダブルクォートの数が偶数ならダブルクォートの対応が取れていて、奇数なら取れていないというわけです。ダブルクォートの対応が取れていない場合は後続する要素と連結します。

このようにして速さを維持したまま複雑なCSVもパースできるようになっています。ただ、複雑なCSVをパースするときは速度が落ちてしまいます。次の表はcsvが使っているベンチマークを使ったパース性能の計測結果です。複雑になるほど性能が落ちている（単位時間あたりでのパース回数が減っている）ことがわかります。

Ruby 2.6.0に入っているcsvでは次のようになります。「ダブルクォートあり」の場合は少し性能が落ちています（207から194に減っている）が、ダブルクォート内が複雑になっても「ダブルクォートあり」と性能が変わりません。（「コンマあり」と「改行あり」が193と192で194とほとんど変わらない。）「ダブルクォートなし」の場合は少し性能があがっています。（373から401に増えている）

Ruby 2.6.0のcsvがなぜ速いか

「最速」だったcsvがどうやってさらに速くなったかというとStringScannerを使うようになったからです。StringScannerは標準添付ライブラリーの1つで、正規表現を使って高速に文字列をスキャンできます。

ただ、単にStringScannerを使っても「最速」だったcsvよりも速くはなりません。line.split(",")は強敵です。@284kmが取り組んだ、まずline.split(",")をStringScannerに置き換えるpull requestでも全体的に遅くなっています。ただ、これでも高速にするための工夫をした後の結果です。Red Data Toolsの開発の集まりなどで@284kmと一緒に高速にするための書き方を模索していました。その結果、次の知見を得ました。

• どの正規表現を使ってどの順番でスキャンするかが重要

StringScannerを使ったコードは次のようなコードになります。ポイントは「次はこういう値が来るはず、来なかったらエラー」というのをつなげていくところです。

row = []
scanner = StringScanner.new(line)
column_value = scanner.scan(/[^",\r\n]+/) # カラムの値
raise "no column value" unless column_value
row << column_value
raise "no comma" unless scanner.scan(/,/) # カラムの区切り文字（コンマ）
column_value = scanner.scan(/[^",\r\n]+/) # 次のカラムの値
raise "no column value" unless column_value
row << column_value
raise "no comma" unless scanner.scan(/,/) # カラムの区切り文字（コンマ）
raise "extra data" unless scanner.eos?    # すべてのデータを使ったか
p row

CSVのように複雑なものだと、「次はこういう値が来るはず、来なかったら別のこの値なはず」というようにフォールバックしていきます。たとえば、「ダブルクォートで囲まれていない値があるはず、なかったらダブルクォートで囲まれた値のはず」といった具合です。

line.split(",")を超える性能を出すためにはフォールバックをいかに減らすかが大事になります。フォールバックのオーバーヘッドがあるとline.split(",")に負けてしまうのです。

フォールバックを減らすには「次はこういう値が来るはず」ができるだけ当たるような順番にします。カラムの値の次はコンマがきやすいので、次の2つでは後者の方がフォールバックの回数が減ります。

カラムの値もコンマも並列に扱う（フォールバックが多い）：

row = []
column_value = nil
until scanner.eos?
  if scanner.scan(/[^",\r\n]+/) # カラムの値
    column_value = scanner.matched
  elsif scanner.scan(/,/) # コンマ
    row << column_value
    column_value = nil
  else
    raise "invalid"
  end
end
row << column_value if column_value
p row

カラムの値の後はコンマがくるはず（フォールバックが少ない）：

row = []
until scanner.eos?
  if (column_value = scanner.scan(/[^",\r\n]+/)) # カラムの値
    if scanner.scan(/,/) or scanner.eos?
      row << column_value
    else
      raise "no comma"
    end
  else
    raise "invalid"
  end
end
p row

line.split(",")に勝つには正規表現のマッチ回数をいかに減らすかを頑張る必要があります。これが基本的なコンセプトです。それではさらに具体的な方法を説明していきます。

行ごとの処理をやめる

line.split(",")ベースのアプローチでは次のようにダブルクォート中が複雑になる処理で性能劣化が大きかったです。

これを解決するために行に分割してから処理することをやめました。

行に分割せずに、ダブルクォート中がどうなっていても（たとえば改行文字を含んでいても）統一的に処理することで性能劣化を防ぎました。

これが一番大変でした。というのは、パースするロジックをすべてStringScannerらしく書き換える必要があるからです。

書き換えた後は次のようなコードになりました。すっきりですね。

row = []
while true
  value = scanner.scan(/[^",\r\n]+/)
  if scanner.scan(/,/)
    row << value
  elsif scanner.scan(/\r\n/)
    row << value
    p row
    row = []
  elsif scanner.eos?
    row << value
    p row
    return
  else
    raise "invalid"
  end
end

これでダブルクォートを使っていても性能劣化しなくなりました。（ダブルクォート中に改行がある方が速くなっているのはなぜだ。。。）

これを実現することによりコードをメンテナンスしやすくなり、最適化や機能追加をしやすくなりました。line.split(",")ベースのコードも200行未満の実装なのでそんなに長すぎるわけではないのですが、状態が多くて適切な場所に適切な処理を入れるのが難しかったのです。

以前と同じくらいの性能にできればStringScannerベースのパーサーで開発を進められます。

loopをwhile trueにする

性能改善の大きなポイントは正規表現のマッチ回数を減らすことですが、それ以外の部分でも少しずつ性能改善できます。その1つでやりやすいものがloop do ... endではなくwhile true ... endでループするようにすることです。

Rubyを使っている場合はdo ... endを使いたいので私は普段は次のようにループを書きます。

loop do
  # ...
end

しかし、今回のように性能改善したいケースでは次のようにwhile true ... endを使った方が高速です。これはloopだとdo ... endの中でスコープが変わるのでその準備をしないといけないのに対し、whileはスコープが変わらないのでその準備が必要ないからです。

while true
  # ...
end

csvのケースではwhile trueの方が15%ほど高速です。

100msでのパース回数：

string[start...end]をstring[start, end - start]にする

Stringには文字列データの一部を共有する機能があるため、既存のStringの一部で必要なStringを作れる場合は共有機能を使うことで高速になります。

文字列データを共有するにはString#[]を使います。String#[]は便利なメソッドでいろんな引数を受けつけます。たとえば、次の2つは同じ結果を返します。

string[1...6]
string[1, 5]

ただし、string[1, 5]の方が速いです。これは、引数が2つの場合は特別扱いされているためです。

csvの場合、string[1, 5]のスタイルを使った場合の性能改善の度合いは軽微です。

必要になるまで処理を遅らせる

みなさんはCSV#lineというメソッドがあるのを知っていますか？私は知りませんでした。このメソッドは最後に処理した行そのもの（パース前の行）を返します。普通はパース結果だけを使うので、この処理のために通常のパース処理が遅くなるのは微妙です。そのため、このための情報を必要になったときにはじめて取得するように変更しました。

微妙に速くなっています。

通常は必要ない処理を必要になるまで処理しないことによる高速化はCSVの書き込み処理で顕著です。

CSVはCSVを読み書きできるのでインスタンスを作るときに読み書き両方用の初期化をしていました。そのため、CSVを読むだけ、書くだけのときに余計な処理をしていました。

この読む用の初期化・書く用の初期化を必要になるまで遅延するようにしました。これにより、読むだけのときは書く用の初期化を一切しなくなり、高速になります。

以下は書き込み処理のベンチマーク結果です。

100msでの処理回数：

2倍ほど速くなっています。CSV.generate_lineはCSVオブジェクトを作らずに1行生成する便利機能ですが、たくさんの行を生成する時はCSVオブジェクトを作った方が高速です。これは、CSV.generate_lineの場合は1行生成する度に書く用の初期化を毎回しなければいけないためです。

つまり、次のように書くのは遅いということです。

rows.each |row|
  puts CSV.generate_line(row)
end

それよりは次のように書いた方が速いです。

output = ""
csv = CSV.new(output)
rows.each |row|
  csv << row
end
puts output

String#each_charではなくString#indexを使う

読む用の初期化時に改行文字を自動検出しているのですが、そこも高速化できた処理でした。

従来はString#each_charで一文字ずつ確認していたのですが、そこをString#indexを使って書き換えました。次のような感じです。

cr_index = sample.index("\r")
lf_index = sample.index("\n")
if cr_index and lf_index
  if cr_index + 1 == lf_index
    "\r\n"
  elsif cr_index < lf_index
    "\r"
  else
    "\n"
  end
elsif cr_index
  "\r"
elsif lf_index
  "\n"
else
  :auto
end

String#indexを使うとCレベルで文字チェックをできるので速くなりました。（後でどのくらい速くなったか追記できるといいな。）

なんか野暮ったいコードなのでもう少しシュッとできるといいですね。

効果がなかった高速化

これで速くなるんじゃないかと試したものの逆に遅くなったアイディアもありました。

特化メソッドを持つモジュールをextend

csvにはまじめにパースするモードとゆるくパースするモードがあります。従来はメソッド内でifで分岐していました。インスタンス作成時にモードにあわせたモジュールをextendしてパース時はメソッド内のifを減らすと速くなるのではないか、という案です。こんな感じです。

module StrictMode
  def parse
    # ...
  end
end

module LiberalMode
  def parse
    # ...
  end
end

class CSV::Parser
  def initialize(options)
    if @options[:liberal_mode]
      extend LiberalMode
    else
      extend StrictMode
    end
  end
end

CSV::Parser.new(:liberal_mode).parse # LiberalMode#parse

実際にやってみてところむしろ遅くなりました。メソッド内でifで分岐する方が速かったです。

さらに速いCSVパーサー

csvはRubyレベルで実装してあるCSVパーサーでは最速です。さらに速くするにはCで実装する必要があります。たとえば、Cを使っているfastest-csvはcsvよりも数倍高速です。

なお、私のオススメはApache Arrowです。Apache ArrowはCSV用のライブラリーではありませんが、CSVパーサーもついています。Apache ArrowのCSVパーサーを使うとfastest-csvよりもさらに数倍高速です。

使い方も簡単です。次のコードでCSVをロードできます。

require "arrow"
Arrow::Table.load("/tmp/a.csv")

参考：Apache Arrowの最新情報（2018年9月版）

今後

コードを整理でき、最適化・機能拡張の準備ができました。たとえば、次のような改良をしていきたいです。興味がある人は一緒に開発しましょう。

• バックスラッシュでダブルクォートをエスケープ #61

• クォート文字を指定しなかったらline.split(",")を使う高速化 #56

• ヘッダーがあるときの高速化 #59

まとめ

Ruby 2.6.0にあわせてcsvのコードを整理して高速化しました。より開発しやすいコードベースになったので一緒に開発していきましょう。

リリース直前にいろいろ変更をぶちこんでごめんなさい。

ツイートする

フォローする