Parser::Lexer#advance method is too big for JIT compilers

I have been investigating why parser is so slow on TruffleRuby.
I had a suspicion it's a too big generated method and indeed that's now clearly the case from this analysis: https://github.com/oracle/truffleruby/issues/2290#issuecomment-1277796067
This has been found before, and notably I found https://github.com/whitequark/parser/issues/524 from a quick search and https://github.com/whitequark/parser/pull/248#issuecomment-173187259, https://github.com/whitequark/parser/pull/248#issuecomment-173626397.

To summarize, the Parser::Lexer#advance method is currently 13525 lines long which is humongous.
I would think most if not all Ruby JITs cannot compile such a big method (or if they do they will compile it in a very suboptimal manner).
And so that method needs to be run in the interpreter, and that's typically slower the more advanced the JIT is due to more profiling and other reasons.
Hence parser is slow on anything but CRuby, on MJIT it hangs, on YJIT it's a bit faster like 11% (YJIT seems to compile a few blocks of advance, not all). I used ruby -Ilib -rparser/current -rbenchmark -e 'code=File.read("test/test_lexer.rb"); 10.times { p Benchmark.realtime { Parser::CurrentRuby.parse(code) } }'.
So on TruffleRuby we can see it tried to compile it, saw it was way too big and bailed out, and then executed the advance method all the time in interpreter.

It's easy to reproduce, for example in the parser repo:

$ truffleruby --engine.TraceCompilation -Ilib -rparser/current -e 'loop { Parser::CurrentRuby.parse(File.read("test/helper.rb")) }' |& grep 'Lexer#advance'      
[engine] opt failed id=6106  Lexer#advance                                      |Tier 1|Time  778(-24199569+24200347)ms|Reason: org.graalvm.compiler.truffle.compiler.GraphTooBigBailoutException: Graph too big to safely compile. Node count: 113880. Graph Size: 150001. Limit: 150000.|Timestamp 24200346847485|Src lexer.rb:11303
[engine] opt failed id=6106  Lexer#advance                                      |Tier 1|Time  635(-24200352+24200987)ms|Reason: org.graalvm.compiler.truffle.compiler.GraphTooBigBailoutException: Graph too big to safely compile. Node count: 113879. Graph Size: 150001. Limit: 150000.|Timestamp 24200987352654|Src lexer.rb:11303

(The Graph Size: 150001 just means it aborted after reaching the limit)

Interesting it does compile when lexing very small and simple files

$ truffleruby --engine.TraceCompilation -Ilib -rparser/current -e 'loop { Parser::CurrentRuby.parse(File.read("test/test_static_environment.rb")) }' |& grep 'Lexer#advance'
[engine] opt done   id=6106  Lexer#advance                                      |Tier 1|Time  3984(1366+2618)ms|AST 26200|Inlined   0Y  66N|IR   9583/ 42570|CodeSize  224281|Addr 0x7f472e900000|Timestamp 24166598032966|Src lexer.rb:11303

So maybe it's not so much above the limit of what TruffleRuby/Graal can compile.

Of course, the lexer.rb file is generated by ragel from lexer.rl.
One idea would be to use different ragel flags to produce smaller method(s).
I tried all options from the --help with ragel 6.10 to see if we can make the method smaller, here are my notes:

ragel --version
Ragel State Machine Compiler version 6.10 March 2017
Copyright (c) 2001-2009 by Adrian Thurston

lexer.rl:
2618 lines

F1: (currently used)
25014 lines
advance: 11302-24827 = 13525 lines
with -L: 11298-23926 = 12628 lines
works

F0:
18145 lines
advance: 11486-17958 = 6472 lines
with -L: 11482-17576 = 6094 lines
fails with undefined local variable or method `_lex_actions' for #<Parser...> (NameError) on CRuby

T0:
10482 lines
advance: 3786-10295 = 6509 lines
with -L: 3782- 9913 = 6131 lines
fails with undefined method `_lex_key_spans' for Parser::Lexer:Class (NoMethodError) on CRuby

T1:
17356 lines
advance: 3602-17169 = 13567 lines
with -L: 3598-16268 = 12670 lines
fails with undefined method `_lex_key_spans' for Parser::Lexer:Class (NoMethodError) on CRuby

G0 --rbx:
43465 lines
advance: 820-43278 = 42458 lines
with -L: 816-42900 = 42084 lines

G1, G2, P: Invalid code style

So the smallest is F0 (and T0), but that's still 6094 lines which still sounds a lot for a single method.
But maybe it helps enough for JITs.

Some points:

1. For some reason only F1 works, F0/T0/T1 fail as noted above.
   Does anyone know why? Maybe that's a bug of Ragel? EDIT: I've found https://github.com/whitequark/parser/pull/248#issuecomment-173191333

2. There is a BlockNode in Truffle which enables automatically splitting huge methods in smaller ones, this is not yet supported on TruffleRuby but would be worth a try. I think it depends on the structure of the code for whether this is able to split Parser::Lexer#advance in smaller chunks (e.g., it wouldn't work with a huge case/when spanning most of the method, which looks like it is the case here :/). And it will be compiled less optimally than if it was reasonably-sized methods in the first place.

3. Have there been other experiments in this area to reduce the size of Parser::Lexer#advance?

4. Extracting larger semantic actions into methods/lambdas would definitely help. (https://github.com/whitequark/parser/pull/248#issuecomment-173631772)

5. Maybe generating C or Java code would be a better for this kind of stuff (although Java also has a size limit to compile, and C compilers can have pretty bad register allocation with huge functions)?

6. I guess one possibility is of course to wait for the new Ruby parser by @kddnewton, as that will have the lexer and parser written in C (and probably not generated with ragel so much more reasonable function sizes). And possibly we could use it for this gem for recent Ruby versions.

Start with lexer.rl and the generated lexer.rb around Parser::Lexer#advance, then reproduce the TruffleRuby compilation bailout using the benchmark command and test files mentioned in the issue. Done would mean reducing the generated method or splitting its work while preserving the existing parser behavior and avoiding the reported JIT size failure.