How to fix an exponential slowness due to backtracking?

[winitzki]

I'm struggling to fix an exponential slowness in fastparse 3.0.2 (Scala 2.13) used for an expression grammar. There is too much backtracking going on, and I have been adding cuts but the exponential slowness remains.

I tried to add memoization to the parsers but this failed with strange error messages about unboxing Unit into Integer.

A small working example of a grammar that shows exponential slowness:

    import fastparse.NoWhitespace._
    import fastparse._
    // Integer calculator program: 1+2*3-(4-5)*6 and so on. No spaces, for simplicity.
    def program[$: P]: P[Int] = P(expr ~ End)
    def expr[$: P]: P[Int]    = P(x_minus | x_plus)
    def x_minus[$: P]         = P(x_times ~ "-" ~ expr)
        .map { case (x, y) => x - y }
    def x_plus[$: P]          = P(x_times ~ ("+" ~ expr).rep)
        .map { case (i, is) => i + is.sum }
    def x_times[$: P]         = P(x_other ~ ("*" ~ x_other).rep)
        .map { case (i, is) => i * is.product }
    def x_other[$: P]         = P(number | ("(" ~ expr ~ ")"))
    def number[$: P]          = P(CharIn("0-9").rep(1))
        .!.map(_.toInt)
    // Verify that this works as expected.
    assert(parse("123*(1+1)", program(_)).get.value == 246)
    assert(parse("123*1+1", program(_)).get.value == 124)
    assert(parse("123*1-1", program(_)).get.value == 122)
    assert(parse("123*(1-1)", program(_)).get.value == 0)

    // Parse an expression of the form `(((((...(1)...)))))`.
     val n = 25
     assert(parse("(" * (n - 1) + "1" + ")" * (n - 1), program(_)).get.value == 1)

The code works but parsing takes about 10 seconds. I found that parsing this expression with n parentheses takes about $2^{n-20}$ seconds. The reason for the exponential slowness is the backtracking. It tries to parse expr after ( and there are two possibilities (minus and plus). Each possibility will need to be fully explored before returning to parse the next (. To explore means again to parse expr recursively. So, there is a 2x increase of parsing work for each parenthesis. To visualize the slowness, consider this function:

def fibonacci(n: Int): Int = if (n <= 1) 1 else fibonacci(n-1) + fibonacci(n-2)

It takes $2^n$ function calls to compute fibonacci(n) by this program.

I tried adding cuts to the grammar at various places but the exponential slowness remains.

So, I have two questions:

1. Can we somehow mitigate this problem by adding cuts, or adding more grammar rules, or in some other way?

2. Memoization could help here: if a parser rule already failed at a certain location, it is not necessary to try again to parse with the same parser rule at the same location. If a parser rule succeeded at a certain location, and a parse is unique, it is not necessary to parse again at the same location. This may eliminate the exponential slowness if implemented correctly. Is there a way to implement that?

[winitzki]

I tried memoization like this:

    val cache_minus = mutable.Map[Int, P[Int]]()
    val cache_plus  = mutable.Map[Int, P[Int]]()

    def x_minus[$](implicit p: P[$]): P[Int] = cache_minus.getOrElseUpdate(p.index, P(x_times ~ "-" ~ expr).map { case (x, y) => x - y })
    def x_plus[$](implicit p: P[$]): P[Int]  = cache_plus.getOrElseUpdate(p.index, P(x_times ~ ("+" ~ expr).rep).map { case (i, is) => i + is.sum })
   // Other grammar rules remain unchanged.

This fails whenever the input contains parentheses:

parse("123*(1+1)", program(_))
// 
java.lang.ClassCastException: class scala.runtime.BoxedUnit cannot be cast to class java.lang.Integer (scala.runtime.BoxedUnit is in unnamed module of loader 'app'; java.lang.Integer is in module java.base of loader 'bootstrap')

	at scala.runtime.BoxesRunTime.unboxToInt(BoxesRunTime.java:99)

But I was unable to find the code that does this unboxing to Int. Probably, this code is generated by a macro. In any case, I don't know how to fix this problem.

[lihaoyi]

The basic problem appears to be here

      def expr[$: P]: P[Int]    = P(x_minus | x_plus)
      def x_minus[$: P]         = P(x_times ~ "-" ~ expr).map { case (x, y) => x - y }
      def x_plus[$: P]          = P(x_times ~ ("+" ~ expr).rep).map { case (i, is) => i + is.sum }

You are making expr parse x_times twice: once as part of x_minus, and once as part of x_plus. This causes exponential backtracking without cuts, and causes the parse to spuriously fail if cuts are introduced

You probably want something like this

      def expr[$: P]: P[Int]    =  P(x_times ~ (("+" | "-").! ~ expr).rep).map { 
        case (i, is) => i + is.map{case ("+", n) => n case ("-", n) => -n}.sum 
      }

Once done, it is no longer exponential. You can also now add cuts to enforce this and improve the error reporting:

@ time{    import fastparse.NoWhitespace._
        import fastparse._
        // Integer calculator program: 1+2*3-(4-5)*6 and so on. No spaces, for simplicity.
        def program[$: P]: P[Int] = P(expr ~ End)
        def expr[$: P]: P[Int]    =  P(x_times ~ (("+" | "-").! ~/ expr).rep).map { 
          case (i, is) => i + is.map{case ("+", n) => n case ("-", n) => -n}.sum 
        }
        def x_times[$: P]         = P(x_other ~ ("*" ~/ x_other).rep).map { case (i, is) => i * is.product }
        def x_other[$: P]         = P(number | ("(" ~/ expr ~ ")"))
        def number[$: P]          = P(CharIn("0-9").rep(1)).!.map(_.toInt)
        // Verify that this works as expected.
        assert(parse("123*(1+1)", program(_)).get.value == 246)
        assert(parse("123*1+1", program(_)).get.value == 124)
        assert(parse("123*1-1", program(_)).get.value == 122)
        assert(parse("123*(1-1)", program(_)).get.value == 0)
    
        // Parse an expression of the form `(((((...(1)...)))))`.
         //val n = 25
         assert(parse("(" * (n - 1) + "1" + ")" * (n - 1), program(_)).get.value == 1)
    }  
res30: (Unit, concurrent.duration.FiniteDuration) = ((), 1929708 nanoseconds)

[winitzki]

@lihaoyi Thank you. I will see if I can modify the grammar to get rid of the exponential slowness.

The other question remains: why did I fail to memoize the parsing results? Memoization appears to be useful in certain cases (at least, when some parsers do not depend on previously parsed results). I just added code, as shown in my comment above, to store ParsingRun values in a mutable dictionary. Mysteriously, I got a class cast exception (where I don't even see the code where a class cast is performed). Is there any way of adding memoization to fastparse?

[lihaoyi]

Memoizing might be possible but it's not something that's built in to the framework.

Part of the confusion is that the P[_] that is passed throughout the parsing run is the same P[_]. Sometimes it's a P[Unit], sometimes it's a P[Int], sometimes it's a P[String], etc.. As the parsing proceeds, the various parsers store their return values on the same P[_] object, to avoid the performance overhead of allocation many objects over and over.

That means the P[_] cannot be stored and re-used later.

What you can do, on the other hand, is to read off the various variables off the P[_]/ParsingRun[_] object, store their values, and stick them back onto the P[_] object later. There's a big list of variables here

fastparse/fastparse/src/fastparse/ParsingRun.scala

Lines 105 to 123 in 49ba3cf

	final class ParsingRun[+T](val input: ParserInput,
	val startIndex: Int,
	val originalParser: ParsingRun[_] => ParsingRun[_],
	val traceIndex: Int,
	val instrument: Instrument,
	// Mutable vars below:
	var terminalMsgs: Msgs,
	var aggregateMsgs: Msgs,
	var shortMsg: Msgs,
	var lastFailureMsg: Msgs,
	var failureStack: List[(String, Int)],
	var isSuccess: Boolean,
	var logDepth: Int,
	var index: Int,
	var cut: Boolean,
	var successValue: Any,
	var verboseFailures: Boolean,
	var noDropBuffer: Boolean,
	val misc: collection.mutable.Map[Any, Any]){

of all the mutable state in a parsing run, and I suppose you would need to save/restore all of them

This isn't something that's supported by the framework by default, but I can imagine it might work. Try it out and see how it goes!

[winitzki]

Thank you for the explanation. After some trial and error, I came up with some memoization code that seems to work.

As you said, the problem with the toy grammar in this example is that times is called twice. And times depends only on other. So, I can memoize just one parser (other) and get rid of the exponential slowness.

//... other rules of the grammar as above. The changes are only for `x_times` and `x_other`:
    def x_times[$: P]: P[R]                       = P(x_other_cached ~ ("*" ~ x_other_cached).rep).map { case (i, is) => i * is.product }
    def x_other[$: P]: P[R]                       = P(number | ("(" ~ expr ~ ")"))
    def x_other_cached[$](implicit p: P[$]): P[R] = cachedParser(cache_other, x_other)

To make this work, I used the following setup:

    final case class PRunData( // Copy all the mutable data from ParsingRun.
      terminalMsgs: Msgs,
      aggregateMsgs: Msgs,
      shortMsg: Msgs,
      lastFailureMsg: Msgs,
      failureStack: List[(String, Int)],
      isSuccess: Boolean,
      logDepth: Int,
      index: Int,
      cut: Boolean,
      successValue: Any,
      verboseFailures: Boolean,
      noDropBuffer: Boolean,
      misc: collection.mutable.Map[Any, Any],
    ) {
      override def toString: String                   = {
        s"ParsingRun(index=$index, isSuccess = $isSuccess, successValue = $successValue)"
      }
      def assignToParsingRun[T](pr: ParsingRun[T]): ParsingRun[T] = { // Assign the mutable data to a given ParsingRun value.
        pr.terminalMsgs = terminalMsgs
        pr.aggregateMsgs = aggregateMsgs
        pr.shortMsg = shortMsg
        pr.lastFailureMsg = lastFailureMsg
        pr.failureStack = failureStack
        pr.isSuccess = isSuccess
        pr.logDepth = logDepth
        pr.index = index
        pr.cut = cut
        pr.successValue = successValue
        pr.verboseFailures = verboseFailures
        pr.noDropBuffer = noDropBuffer
        misc.foreach { case (k, v) => pr.misc.put(k, v) }
        pr
    }

    object PRunData { // Copy all the mutable data from a parsing run into a PRunData value.
      def ofParsingRun[T](pr: ParsingRun[T]): PRunData = PRunData(
        pr.terminalMsgs,
        pr.aggregateMsgs,
        pr.shortMsg,
        pr.lastFailureMsg,
        pr.failureStack,
        pr.isSuccess,
        pr.logDepth,
        pr.index,
        pr.cut,
        pr.successValue,
        pr.verboseFailures,
        pr.noDropBuffer,
        mutable.Map.from(pr.misc),
      )
    }

def cacheGrammar[R](cache: mutable.Map[Int, PRunData], parser: => P[_])(implicit p: P[_]): P[R] = {
      // The `parser` has not yet been run! And it is mutable. Do not run it twice!
      val cachedData: PRunData = cache.getOrElseUpdate(p.index, PRunData.ofParsingRun(parser))
      // After the `parser` has been run on `p`, the value of `p` changes and becomes equal to the result of running the parser.
      // If the result was cached, we need to assign it to the current value of `p`. This will imitate the side effect of running the parser again.
      cachedData.assignToParsingRun(p).asInstanceOf[P[R]]
}

// Need a separate cache for every memoized parser.
val cache_other = mutable.Map[Int, PRunData]()

// Need to do cache_other.clear() between different calls to parse an expression.
val n = 500
cache_other.clear()
assert(parse("(" * (n - 1) + "1" + ")" * (n - 1), program(_)).get.value == 1)
cache_other.clear()
assert(parse("1+" + "(1+" * (n - 1) + "1" + ")" * (n - 1), program(_)).get.value == n + 1)

[lihaoyi]

Glad to see it working! Memoizing in Fastparse is a cool trick that I've known for a while "should" work, but I've never actually tried it haha.

However, is there a reason you want to go the memoization approach, rather than refactoring your grammar? The refactored grammar that I proposed has benefits other than performance, e.g. I would expect error reporting to be much more precise. you can try adding mis-matched parens and seeing the effect.

[winitzki]

I'm working with a bigger grammar with several different kinds of braces and several different types of expressions. The grammar is specified in ABNF and I would rather not have to rewrite the grammar. https://github.com/dhall-lang/dhall-lang/blob/master/standard/dhall.abnf
My project (early experimental stage) is here https://github.com/winitzki/scall

If memoizing works, it could be as easy as def parser1[$:P] = P(...).memoize(params) just like the logging is added.

I had another question: How do I activate the parsing error hints? "Expected blah but got blahblah". Are the hints activated only when cuts are present?

[winitzki]

I implemented fastparse-memoize as a tiny library, based on the code shown in this discussion. https://central.sonatype.com/search?q=fastparse-memoize
Adding .memoize to parsers in certain places breaks parsing but, if used carefully, speeds up parsing 10x-100x in some cases.

The speedup is especially big after JVM warm-up. I have a performance test where I am parsing a realistic example file, - this was not a specially crafted test with hundreds of unneeded parentheses. Without memoizing, the parsing took 6 seconds even when repeated many times (so, JVM warmup does not improve performance). After memoizing several parsing rules, the parsing took 0.5 seconds, that is, I got a 12x speedup. Then I repeated this parse 2000 times, and the speedup grew to about 700x due to JVM warmup. (Best parsing time was 0.0075 seconds.)