3 ms·

You will probably find https://github.com/BurntSushi/aho-corasick/blob/master/DESIGN.md https://github.com/BurntSushi/aho-corasick/blob/master/DESIG... good rea

You will probably find https://github.com/BurntSushi/aho-corasick/blob/master/DESIGN.md https://github.com/BurntSushi/aho-corasick/blob/master/DESIG... good reading. I believe captures get in the way of using the fastest of these NFA-style techniques, though. There's a comment from burntsushi to this effect in: https://lobste.rs/s/fq8uil/aho_corasick https://lobste.rs/s/fq8uil/aho_corasick ETA: Heh, I'm amused to find the latter link to be another point in what seems to be an extended conversation between Andy Chu and the Rust text-processing community :)

chubot 6y ago
Ha yes, as far as I remember, my claim about Aho-Corasick had validity, but I definitely learned a bunch of things from that thread. If you scroll way down you will see a benchmark I did for the "constant string" problem. So you can see that re2c does scale better from 1000-6000 fixed strings than either RE2 or rust/regex. But I uncovered a whole bunch of other problems, like re2c segfaulting, the output being slow to compile, egrep blowing up, the non-regular heuristics of "grep" playing a role, etc. https://github.com/oilshell/blog-code/blob/master/fgrep-problem-benchmarks/fixed-strings.sh#L328 https://github.com/oilshell/blog-code/blob/master/fgrep-prob... # grep is faster than both fgrep and the "optimal" DFA in native code # (generated by re2c). I think grep is benefitting from SKIPPING bytes. # All times are 'user' time, which is most of the 'real' time. # re2c compile | re2c code size | re2c match time | ripgrep time | RE2 # n= 100 7 ms 11 KiB 1,566 ms 687 ms 1,398 ms # n=1000 66 ms 57 KiB 2,311 ms 1,803 ms 1,874 ms # n=2000 120 ms 93 KiB 2,499 ms 3,591 ms 2,681 ms # n=3000 204 ms 125 KiB 2,574 ms 5,801 ms 3,471 ms # n=4000 266 ms 159 KiB 2,563 ms 8,083 ms 4,323 ms # n=5000 363 ms 186 KiB 2,638 ms 10,431 ms 5,294 ms # n=6000 366 ms 213 KiB 2,659 ms 13,182 ms 6,397 ms # n=47,000 2,814 ms # # NOTES: # - egrep blows up around 400 strings! # - RE2 says "DFA out of memory" at 2000 strings, because it exhausts its 8 MB # budget. We simply bump it up. # - at 48,000 words, re2c segfaults! # - At 10,000 words, GCC takes 36 seconds to compile re2c's output! It's 74K # lines in 1.2 MB of source. I meant to blog about this but never got around to it ... As mentioned, I think you would uncover similarly interesting things by benchmarking Sublime-like workloads with re2c's capture algorithm. They use some fundamentally different automata-based implementation techniques.

chubot 6y ago

Ha yes, as far as I remember, my claim about Aho-Corasick had validity, but I definitely learned a bunch of things from that thread. If you scroll way down you will see a benchmark I did for the "constant string" problem. So you can see that re2c does scale better from 1000-6000 fixed strings than either RE2 or rust/regex. But I uncovered a whole bunch of other problems, like re2c segfaulting, the output being slow to compile, egrep blowing up, the non-regular heuristics of "grep" playing a role, etc. https://github.com/oilshell/blog-code/blob/master/fgrep-problem-benchmarks/fixed-strings.sh#L328 https://github.com/oilshell/blog-code/blob/master/fgrep-prob... # grep is faster than both fgrep and the "optimal" DFA in native code # (generated by re2c). I think grep is benefitting from SKIPPING bytes. # All times are 'user' time, which is most of the 'real' time. # re2c compile | re2c code size | re2c match time | ripgrep time | RE2 # n= 100 7 ms 11 KiB 1,566 ms 687 ms 1,398 ms # n=1000 66 ms 57 KiB 2,311 ms 1,803 ms 1,874 ms # n=2000 120 ms 93 KiB 2,499 ms 3,591 ms 2,681 ms # n=3000 204 ms 125 KiB 2,574 ms 5,801 ms 3,471 ms # n=4000 266 ms 159 KiB 2,563 ms 8,083 ms 4,323 ms # n=5000 363 ms 186 KiB 2,638 ms 10,431 ms 5,294 ms # n=6000 366 ms 213 KiB 2,659 ms 13,182 ms 6,397 ms # n=47,000 2,814 ms # # NOTES: # - egrep blows up around 400 strings! # - RE2 says "DFA out of memory" at 2000 strings, because it exhausts its 8 MB # budget. We simply bump it up. # - at 48,000 words, re2c segfaults! # - At 10,000 words, GCC takes 36 seconds to compile re2c's output! It's 74K # lines in 1.2 MB of source. I meant to blog about this but never got around to it ... As mentioned, I think you would uncover similarly interesting things by benchmarking Sublime-like workloads with re2c's capture algorithm. They use some fundamentally different automata-based implementation techniques.