ScalaのRegexParsersがすごく遅くなる件の原因と対策（version 1.0.2で修正されました）

追記： この問題はversion 1.0.2で修正されました。

https://groups.google.com/d/topic/scala-announce/AnIPnB1rfUQ/discussion
http://repo1.maven.org/maven2/org/scala-lang/modules/scala-parser-combinators_2.11/1.0.2/

Scala 2.11からscala-parser-combinatorsは別jarになってますのでサクッとbuild.sbtを書き換えて修正できるようです。

RegexParsersでCSVパーサを書いていました

テストコードはパスして、実際にある程度のサイズのファイルを食べさせてみると、すごく遅い。まあそんなものなのかなぁと一晩放置すると

java.lang.OutOfMemoryError: Java heap space

となりました。

VisualVMでプロファイルしたものが以下です

Reader1WithParser1

Regex.findPrefixMatchOf()がほとんどの時間を占めていて、char[]の消費がすごい。

調べてみると該当するIssueが見つかりました

どうやらJavaのStringに関する仕様変更をまともに食らったらしく、メモリパフォーマンスがO(入力長)！！になってしまった模様。修正パッチはマージされていますが、単純にRegexParsers.scala has O(inputlength) memory performance on java >= 7u6に書かれているFastCharSequenceを参考にArray[Char]をラップして、RegexParsers.parseまたはRegexParsers.parseAllに渡せばよさそうです。charAtのindexが負の場合のチェックが抜けてますので、そこを修正して

FastCharSequence.scala

/**
 * https://issues.scala-lang.org/browse/SI-7710
 */
class FastCharSequence(chars: Array[Char], val sb: Int, val eb: Int) extends CharSequence {
  def this(chars: Array[Char]) = this(chars, 0, chars.length)

  lazy val length = eb - sb

  def charAt(i: Int): Char = {
    if (i < 0 || i >= length) {
      throw new IndexOutOfBoundsException
    }
    chars(i + sb)
  }

  def subSequence(s: Int, e: Int): CharSequence = {
    if (s < 0 || e < 0 || s > e || e > length) {
      throw new IndexOutOfBoundsException
    }
    new FastCharSequence(chars, sb + s, sb + e)
  }

  override def toString(): String = new String(chars, sb, length)
}

また、ファイル全体を読み込んでパーサに渡すのでなく、一定サイズをバッファに読み込み、順次パースしていき、失敗するとバッファを増やしてトライする…というような処理を行う場合、このFastCharSequenceをなるべく低コストで連結できるとうれしいので、その場合は以下のように対応できます。

JointCharSequence.scala

class JointCharSequence(a: CharSequence, b: CharSequence) extends CharSequence {
  lazy val length = a.length + b.length

  def charAt(i: Int) = {
    if (i < 0 || i >= length) {
      throw new IndexOutOfBoundsException
    }
    if (i < a.length) {
      a.charAt(i)
    } else {
      b.charAt(i-a.length)
    }
  }

  def subSequence(s: Int, e: Int) = {
    if (s < 0 || e < 0 || s > e || e > length) {
      throw new IndexOutOfBoundsException
    }
    if (s < a.length) {
      if (e <= a.length) {
        a.subSequence(s, e)
      } else {
        val _e = e-a.length
        val _a = if (s == 0) a else a.subSequence(s, a.length)
        val _b = if (_e == b.length) b else b.subSequence(0, _e)
        new JointCharSequence(_a, _b)
      }
    } else {
      b.subSequence(s-a.length, e-a.length)
    }
  }

  override def toString(): String = a.toString + b.toString
}

上記の修正を適用して、なんとか実用的な速度でCSVパーサが動くようになりました

Reader2WithParser1

しかしOrangeSignal CSV比ではわずか10%の速度。

OrangeSignal CSV

はやい！