Support Direct Threaded VM

[imasahiro]

Motivations:

• Onigumo implements token threaded VM but didn't implement direct threaded code yet.
• https://github.com/k-takata/Onigmo/issues/51

Changes:

• Add a pointer field to each bytecode to hold label pointer.
• Jump to next op without label table lookup

Results:

• Increase Bytecode memory usage (8 *n bytes)
• Faster pattern match (except \b\w+nn\b) at least at M1 mac (will check perf at other platform e.g. x86 later)

Here are benchmark scores. Benchmark suite is derived form http://sljit.sourceforge.net/regex_perf.html.

$ cc --version
Apple clang version 12.0.5 (clang-1205.0.22.11)
Target: arm64-apple-darwin20.6.0
Thread model: posix
InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin

Pattern	Current	Proposal
Twain	15 ms	15 ms
(?i)Twain	60 ms	18 ms
[a-z]shing	14 ms	13 ms
Huck[a-zA-Z]+|Saw[a-zA-Z]+	20 ms	16 ms
\b\w+nn\b	394 ms	414 ms
[a-q][^u-z]{13}x	20 ms	7 ms
Tom|Sawyer|Huckleberry|Finn	25 ms	19 ms
(?i)Tom|Sawyer|Huckleberry|Finn	236 ms	179 ms
.{0,2}(Tom|Sawyer|Huckleberry|Finn)	48 ms	38 ms
.{2,4}(Tom|Sawyer|Huckleberry|Finn)	46 ms	44 ms
Tom.{10,25}river|river.{10,25}Tom	42 ms	41 ms
[a-zA-Z]+ing	509 ms	410 ms
\s[a-zA-Z]{0,12}ing\s	48 ms	44 ms
([A-Za-z]awyer|[A-Za-z]inn)\s	101 ms	99 ms
["'][^"']{0,30}[?!.]["']	44 ms	39 ms

[imasahiro]

@k-takata Hi, do you have a chance to review this?

I've applied to Ruby this patch (https://github.com/imasahiro/ruby/commit/860d60cfca690309cb1ba2811bbb1175f78dd48d) and it seems benchmark result shows not bad number (with https://benchmarksgame-team.pages.debian.net/benchmarksgame/program/regexredux-ruby-3.html (which checks regexp library performance) become 8% faster than current master branch.)

[imasahiro]

Hi~ any update so far...? @k-takata

[imasahiro]

ping @k-takata

[imasahiro]

Or is this repo already obsoleted? Then should I send a PR to https://github.com/ruby/ruby instead for example?