performance - 在 Scala 组合器解析器中访问位置信息会降低性能

Question

我在 Scala 中为我的解析器编写了一个新的组合器。
它是 ^^ 组合器的变体，它传递位置信息。
但是访问输入元素的位置信息真的很划算。
在我的情况下，解析一个大的例子需要大约 3 秒没有位置信息，它需要超过 30 秒。
我写了一个可运行的示例，其中访问位置时的运行时间增加了大约 50%。
这是为什么？我怎样才能获得更好的运行时间？
例子:

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))
  }
}

输出:

without: 2952496 us

with : 4591070 us

Answer 1

不幸的是，我认为您不能使用相同的方法。问题是行号最终由 scala.util.parsing.input.OffsetPosition 实现每次创建时都会构建每个换行符的列表。因此，如果它以字符串输入结束，它将在每次调用 pos 时解析整个内容。 (在你的例子中两次)。查看 CharSequenceReader 的代码和 OffsetPosition更多细节。

您可以快速做一件事来加快速度:

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

至少避免创建 pos两次。但这仍然会给您留下很多多余的工作。恐怕要真正解决您必须像OffsetPosition 中那样构建索引的问题你自己，就一次，然后继续引用它。

您还可以提交错误报告/提出增强请求。这不是实现该功能的好方法。