Xi-Editor Retrospective

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

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/_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

> it might be able to safely save the file, but you can also do that by frequently checkpointing

It is always amazing to discover niches where the conceptual and practical power of logging has not yet penetrated.

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.

On the github page https://github.com/xi-editor/xi-editor:

  JSON. The protocol for front-end / back-end communication, as well as between the back-end 
  and plug-ins, is based on simple JSON messages. I considered binary formats, but the actual 
  improvement in performance would be completely in the noise. Using JSON considerably lowers 
  friction for developing plug-ins, as it’s available out of the box for most modern languages,
  and there are plenty of the libraries available for the other ones.

4 years later:

  The choice of JSON was controversial from the start. It did end up being a source of friction, but for surprising reasons.

  For one, JSON in Swift is shockingly slow.

Surprising reasons?!