accepts() vs choices() in InteractiveParser

[Daniel63656]

I am using the InteractiveParser to feed tokens one at a time. I noticed this to be comparatively slow. After profiling it, I saw that a lot of copying is done. After checking the class, I noticed that accepts() (which I use in each step to query next allowed terminals) loops over all terminals returned from choices(), copies the parser state and then checks if feeding the terminal causes an UnexpectedToken exception. Why is this even necessary? The docs of choices() say: "only returns token types that are accepted by the current state" so why doing the very expensive copying of the entire parser state to verify this? Can I just use choices() and filter out the terminals?

[MegaIng]

choices() returns the terminals that have a transition in the state machine from the current state. But following that transition might lead to errors further down the line, see #646

Whether choices() is enough for you depends on what you are trying to do.

[Daniel63656]

I am trying to get all terminal at the step that conform to the grammar. According to the issue, I would need to use accepts() then I guess but the copying overhead is way too much. I use this in a transformer at each prediction and using this approach doubles the inference time, meaning the parsing takes as much time as running the model (!). Maybe there is another solution to verify the tokens?

[MegaIng]

I don't think there is a fundamentally different approach that avoids copying the parser state.

But it might be possible to avoid deep-copying the value_stack, which I suspect is the majority of the cost of copying, since everything else should be quite cheap to copy.

[Daniel63656]

Is there no way to "peek" and check if a token would be accepted without advancing the state (thus making copying of any kind obsolete)?

[erezsh]

I agree that the deepcopy is the most likely candidate / suspect. I think the deepcopy is there because the callbacks (i.e. inline transformer) might change the objects they are given. But actually in this use-case we don't care about the values. We can even tell the parser not to compute anything in the value_stack, which will cause it to run faster, and avoid the risk of side-effects from the callbacks.

Another optimization for this particular scenario: If the action is a SHIFT (which is quite probable), unwinding the stack only requires a pop, and no copy is needed.

[Daniel63656]

@erezsh yes I can confirm that. Replacing accepts() with choices() reduced the percentage of compute time in my method taken by lark from 50% to almost 0% in my case. But of course this also defeats the purpose if it also returns invalid Tokens.

[erezsh]

Sorry, my message was to @MegaIng .

Anyway, I think we can make accepts() pretty fast if we do those things.

[erezsh]

@Daniel63656 I created a PR that might solve your performance problems.

Can you give it a try and let me know if it helped?

https://github.com/lark-parser/lark/pull/1419

[Daniel63656]

yes, this helps a lot. The calls to accepts() now only takes about 2,6% of time in my case instead of the 50% it used to be.

[erezsh]

There could be more optimizations done, but sounds like it's good enough right now, so I'm closing the issue.