4 ms·

Author of syntect here: This isn't why TextMate/Sublime/VSCode/Atom style regex parsing is slow. The main reason is that the parsing model is applying a whole

Author of syntect here: This isn't why TextMate/Sublime/VSCode/Atom style regex parsing is slow. The main reason is that the parsing model is applying a whole bunch of unanchored regexes to the unparsed remainder of the line one after another until one matches, then starting again for the next token. This means each token parsed can require dozens of regex matches over the same characters. I implemented a bunch of caching schemes to cut down on this number but it still tends to need many matches per token. It sounds like Oil's lexer probably does about one regex run per token, with probably a somewhat faster regex engine, and sure enough it's something like 40x faster than syntect. Oniguruma is actually pretty fast and anyhow most of the regexes in Sublime syntax definitions are written to not require backtracking, because Sublime has two regex engines and only uses the fast one when no backtracking is required. In fact fancy-regex should delegate directly to Rust's regex crate on these regexes but is somewhat slower than Oniguruma, for reasons I haven't yet looked into (edit: see Raph's comment, it's probably heavy use of captures, another thing Oil's lexer doesn't need). Also note that byte-serial table-driven lexers have a speed limit of one byte per l1 cache round trip (~5 cycles), whereas faster lexers can take advantage of multi-byte instructions (even SIMD) and out of order execution to go much faster, hence why pulldown-cmark is 2500x faster than syntect rather than just 40. [edit: I should also clarify that since unlike these other parsers, syntect takes a grammar and can parse many languages, so how fast it is depends a lot on the grammar, I suspect the markdown grammar in particular is slower than usual, given that pulldown-cmark runs about 250MB/s and syntect on ES6 Javascript (a complicated but well-implemented grammar) is about 0.5MB/s, so the Markdown grammar may be 5 times slower]

saagarjha 6y ago
This is probably already implemented if it does exist, but I know with a bunch of fixed text strings you can create a NFA/trie thing using Aho-Corasick. Does such a thing exist for regexes (specifically: one that can match "all of them at once"), and is it used for the fast regex engine?
- raphlinus 6y ago
  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
  I replied elsewhere, but to answer more concisely: that's exactly what "regular language" / automata-based engines do, as opposed to Perl-style backtracking engines (which are more common). Here are hundreds of regexes OR'd together so the lexer reads the input exactly once, not 100 times: https://www.oilshell.org/release/0.8.pre6/source-code.wwz/_devbuild/tmp/osh-lex.re2c.h https://www.oilshell.org/release/0.8.pre6/source-code.wwz/_d... And in the lobste.rs thread linked below, I was basically saying for all practical purposes you can ignore Aho-Corasick and use the more general regex version. Since the "fgrep problem" (fixed strings) problem doesn't involve captures, you should get a DFA that runs at the same speed either way. (I don't recall if the compile time was longer but I don't think so, it is buried in the thread probably :) ) https://news.ycombinator.com/item?id=23665569 https://news.ycombinator.com/item?id=23665569
chubot 6y ago
The main reason is that the parsing model is applying a whole bunch of unanchored regexes to the unparsed remainder of the line one after another until one matches, then starting again for the next token. This means each token parsed can require dozens of regex matches over the same characters. Hm but why can't you just OR them together? That is perfectly fine with a regular language engine. For example, I OR together about 50 different regexes here (including a whole bunch of constant strings) for the ShCommand mode: https://www.oilshell.org/release/0.8.pre6/source-code.wwz/_devbuild/tmp/osh-lex.re2c.h https://www.oilshell.org/release/0.8.pre6/source-code.wwz/_d... Despite this big mess, everything "just works", i.e. the lexer reads every byte of input just once. re2c picks the alternative with longest match, and it picks the first match to break ties. ----- I suspect the reason that you can't do this is (1) Sublime was originally implemented with a Perl-style regex engine and (2) the order of | clauses matters more when using a backtracking engine. It doesn't have the simple rule that an automata-based engine has. My claim is that you avoid performance problems by using a "regular language" engine. So I think what you point out supports this, even it might be a slightly different issue than "more backtracking". I think you are saying that Sublime's parsing model prevents composition by |, which makes lexing slow, because it forces you to read each byte many times. (in addition to the captures issue, let me think about that)
- trishume 6y ago
  Two reasons: captures, and it needs to know which of the regexes matched. I meant to but forgot to mention in my original comment that the reason Sublime's built-in highlighter is the fastest is they wrote a custom regex engine which basically does the equivalent of or-ing them together but unlike all other regex engines handles captures and information about which one matched properly while doing so. The custom engine doesn't do backtracking and it falls back to Oniguruma for regexes that use fancy features. So yah it's in theory possible you just need to write a custom regex engine to do it.
  - fanf2 6y ago
    re2c supports captures and it will tell you which regex matched. http://re2c.org/manual/manual.html#submatch-extraction http://re2c.org/manual/manual.html#submatch-extraction

saagarjha 6y ago

This is probably already implemented if it does exist, but I know with a bunch of fixed text strings you can create a NFA/trie thing using Aho-Corasick. Does such a thing exist for regexes (specifically: one that can match "all of them at once"), and is it used for the fast regex engine?

raphlinus 6y ago
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
I replied elsewhere, but to answer more concisely: that's exactly what "regular language" / automata-based engines do, as opposed to Perl-style backtracking engines (which are more common). Here are hundreds of regexes OR'd together so the lexer reads the input exactly once, not 100 times: https://www.oilshell.org/release/0.8.pre6/source-code.wwz/_devbuild/tmp/osh-lex.re2c.h https://www.oilshell.org/release/0.8.pre6/source-code.wwz/_d... And in the lobste.rs thread linked below, I was basically saying for all practical purposes you can ignore Aho-Corasick and use the more general regex version. Since the "fgrep problem" (fixed strings) problem doesn't involve captures, you should get a DFA that runs at the same speed either way. (I don't recall if the compile time was longer but I don't think so, it is buried in the thread probably :) ) https://news.ycombinator.com/item?id=23665569 https://news.ycombinator.com/item?id=23665569

chubot 6y ago

The main reason is that the parsing model is applying a whole bunch of unanchored regexes to the unparsed remainder of the line one after another until one matches, then starting again for the next token. This means each token parsed can require dozens of regex matches over the same characters. Hm but why can't you just OR them together? That is perfectly fine with a regular language engine. For example, I OR together about 50 different regexes here (including a whole bunch of constant strings) for the ShCommand mode: https://www.oilshell.org/release/0.8.pre6/source-code.wwz/_devbuild/tmp/osh-lex.re2c.h https://www.oilshell.org/release/0.8.pre6/source-code.wwz/_d... Despite this big mess, everything "just works", i.e. the lexer reads every byte of input just once. re2c picks the alternative with longest match, and it picks the first match to break ties. ----- I suspect the reason that you can't do this is (1) Sublime was originally implemented with a Perl-style regex engine and (2) the order of | clauses matters more when using a backtracking engine. It doesn't have the simple rule that an automata-based engine has. My claim is that you avoid performance problems by using a "regular language" engine. So I think what you point out supports this, even it might be a slightly different issue than "more backtracking". I think you are saying that Sublime's parsing model prevents composition by |, which makes lexing slow, because it forces you to read each byte many times. (in addition to the captures issue, let me think about that)

trishume 6y ago
Two reasons: captures, and it needs to know which of the regexes matched. I meant to but forgot to mention in my original comment that the reason Sublime's built-in highlighter is the fastest is they wrote a custom regex engine which basically does the equivalent of or-ing them together but unlike all other regex engines handles captures and information about which one matched properly while doing so. The custom engine doesn't do backtracking and it falls back to Oniguruma for regexes that use fancy features. So yah it's in theory possible you just need to write a custom regex engine to do it.
- fanf2 6y ago
  re2c supports captures and it will tell you which regex matched. http://re2c.org/manual/manual.html#submatch-extraction http://re2c.org/manual/manual.html#submatch-extraction