One-more-re-nightmare – A fast regex compiler in Common Lisp

Perhaps most importantly, a good CL implementation can help with debugging this, by keeping track of the original CL code that generated the intermediate code, and pointing you to it. With the "use a program to generate C" approach, if there's some bug in the C code, the best the compiler or runtime can do is point you to the line of C code that's crashing. It's up to you to figure out where that came from.

This was a problem for early C++ compilers like Cfront that translated C++ into C: the error messages from the C compiler referenced the intermediate C, not the original C++.

I noticed this too and was hoping the author would mention it in his article but couldn't find a reference to it :) This is a great album to listen to while doing technical work.

I'm pretty sure I submitted it properly. Strange. Dang, could you fix it?

re2 has limited functionality. It’s works wel for specific patterns, like crawling, but not general purpose

If the benchmarks are to be believed, I think it substantially outperforms re2, because it also beats Hyperscan, and I think Hyperscan typically beats re2.

Author here - I don't think this is an issue.

If you don't use submatching, you can just compute the minimal DFAs and compare them to test for equivalence, and you don't even need negation. Thus, introducing negation can't do any harm there.

But as I generate Mealy machines for submatching, which can't be minimised, we need another approach. Knowing that A - B = A ∧ ¬B, one can produce a DFA for (A - B) ∨ (B - A), and if it has no accepting states, then A and B must be equivalent, as nothing can match one but not both. But DFA construction is O(2ⁿ), even if one takes the RE → NFA → DFA route, so this is nothing new complexity-wise.

Such a decision procedure is never used in a derivative-based regex implementation, anyway. The equivalence of regular expressions only needs to be approximated, and the approximation consists of some structural rules (see Definition 4.1 of [1]). Relatively few rules are needed to guarantee that a _finite_ machine can be generated, and only a dozen rules are required to get very close to a minimal DFA (table 1, page 14 of [1]). So having the possibility of writing a precise regex equivalence function is completely irrelevant to producing an efficient regex engine.

A decision procedure is handy, but you can write one for submatch-less regexes without negation, the complexity of such a procedure is typical for DFA construction, and the problem of deciding if two regular expressions are equivalent is irrelevant.

[1] Regular-expression derivatives reexamined https://www.ccs.neu.edu/home/turon/re-deriv.pdf

The complement operation doesn't provide a way of deciding whether two regexes are equivalent, nor is any such thing required to implement it. Using derivatives to interpret a regular expression that contains a complement operator does not require a function for calculating equivalence of two regular expressions.

Equivalence is required for compiling. The reason is that regular expressions have features like the Kleene closure which express iteration, and these give rise to endless derivatives: regular expressions whose derivative you can keep taking ad nauseum. This is fine for interpreting, because the algorithm terminates when you have consumed the input or hit an impasse. The compiler, however, has to close the loops and turn them into cycles in the state machine graph. To do that it has to check each derivative: "have I derived an expression which has occurred before?" If so, then just hook to the previous state.

If you make the check literal, just comparing the regex syntax for identical structure, the graph will sometimes be larger than necessary, because it will contain redundant nodes that should be equivalent states. The smarter you make the equivalence function, the more compact the graphs will be.

>Languages are rarely "slow" or "fast" by themselves.

For sure they are, language features will for sure limit the optimizations a compiler/interpreter can do and for sure a language with many levels of abstractions will have to pay the price in performance somewhere.

Every-time someone improves the benchmark performance of a slow language that person is not a regular developer, but someone that has a deeper understanding on what happens under the hood, knows how to use profiling tools, maybe knows assembly and most of the time they have to use tricks or advanced patterns.

Btw, optimizing some slow language in a hot path with clever tricks or some advanced patterns is fine, it happens all the time, you can;t just switch the project language with 1 click.

Yes and no. Some language features can make it incredibly difficult to optimise. I know the JRuby folks had all sorts of fun trying to make method dispatch fast in the face of "well, this method definition can be changed at any time, arbitrarily often, including during execution of the method itself". I know CL must also have solved that problem but I presume the toolkit is sufficiently different that the techniques just don't map.

I also feel that for 99% of applications, it doesn't matter. Like, yeah, there are a a few areas where hyper-optimized code in some kind of near-bare-metal language is necessary. But most of the time, if you're writing code, the language itself isn't gonna be the deciding factor if something is performant enough for your application. Furthermore, by using a "fast" language, you're then trading your ability to quickly and cleanly implement code that's human readable suffers greatly.