Thank you@Nikita-str for putting the time and effort into writing this up. I support moving to a trampoline style parsing with a loop and state machine. The recursive descent parsing doesn’t suit rust so much (no tail call optimisation) and causes multiple issues.

I understand that statically it’s not as easy to find sub parse nodes, but I hope we can improve debugging but having a debug_log which prints which parser is currently running when a flag is passed (we don’t have this today).

Do you know if this can be worked on incrementally? Or do you plan to just keep updating this? Maybe maintainers can help if they have access, we could have a check list at the top and keep rebasing as we go along (the parser doesn’t beg touched as much these days so I don’t think it will conflict that often).

im interested to hear from the other maintainers.

this can be worked on incrementally?

I think, incrementally is not an option, because if any node A call sub-parse-node B outside ofParseLoop then the Loop cannot handle any subsequent calls from node B (or otherwise the Loop will return handling on wrong position), and therefore it's parsed in the old way (this is why bothparse andparse_loop are now preserved for rewritten nodes). So such changes should be done for all nodes to make sense.

maintainers can help if they have access

That would be good, actually. We can do it in parallel. It's a very easily separable task, and with a few extra hands this can be done in 1-2 days.

I feel like this may be over engineering something that should have a very simple solution.

Seeing the original issue, the parser works fine on release mode, so there must be some set of optimizations that the compiler is doing to reduce the amount of recursion. My suggestion would be that we should try to look at the assembly of a release build, then carefully try to force the compiler to apply the same optimizations in debug mode.

My suggestion would be that we should try to look at the assembly of a release build, then carefully try to force the compiler to apply the same optimizations in debug mode.

@jedel1043
The problem here, is that in debug mode (withopt-level = 0) the stack structures take too many memory and it use up the stack too quickly. Also withopt-level = 0 there is no auto function splitting (to make less stack allocation) & no auto passing through some functions (in code A call B then B call C, then withopt-level = 1 (or more) it can be transformed into A call C directly).

To temporarily solve it you even need really splitting the functions (after making some structure size less -- what seems good to me; only structures' size reduction is not enough).

For more details seethis PR: first part of commits is seems ok to me, and second part is ugly (because you need splitting the function to solve the problem withopt-level = 0).

But maybe, in current PR you need to do something like the splitting (you need to continue execution fromcontinue_point)... but at least it would not be a temporary solution, but a long-term one.

The problem here, is that in debug mode (with opt-level = 0) the stack structures take too many memory and it use up the stack too quickly. Also with opt-level = 0 there is no auto function splitting (to make less stack allocation) & no auto passing through some functions (in code A call B then B call C, then with opt-level = 1 (or more) it can be transformed into A call C directly).

If the problem is the size of ast nodes, I think we should just stop having ast nodes in the stack, and use something likeoxc_allocator to have an arena of all ast nodes. This way we don't need to deal with trampolining functions, and it also gives the nice bonus of making the drop of ast trees really cheap.

The problem here, is that in debug mode (with opt-level = 0) the stack structures take too many memory and it use up the stack too quickly. Also with opt-level = 0 there is no auto function splitting (to make less stack allocation) & no auto passing through some functions (in code A call B then B call C, then with opt-level = 1 (or more) it can be transformed into A call C directly).

If the problem is the size of ast nodes, I think we should just stop having ast nodes in the stack, and use something likeoxc_allocator to have an arena of all ast nodes. This way we don't need to deal with trampolining functions, and it also gives the nice bonus of making the drop of ast trees really cheap.

I don’t think having heap allocated nodes would help with performance of the parser as we need to visit them a lot so it would create a new problem with back and forth trips to the heap (this would need to be benchmarked).

The idea of specialized allocation for nodes on the AST also seems odd if we drop the whole tree anyway once we’ve moved onto the VM stage, unless I’m misunderstanding something.

Seeing the original issue, the parser works fine on release mode, so there must be some set of optimizations that the compiler is doing to reduce the amount of recursion

I’m guessing the compiler is aggressively inlining during release mode so we don’t end up with deep stacks. So if we wanted to recreate this in debug mode we would need to addinline(always) in a lot of places across the parser. I can’t say I’m sure if that’s a proper fix for this problem.

I’d be open to seeing how a loop & state machine fairs in performance to what we have today.

I don’t think having heap allocated nodes would help with performance of the parser as we need to visit them a lot so it would create a new problem with back and forth trips to the heap (this would need to be benchmarked).

It's not for performance though. The problem that we have right now is that our AST nodes use too much space in the stack, which gives little room for function calls. Moving every AST node to the heap makes it such that more recursive calls can be made. We would obviously still need to rewrite the parser to be smarter about recursive operators ([[[[[]]]]] and such, maybe it can be done with a pratt parser), but it should be a smaller change than having to convert everything to trampolines.

I don’t think having heap allocated nodes would help with performance of the parser as we need to visit them a lot so it would create a new problem with back and forth trips to the heap (this would need to be benchmarked).

It's not for performance though. The problem that we have right now is that our AST nodes use too much space in the stack, which gives little room for function calls. Moving every AST node to the heap makes it such that more recursive calls can be made. We would obviously still need to rewrite the parser to be smarter about recursive operators ([[[[[]]]]] and such, maybe it can be done with a pratt parser), but it should be a smaller change than having to convert everything to trampolines.

Oh yeah I know the original issue isn’t about performance. I was saying that to move nodes to the heap could end up harming parser performance despite fixing this specific issue. The trade off wouldn’t be worth it.

instead, as you say we would be best finding ways to make the parser smarter around recursive operations. Or have a parser that wasn’t subject to these problems. The answer may be a bit of both.

Oh, yeah I know the original issue isn’t about performance. I was saying that to move nodes to the heap could end up harming parser performance despite fixing this specific issue. The trade off wouldn’t be worth it.

It could also improve performance! My thought is that right now any inner expression needs to be allocated on the heap, which distributes expressions throughout the heap, causing a lot of cache misses when you try to access related expressions. If we use bumpalo, related expressions will live near each other, making multiple accesses very cheap if the expressions fit in the same cache line.