title: Why is Scala's combinator parsing slow when parsing large files? What can I do?
body: <p>I need to parse files that have millions of lines. I noticed that my combinator parser gets slower and slower as it parses more and more lines. The problem seems to be in scala's "rep" or regex parsers, because this behaviour occurs even for the simple example parser shown below:</p>
  
  <pre><code>def file: Parser[Int] = rep(line) ^^ { 1 }  // a file is a repetition of lines
  
  def line: Parser[Int] = """(?m)^.*$""".r ^^ { 0 } // reads a line and returns 0
  </code></pre>
  
  <p>When I try to parse a file with millions of lines of equal length with this simple parser, in the beginning it parses 46 lines/ms. After 370000 lines, the speed drops to 20 lines/ms. After 840000 lines, it drops to 10 lines/ms. After 1790000 lines, 5 lines/ms...</p>
  
  <p>My questions are:</p>
  
  <ul>
  <li><p>Why does this happen?</p></li>
  <li><p>What can I do to prevent this?</p></li>
  </ul>