regex_game_of_life is slow on TruffleRuby

[gogainda]

Project: https://github.com/dmagliola/regex_game_of_life In short it's implementation of Game of Life using RegExp

regex_gol_v2.rb: Final version described on my talk, using named captures to do the replacement also using Regex. The new interesting code is in method add_neighbour_capture

Noticed that v2 is considerably slower on TruffleRuby comparing to other implementations. Not something is useful in real world, but may be used as an artificial benchmark.

[eregon]

Could you share the numbers you see, and also on CRuby? Is the v2 supposed to be faster or rather just fancier?

[gogainda]

I dont have any numbers, since it's not printing FPS. It just runs much slower that v1. On CRuby both variants are running smoothly

[ahorek]

board = "000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000010100000000000000000000000000000000000000000000000000000000011000000110000000000001100000000000000000000000000000000000000000000010001000011000000000000110000000000000000000000000000000000110000000010000010001100000000000000000000000000000000000000000000000011000000001000101100001010000000000000000000000000000000000000000000000000000000100000100000001000000000000000000000000000000000000000000000000000000001000100000000000000000000000000000000000000000000000000000000000000000011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
regex = /(?-mix:(?<=000(?:.{67})0)0(?=0(?:.{67})(?<replace>1)11)|(?<=000(?:.{67})0)0(?=(?<replace>1)(?:.{67})011)|(?<=000(?:.{67})0)0(?=(?<replace>1)(?:.{67})101)|(?<=000(?:.{67})0)0(?=(?<replace>1)(?:.{67})110)|(?<=(?<replace>0)00(?:.{67})0)1(?=0(?:.{67})000)|(?<=(?<replace>0)00(?:.{67})0)1(?=0(?:.{67})001)|(?<=(?<replace>0)00(?:.{67})0)1(?=0(?:.{67})010)|(?<=(?<replace>0)00(?:.{67})0)1(?=0(?:.{67})100)|(?<=(?<replace>0)00(?:.{67})0)1(?=1(?:.{67})000)|(?<=(?<replace>0)00(?:.{67})0)1(?=1(?:.{67})111)|(?<=000(?:.{67})(?<replace>1))0(?=0(?:.{67})011)|(?<=000(?:.{67})(?<replace>1))0(?=0(?:.{67})101)|(?<=000(?:.{67})(?<replace>1))0(?=0(?:.{67})110)|(?<=000(?:.{67})(?<replace>1))0(?=1(?:.{67})001)|(?<=000(?:.{67})(?<replace>1))0(?=1(?:.{67})010)|(?<=000(?:.{67})(?<replace>1))0(?=1(?:.{67})100)|(?<=(?<replace>0)00(?:.{67})1)1(?=0(?:.{67})000)|(?<=(?<replace>0)00(?:.{67})1)1(?=0(?:.{67})111)|(?<=(?<replace>0)00(?:.{67})1)1(?=1(?:.{67})011)|(?<=(?<replace>0)00(?:.{67})1)1(?=1(?:.{67})101)|(?<=(?<replace>0)00(?:.{67})1)1(?=1(?:.{67})110)|(?<=(?<replace>0)00(?:.{67})1)1(?=1(?:.{67})111)|(?<=00(?<replace>1)(?:.{67})0)0(?=0(?:.{67})011)|(?<=00(?<replace>1)(?:.{67})0)0(?=0(?:.{67})101)|(?<=00(?<replace>1)(?:.{67})0)0(?=0(?:.{67})110)|(?<=00(?<replace>1)(?:.{67})0)0(?=1(?:.{67})001)|(?<=00(?<replace>1)(?:.{67})0)0(?=1(?:.{67})010)|(?<=00(?<replace>1)(?:.{67})0)0(?=1(?:.{67})100)|(?<=(?<replace>0)01(?:.{67})0)1(?=0(?:.{67})000)|(?<=(?<replace>0)01(?:.{67})0)1(?=0(?:.{67})111)|(?<=(?<replace>0)01(?:.{67})0)1(?=1(?:.{67})011)|(?<=(?<replace>0)01(?:.{67})0)1(?=1(?:.{67})101)|(?<=(?<replace>0)01(?:.{67})0)1(?=1(?:.{67})110)|(?<=(?<replace>0)01(?:.{67})0)1(?=1(?:.{67})111)|(?<=00(?<replace>1)(?:.{67})1)0(?=0(?:.{67})001)|(?<=00(?<replace>1)(?:.{67})1)0(?=0(?:.{67})010)|(?<=00(?<replace>1)(?:.{67})1)0(?=0(?:.{67})100)|(?<=00(?<replace>1)(?:.{67})1)0(?=1(?:.{67})000)|(?<=(?<replace>0)01(?:.{67})1)1(?=0(?:.{67})011)|(?<=(?<replace>0)01(?:.{67})1)1(?=0(?:.{67})101)|(?<=(?<replace>0)01(?:.{67})1)1(?=0(?:.{67})110)|(?<=(?<replace>0)01(?:.{67})1)1(?=0(?:.{67})111)|(?<=(?<replace>0)01(?:.{67})1)1(?=1(?:.{67})001)|(?<=(?<replace>0)01(?:.{67})1)1(?=1(?:.{67})010)|(?<=(?<replace>0)01(?:.{67})1)1(?=1(?:.{67})011)|(?<=(?<replace>0)01(?:.{67})1)1(?=1(?:.{67})100)|(?<=(?<replace>0)01(?:.{67})1)1(?=1(?:.{67})101)|(?<=(?<replace>0)01(?:.{67})1)1(?=1(?:.{67})110)|(?<=(?<replace>0)01(?:.{67})1)1(?=1(?:.{67})111)|(?<=0(?<replace>1)0(?:.{67})0)0(?=0(?:.{67})011)|(?<=0(?<replace>1)0(?:.{67})0)0(?=0(?:.{67})101)|(?<=0(?<replace>1)0(?:.{67})0)0(?=0(?:.{67})110)|(?<=0(?<replace>1)0(?:.{67})0)0(?=1(?:.{67})001)|(?<=0(?<replace>1)0(?:.{67})0)0(?=1(?:.{67})010)|(?<=0(?<replace>1)0(?:.{67})0)0(?=1(?:.{67})100)|(?<=(?<replace>0)10(?:.{67})0)1(?=0(?:.{67})000)|(?<=(?<replace>0)10(?:.{67})0)1(?=0(?:.{67})111)|(?<=(?<replace>0)10(?:.{67})0)1(?=1(?:.{67})011)|(?<=(?<replace>0)10(?:.{67})0)1(?=1(?:.{67})101)|(?<=(?<replace>0)10(?:.{67})0)1(?=1(?:.{67})110)|(?<=(?<replace>0)10(?:.{67})0)1(?=1(?:.{67})111)|(?<=0(?<replace>1)0(?:.{67})1)0(?=0(?:.{67})001)|(?<=0(?<replace>1)0(?:.{67})1)0(?=0(?:.{67})010)|(?<=0(?<replace>1)0(?:.{67})1)0(?=0(?:.{67})100)|(?<=0(?<replace>1)0(?:.{67})1)0(?=1(?:.{67})000)|(?<=(?<replace>0)10(?:.{67})1)1(?=0(?:.{67})011)|(?<=(?<replace>0)10(?:.{67})1)1(?=0(?:.{67})101)|(?<=(?<replace>0)10(?:.{67})1)1(?=0(?:.{67})110)|(?<=(?<replace>0)10(?:.{67})1)1(?=0(?:.{67})111)|(?<=(?<replace>0)10(?:.{67})1)1(?=1(?:.{67})001)|(?<=(?<replace>0)10(?:.{67})1)1(?=1(?:.{67})010)|(?<=(?<replace>0)10(?:.{67})1)1(?=1(?:.{67})011)|(?<=(?<replace>0)10(?:.{67})1)1(?=1(?:.{67})100)|(?<=(?<replace>0)10(?:.{67})1)1(?=1(?:.{67})101)|(?<=(?<replace>0)10(?:.{67})1)1(?=1(?:.{67})110)|(?<=(?<replace>0)10(?:.{67})1)1(?=1(?:.{67})111)|(?<=0(?<replace>1)1(?:.{67})0)0(?=0(?:.{67})001)|(?<=0(?<replace>1)1(?:.{67})0)0(?=0(?:.{67})010)|(?<=0(?<replace>1)1(?:.{67})0)0(?=0(?:.{67})100)|(?<=0(?<replace>1)1(?:.{67})0)0(?=1(?:.{67})000)|(?<=(?<replace>0)11(?:.{67})0)1(?=0(?:.{67})011)|(?<=(?<replace>0)11(?:.{67})0)1(?=0(?:.{67})101)|(?<=(?<replace>0)11(?:.{67})0)1(?=0(?:.{67})110)|(?<=(?<replace>0)11(?:.{67})0)1(?=0(?:.{67})111)|(?<=(?<replace>0)11(?:.{67})0)1(?=1(?:.{67})001)|(?<=(?<replace>0)11(?:.{67})0)1(?=1(?:.{67})010)|(?<=(?<replace>0)11(?:.{67})0)1(?=1(?:.{67})011)|(?<=(?<replace>0)11(?:.{67})0)1(?=1(?:.{67})100)|(?<=(?<replace>0)11(?:.{67})0)1(?=1(?:.{67})101)|(?<=(?<replace>0)11(?:.{67})0)1(?=1(?:.{67})110)|(?<=(?<replace>0)11(?:.{67})0)1(?=1(?:.{67})111)|(?<=0(?<replace>1)1(?:.{67})1)0(?=0(?:.{67})000)|(?<=(?<replace>0)11(?:.{67})1)1(?=0(?:.{67})001)|(?<=(?<replace>0)11(?:.{67})1)1(?=0(?:.{67})010)|(?<=(?<replace>0)11(?:.{67})1)1(?=0(?:.{67})011)|(?<=(?<replace>0)11(?:.{67})1)1(?=0(?:.{67})100)|(?<=(?<replace>0)11(?:.{67})1)1(?=0(?:.{67})101)|(?<=(?<replace>0)11(?:.{67})1)1(?=0(?:.{67})110)|(?<=(?<replace>0)11(?:.{67})1)1(?=0(?:.{67})111)|(?<=(?<replace>0)11(?:.{67})1)1(?=1(?:.{67})000)|(?<=(?<replace>0)11(?:.{67})1)1(?=1(?:.{67})001)|(?<=(?<replace>0)11(?:.{67})1)1(?=1(?:.{67})010)|(?<=(?<replace>0)11(?:.{67})1)1(?=1(?:.{67})011)|(?<=(?<replace>0)11(?:.{67})1)1(?=1(?:.{67})100)|(?<=(?<replace>0)11(?:.{67})1)1(?=1(?:.{67})101)|(?<=(?<replace>0)11(?:.{67})1)1(?=1(?:.{67})110)|(?<=(?<replace>0)11(?:.{67})1)1(?=1(?:.{67})111)|(?<=(?<replace>1)00(?:.{67})0)0(?=0(?:.{67})011)|(?<=(?<replace>1)00(?:.{67})0)0(?=0(?:.{67})101)|(?<=(?<replace>1)00(?:.{67})0)0(?=0(?:.{67})110)|(?<=(?<replace>1)00(?:.{67})0)0(?=1(?:.{67})001)|(?<=(?<replace>1)00(?:.{67})0)0(?=1(?:.{67})010)|(?<=(?<replace>1)00(?:.{67})0)0(?=1(?:.{67})100)|(?<=1(?<replace>0)0(?:.{67})0)1(?=0(?:.{67})000)|(?<=1(?<replace>0)0(?:.{67})0)1(?=0(?:.{67})111)|(?<=1(?<replace>0)0(?:.{67})0)1(?=1(?:.{67})011)|(?<=1(?<replace>0)0(?:.{67})0)1(?=1(?:.{67})101)|(?<=1(?<replace>0)0(?:.{67})0)1(?=1(?:.{67})110)|(?<=1(?<replace>0)0(?:.{67})0)1(?=1(?:.{67})111)|(?<=(?<replace>1)00(?:.{67})1)0(?=0(?:.{67})001)|(?<=(?<replace>1)00(?:.{67})1)0(?=0(?:.{67})010)|(?<=(?<replace>1)00(?:.{67})1)0(?=0(?:.{67})100)|(?<=(?<replace>1)00(?:.{67})1)0(?=1(?:.{67})000)|(?<=1(?<replace>0)0(?:.{67})1)1(?=0(?:.{67})011)|(?<=1(?<replace>0)0(?:.{67})1)1(?=0(?:.{67})101)|(?<=1(?<replace>0)0(?:.{67})1)1(?=0(?:.{67})110)|(?<=1(?<replace>0)0(?:.{67})1)1(?=0(?:.{67})111)|(?<=1(?<replace>0)0(?:.{67})1)1(?=1(?:.{67})001)|(?<=1(?<replace>0)0(?:.{67})1)1(?=1(?:.{67})010)|(?<=1(?<replace>0)0(?:.{67})1)1(?=1(?:.{67})011)|(?<=1(?<replace>0)0(?:.{67})1)1(?=1(?:.{67})100)|(?<=1(?<replace>0)0(?:.{67})1)1(?=1(?:.{67})101)|(?<=1(?<replace>0)0(?:.{67})1)1(?=1(?:.{67})110)|(?<=1(?<replace>0)0(?:.{67})1)1(?=1(?:.{67})111)|(?<=(?<replace>1)01(?:.{67})0)0(?=0(?:.{67})001)|(?<=(?<replace>1)01(?:.{67})0)0(?=0(?:.{67})010)|(?<=(?<replace>1)01(?:.{67})0)0(?=0(?:.{67})100)|(?<=(?<replace>1)01(?:.{67})0)0(?=1(?:.{67})000)|(?<=1(?<replace>0)1(?:.{67})0)1(?=0(?:.{67})011)|(?<=1(?<replace>0)1(?:.{67})0)1(?=0(?:.{67})101)|(?<=1(?<replace>0)1(?:.{67})0)1(?=0(?:.{67})110)|(?<=1(?<replace>0)1(?:.{67})0)1(?=0(?:.{67})111)|(?<=1(?<replace>0)1(?:.{67})0)1(?=1(?:.{67})001)|(?<=1(?<replace>0)1(?:.{67})0)1(?=1(?:.{67})010)|(?<=1(?<replace>0)1(?:.{67})0)1(?=1(?:.{67})011)|(?<=1(?<replace>0)1(?:.{67})0)1(?=1(?:.{67})100)|(?<=1(?<replace>0)1(?:.{67})0)1(?=1(?:.{67})101)|(?<=1(?<replace>0)1(?:.{67})0)1(?=1(?:.{67})110)|(?<=1(?<replace>0)1(?:.{67})0)1(?=1(?:.{67})111)|(?<=(?<replace>1)01(?:.{67})1)0(?=0(?:.{67})000)|(?<=1(?<replace>0)1(?:.{67})1)1(?=0(?:.{67})001)|(?<=1(?<replace>0)1(?:.{67})1)1(?=0(?:.{67})010)|(?<=1(?<replace>0)1(?:.{67})1)1(?=0(?:.{67})011)|(?<=1(?<replace>0)1(?:.{67})1)1(?=0(?:.{67})100)|(?<=1(?<replace>0)1(?:.{67})1)1(?=0(?:.{67})101)|(?<=1(?<replace>0)1(?:.{67})1)1(?=0(?:.{67})110)|(?<=1(?<replace>0)1(?:.{67})1)1(?=0(?:.{67})111)|(?<=1(?<replace>0)1(?:.{67})1)1(?=1(?:.{67})000)|(?<=1(?<replace>0)1(?:.{67})1)1(?=1(?:.{67})001)|(?<=1(?<replace>0)1(?:.{67})1)1(?=1(?:.{67})010)|(?<=1(?<replace>0)1(?:.{67})1)1(?=1(?:.{67})011)|(?<=1(?<replace>0)1(?:.{67})1)1(?=1(?:.{67})100)|(?<=1(?<replace>0)1(?:.{67})1)1(?=1(?:.{67})101)|(?<=1(?<replace>0)1(?:.{67})1)1(?=1(?:.{67})110)|(?<=1(?<replace>0)1(?:.{67})1)1(?=1(?:.{67})111)|(?<=(?<replace>1)10(?:.{67})0)0(?=0(?:.{67})001)|(?<=(?<replace>1)10(?:.{67})0)0(?=0(?:.{67})010)|(?<=(?<replace>1)10(?:.{67})0)0(?=0(?:.{67})100)|(?<=(?<replace>1)10(?:.{67})0)0(?=1(?:.{67})000)|(?<=11(?<replace>0)(?:.{67})0)1(?=0(?:.{67})011)|(?<=11(?<replace>0)(?:.{67})0)1(?=0(?:.{67})101)|(?<=11(?<replace>0)(?:.{67})0)1(?=0(?:.{67})110)|(?<=11(?<replace>0)(?:.{67})0)1(?=0(?:.{67})111)|(?<=11(?<replace>0)(?:.{67})0)1(?=1(?:.{67})001)|(?<=11(?<replace>0)(?:.{67})0)1(?=1(?:.{67})010)|(?<=11(?<replace>0)(?:.{67})0)1(?=1(?:.{67})011)|(?<=11(?<replace>0)(?:.{67})0)1(?=1(?:.{67})100)|(?<=11(?<replace>0)(?:.{67})0)1(?=1(?:.{67})101)|(?<=11(?<replace>0)(?:.{67})0)1(?=1(?:.{67})110)|(?<=11(?<replace>0)(?:.{67})0)1(?=1(?:.{67})111)|(?<=(?<replace>1)10(?:.{67})1)0(?=0(?:.{67})000)|(?<=11(?<replace>0)(?:.{67})1)1(?=0(?:.{67})001)|(?<=11(?<replace>0)(?:.{67})1)1(?=0(?:.{67})010)|(?<=11(?<replace>0)(?:.{67})1)1(?=0(?:.{67})011)|(?<=11(?<replace>0)(?:.{67})1)1(?=0(?:.{67})100)|(?<=11(?<replace>0)(?:.{67})1)1(?=0(?:.{67})101)|(?<=11(?<replace>0)(?:.{67})1)1(?=0(?:.{67})110)|(?<=11(?<replace>0)(?:.{67})1)1(?=0(?:.{67})111)|(?<=11(?<replace>0)(?:.{67})1)1(?=1(?:.{67})000)|(?<=11(?<replace>0)(?:.{67})1)1(?=1(?:.{67})001)|(?<=11(?<replace>0)(?:.{67})1)1(?=1(?:.{67})010)|(?<=11(?<replace>0)(?:.{67})1)1(?=1(?:.{67})011)|(?<=11(?<replace>0)(?:.{67})1)1(?=1(?:.{67})100)|(?<=11(?<replace>0)(?:.{67})1)1(?=1(?:.{67})101)|(?<=11(?<replace>0)(?:.{67})1)1(?=1(?:.{67})110)|(?<=11(?<replace>0)(?:.{67})1)1(?=1(?:.{67})111)|(?<=(?<replace>1)11(?:.{67})0)0(?=0(?:.{67})000)|(?<=111(?:.{67})(?<replace>0))1(?=0(?:.{67})001)|(?<=111(?:.{67})(?<replace>0))1(?=0(?:.{67})010)|(?<=111(?:.{67})(?<replace>0))1(?=0(?:.{67})011)|(?<=111(?:.{67})(?<replace>0))1(?=0(?:.{67})100)|(?<=111(?:.{67})(?<replace>0))1(?=0(?:.{67})101)|(?<=111(?:.{67})(?<replace>0))1(?=0(?:.{67})110)|(?<=111(?:.{67})(?<replace>0))1(?=0(?:.{67})111)|(?<=111(?:.{67})(?<replace>0))1(?=1(?:.{67})000)|(?<=111(?:.{67})(?<replace>0))1(?=1(?:.{67})001)|(?<=111(?:.{67})(?<replace>0))1(?=1(?:.{67})010)|(?<=111(?:.{67})(?<replace>0))1(?=1(?:.{67})011)|(?<=111(?:.{67})(?<replace>0))1(?=1(?:.{67})100)|(?<=111(?:.{67})(?<replace>0))1(?=1(?:.{67})101)|(?<=111(?:.{67})(?<replace>0))1(?=1(?:.{67})110)|(?<=111(?:.{67})(?<replace>0))1(?=1(?:.{67})111)|(?<=111(?:.{67})1)1(?=(?<replace>0)(?:.{67})000)|(?<=111(?:.{67})1)1(?=(?<replace>0)(?:.{67})001)|(?<=111(?:.{67})1)1(?=(?<replace>0)(?:.{67})010)|(?<=111(?:.{67})1)1(?=(?<replace>0)(?:.{67})011)|(?<=111(?:.{67})1)1(?=(?<replace>0)(?:.{67})100)|(?<=111(?:.{67})1)1(?=(?<replace>0)(?:.{67})101)|(?<=111(?:.{67})1)1(?=(?<replace>0)(?:.{67})110)|(?<=111(?:.{67})1)1(?=(?<replace>0)(?:.{67})111)|(?<=111(?:.{67})1)1(?=1(?:.{67})(?<replace>0)00)|(?<=111(?:.{67})1)1(?=1(?:.{67})(?<replace>0)01)|(?<=111(?:.{67})1)1(?=1(?:.{67})(?<replace>0)10)|(?<=111(?:.{67})1)1(?=1(?:.{67})(?<replace>0)11)|(?<=111(?:.{67})1)1(?=1(?:.{67})1(?<replace>0)0)|(?<=111(?:.{67})1)1(?=1(?:.{67})1(?<replace>0)1)|(?<=111(?:.{67})1)1(?=1(?:.{67})11(?<replace>0))|(?<=111(?:.{67})1)1(?=1(?:.{67})111))/

require 'benchmark/ips'
Benchmark.ips do |x|
  x.warmup = 10
  x.report("regex") { board.gsub(regex, '\k<replace>') }
end

indeed, truffleruby is significantly slower here compared to other implementations

 0.084 (truffleruby 22.3.0)
 8.381 (ruby 3.2 head)
11.678 (jruby 9.3.7.0)

[eregon]

Thanks for the benchmark, that's a lot more convenient.

The issue is shown clearly with --engine.TraceCompilation:

[engine] opt failed id=1716  tregex bt ASCII: /(?-mix:(?<=000(?:.{67})0)0(?=... |Tier 1|Time  272(-19684047+19684319)ms|Reason: org.graalvm.compiler.truffle.compiler.GraphTooBigBailoutException: Graph too big to safely compile. Node count: 90260. Graph Size: 150026. Limit: 150000.|Timestamp 19684319056080|Src n/a
[engine] opt failed id=1716  tregex bt ASCII: /(?-mix:(?<=000(?:.{67})0)0(?=... |Tier 1|Time  366(-19684319+19684685)ms|Reason: org.graalvm.compiler.truffle.compiler.GraphTooBigBailoutException: Graph too big to safely compile. Node count: 90260. Graph Size: 150026. Limit: 150000.|Timestamp 19684685259735|Src n/a

The regexp is simply too big (11k characters-long!), and so it's not reasonable to compile it. Therefore it's run in interpreter and that's pretty slow. @djoooooe What do you think? Could TRegex detect this maybe?

It's possible to run on Joni using:

ruby --experimental-options --use-truffle-regex=false bench_regexp_game_of_life.rb

and that gives me:

TruffleRuby TRegex too big to compile
               regex      0.128  (± 0.0%) i/s -      1.000  in   7.810786s
TruffleRuby Joni
               regex     14.144  (± 0.0%) i/s -     71.000  in   5.024343s
CRuby 3.0.3
               regex     10.265  (± 0.0%) i/s -     52.000  in   5.067043s