5 ms·

Tangent/clarification: the regex slowness issue is almost certainly due to using Perl-style exponential time regexes (which are required by Sublime syntax defin

by chubot 6y ago

Tangent/clarification: the regex slowness issue is almost certainly due to using Perl-style exponential time regexes (which are required by Sublime syntax definitions) rather than "regular languages". The syntect library mentioned uses fancy-regex, which is explicitly different than Rust's default regex crate, in that it supports regex constructs that require exponential backtracking: https://github.com/fancy-regex/fancy-regex https://github.com/fancy-regex/fancy-regex In particular, it uses backtracking to implement "fancy" features such as look-around and backtracking, which are not supported in purely NFA-based implementations (exemplified by RE2, and implemented in Rust in the regex crate). I think "regexes" have gotten bad name so I call them "regular languages" now. That is, RE2, rust/regex, and libc are "regular language" engines while Perl/Python/PCRE/Java/etc. are "regex" engines. In my experience, lexing with regular languages can beat hand written code. In the case of Oil vs. zsh, it's beating hand-written C code by an order of magnitude (9-10x). http://www.oilshell.org/blog/2020/01/parser-benchmarks.html http://www.oilshell.org/blog/2020/01/parser-benchmarks.html https://lobste.rs/s/77nu3d/oil_s_parser_is_160x_200x_faster_than_it_was https://lobste.rs/s/77nu3d/oil_s_parser_is_160x_200x_faster_... --- First, TextMate / Sublime style syntax highlighting is not really all that great. It is quite slow, largely because it grinds through a lot of regular expressions with captures pedantic: I think the issue is probably more lookahead than captures ? You can do captures quickly in a "regular language" engine. It may be surprising just how much slower regex-based highlighting is than fast parsers. The library that xi uses, syntect, is probably the fastest open source implementation in existence (the one in Sublime is faster but not open source). Even so, it is approximately 2500 times slower for parsing Markdown than pulldown-cmark.

an_opabinia 6y ago
The bigger problem I feel is with this: > On the plus side, there is a large and well-curated open source collection of syntax definitions Whenever I tried to get Java highlighting updated in GitHub for “var” my issue is closed minutes later by people who don’t work at GitHub telling me to open an issue with some random unpaid TextMate / Sublime repo. Really the overall problem is not owning the front end. It means you can’t do things like fix syntax highlighting, at least as important to programming as high performance word wrap.
raphlinus 6y ago
First, syntect can use both onig (an adaptation of Ruby regex, same as Sublime) and fancy-regex. The latter is yet another xi-instigated, and was motivated by trying to do a better job at this. Second, the design of fancy-regex is precisely to delegate to the regex crate when features like lookahead aren't needed. I had high hopes for the performance, but it turned out to be lackluster, a highly tuned backtracking engine beats it in most cases. And much of the problem is indeed that RE2-style approaches are a lot faster when captures aren't required. And, by nature, Sublime-style syntax definitions rely extremely heavily on captures. A bit of discussion (including comments from burntsushi) here: https://www.reddit.com/r/rust/comments/5zit0e/regex_captures_slow_compared_to_python/ https://www.reddit.com/r/rust/comments/5zit0e/regex_captures... Third, the question of whether "regular languages" would support faster parsing is somewhat academic, though perhaps you could build something. Though the languages being parsed often have some regular features, as a rule there are exceptions. Markdown is an extreme example, and cannot be parsed well with either regular languages or Perl-style regexes, though that hasn't stopped people from trying.
- chubot 6y ago
  OK thanks for the clarifications. I responded to BurntSushi and others here: https://lobste.rs/s/fq8uil/aho_corasick https://lobste.rs/s/fq8uil/aho_corasick https://news.ycombinator.com/item?id=23665341 https://news.ycombinator.com/item?id=23665341 I don't have experience with captures in re2c, but it's entirely automata-based, and they apparently implement something "fast" for captures and published it in this 2017 paper, so it's pretty new: https://arxiv.org/abs/1907.08837 https://arxiv.org/abs/1907.08837 I'm sort of interested in benchmarking some Sublime-ish workloads with it, but I'm not sure I'll have time. ---- And the other claim from that comment is that while regular languages aren't powerful enough by themselves for syntax highlighting, you can add a trivial state machine on top of them (perhaps Vim-like), and get something more powerful and faster than Sublime's model. I'd have to look at the captures vs. lookahead issue more closely, but the general claim is that I think Sublime has a bad parsing model based on a sloppy application of Perl-style regexes (e.g. if you are really forced to read every byte multiple times, that seems dumb, and can be avoided with regular languages)
trishume 6y ago
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 :)

by chubot 6y ago

an_opabinia 6y ago

The bigger problem I feel is with this: > On the plus side, there is a large and well-curated open source collection of syntax definitions Whenever I tried to get Java highlighting updated in GitHub for “var” my issue is closed minutes later by people who don’t work at GitHub telling me to open an issue with some random unpaid TextMate / Sublime repo. Really the overall problem is not owning the front end. It means you can’t do things like fix syntax highlighting, at least as important to programming as high performance word wrap.

raphlinus 6y ago

First, syntect can use both onig (an adaptation of Ruby regex, same as Sublime) and fancy-regex. The latter is yet another xi-instigated, and was motivated by trying to do a better job at this. Second, the design of fancy-regex is precisely to delegate to the regex crate when features like lookahead aren't needed. I had high hopes for the performance, but it turned out to be lackluster, a highly tuned backtracking engine beats it in most cases. And much of the problem is indeed that RE2-style approaches are a lot faster when captures aren't required. And, by nature, Sublime-style syntax definitions rely extremely heavily on captures. A bit of discussion (including comments from burntsushi) here: https://www.reddit.com/r/rust/comments/5zit0e/regex_captures_slow_compared_to_python/ https://www.reddit.com/r/rust/comments/5zit0e/regex_captures... Third, the question of whether "regular languages" would support faster parsing is somewhat academic, though perhaps you could build something. Though the languages being parsed often have some regular features, as a rule there are exceptions. Markdown is an extreme example, and cannot be parsed well with either regular languages or Perl-style regexes, though that hasn't stopped people from trying.

chubot 6y ago
OK thanks for the clarifications. I responded to BurntSushi and others here: https://lobste.rs/s/fq8uil/aho_corasick https://lobste.rs/s/fq8uil/aho_corasick https://news.ycombinator.com/item?id=23665341 https://news.ycombinator.com/item?id=23665341 I don't have experience with captures in re2c, but it's entirely automata-based, and they apparently implement something "fast" for captures and published it in this 2017 paper, so it's pretty new: https://arxiv.org/abs/1907.08837 https://arxiv.org/abs/1907.08837 I'm sort of interested in benchmarking some Sublime-ish workloads with it, but I'm not sure I'll have time. ---- And the other claim from that comment is that while regular languages aren't powerful enough by themselves for syntax highlighting, you can add a trivial state machine on top of them (perhaps Vim-like), and get something more powerful and faster than Sublime's model. I'd have to look at the captures vs. lookahead issue more closely, but the general claim is that I think Sublime has a bad parsing model based on a sloppy application of Perl-style regexes (e.g. if you are really forced to read every byte multiple times, that seems dumb, and can be avoided with regular languages)

trishume 6y ago

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 :)