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](https://github.com/scala/scala-parser-combinators)は別jarになってますのでサクッとbuild.sbtを書き換えて修正できるようです。

# [RegexParsers](http://www.scala-lang.org/api/2.10.4/index.html#scala.util.parsing.combinator.RegexParsers)でCSVパーサを書いていました
テストコードはパスして、実際にある程度のサイズのファイルを食べさせてみると、すごく遅い。まあそんなものなのかなぁと一晩放置すると

```
java.lang.OutOfMemoryError: Java heap space
```

となりました。

## VisualVMでプロファイルしたものが以下です
Reader1WithParser1
![parser1](https://qiita-image-store.s3.amazonaws.com/0/47014/8825a2db-3570-8c9f-8237-ef7edba3acc5.png)

![4361ec54766bc80fc470de34a5b4296c.png](https://qiita-image-store.s3.amazonaws.com/0/47014/dbe88083-9eb4-ebec-2522-263b59458037.png)

![b8d2b349f5ccd23888a88ea367043bf0
.png](https://qiita-image-store.s3.amazonaws.com/0/47014/5a72f2a9-d8ac-5514-e469-3988b5b2b245.png)

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

## 調べてみると[該当するIssueが見つかり](https://issues.scala-lang.org/browse/SI-7710)ました
どうやらJavaのStringに関する仕様変更をまともに食らったらしく、メモリパフォーマンスがO(入力長)！！になってしまった模様。[修正パッチはマージされています](https://github.com/scala/scala-parser-combinators/pull/17)が、単純に[RegexParsers.scala has O(inputlength) memory performance on java >= 7u6](https://issues.scala-lang.org/browse/SI-7710)に書かれている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
![1d2d8655dec622eb581dd06e2ce4e4d4.png](https://qiita-image-store.s3.amazonaws.com/0/47014/292cc776-fc19-2011-e13e-94e9d92c1db4.png)


しかし[OrangeSignal CSV](https://github.com/orangesignal/orangesignal-csv)比ではわずか10%の速度。



OrangeSignal CSV
![d84cd129dae7b361b440ac09920ff83b.png](https://qiita-image-store.s3.amazonaws.com/0/47014/6257b676-d584-9e9d-f3e9-49e6b1002760.png)
はやい！