Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

accepts() vs choices() in InteractiveParser #1418

Closed
Daniel63656 opened this issue May 21, 2024 · 10 comments
Closed

accepts() vs choices() in InteractiveParser #1418

Daniel63656 opened this issue May 21, 2024 · 10 comments
Labels

Comments

@Daniel63656
Copy link

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
Copy link
Member

MegaIng commented May 21, 2024

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
Copy link
Author

Daniel63656 commented May 21, 2024

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
Copy link
Member

MegaIng commented May 21, 2024

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
Copy link
Author

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
Copy link
Member

erezsh commented May 21, 2024

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
Copy link
Author

Daniel63656 commented May 21, 2024

@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
Copy link
Member

erezsh commented May 21, 2024

Sorry, my message was to @MegaIng .

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

@erezsh
Copy link
Member

erezsh commented May 26, 2024

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

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

#1419

@Daniel63656
Copy link
Author

Daniel63656 commented May 27, 2024

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
Copy link
Member

erezsh commented Jun 22, 2024

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

@erezsh erezsh closed this as completed Jun 22, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

3 participants