Xi-Editor Retrospective

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...

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.

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]