Accessing position information in a scala combinatorparser kills performance

Question

I wrote a new combinator for my parser in scala.

Its a variation of the ^^ combinator, which passes position information on. But accessing the position information of the input element really cost performance.

In my case parsing a big example need around 3 seconds without position information, with it needs over 30 seconds.

I wrote a runnable example where the runtime is about 50% more when accessing the position.

Why is that? How can I get a better runtime?

Example:

import scala.util.parsing.combinator.RegexParsers
import scala.util.parsing.combinator.Parsers
import scala.util.matching.Regex
import scala.language.implicitConversions
object FooParser extends RegexParsers with Parsers {
  var withPosInfo = false
  def b: Parser[String] = regexB("""[a-z]+""".r)  ^^@ { case (b, x) => b + " ::" + x.toString }
  def regexB(p: Regex): BParser[String] = new BParser(regex(p))
  class BParser[T](p: Parser[T]) {
    def ^^@[U](f: ((Int, Int), T) => U): Parser[U] = Parser { in =>
      val source = in.source
      val offset = in.offset
      val start = handleWhiteSpace(source, offset)
      val inwo = in.drop(start - offset)
      p(inwo) match {
        case Success(t, in1) =>
          {
            var a = 3
            var b = 4
            if(withPosInfo)
            { // takes a lot of time
              a = inwo.pos.line
              b = inwo.pos.column
            }            
            Success(f((a, b), t), in1)
          }
        case ns: NoSuccess => ns
      }
    }
  }
  def main(args: Array[String]) = {
    val r = "foo"*50000000
    var now = System.nanoTime

    parseAll(b, r) 
    var us = (System.nanoTime - now) / 1000
    println("without: %d us".format(us))
    withPosInfo = true
    now = System.nanoTime
    parseAll(b, r)
    us = (System.nanoTime - now) / 1000
    println("with   : %d us".format(us))
  }
}

Output:

without: 2952496 us

with : 4591070 us

Answer 1

Unfortunately, I don't think you can use the same approach. The problem is that line numbers end up implemented by scala.util.parsing.input.OffsetPosition which builds a list of every line break every time it is created. So if it ends up with string input it will parse the entire thing on every call to pos (twice in your example). See the code for CharSequenceReader and OffsetPosition for more details.

There is one quick thing you can do to speed this up:

val ip = inwo.pos
a = ip.line
b = ip.column

to at least avoid creating pos twice. But that still leaves you with a lot of redundant work. I'm afraid to really solve the problem you'll have to build the index as in OffsetPosition yourself, just once, and then keep referring to it.

You could also file a bug report / make an enhancement request. This is not a very good way to implement the feature.