News for hackers. Stuff that matters.
Re:Show HN: Regular expression compilation visualized by dan-robertson on Tuesday March 23, 2021 @08:32AM (#26554246)
I wonder what the state of the art is in regex compilation? It feels to me like it shouldn’t be compilation to a program that processes one character at a time as you’ll be doing a lot of branches and so can’t process the data that fast. It feels like there ought to be a way to take advantage of ILP or SIMD operations. Maybe regex just doesn’t matter enough for that to be important.
Re:Show HN: Regular expression compilation visualized by JoelJacobson on Tuesday March 23, 2021 @09:11AM (#26554544)
Author here. The generated LLVM IR at the bottom actually make uses of vector instructions, which will make LLVM generate SIMD instructions if supported by the CPU.

For instance, try entering just a long word as the regex, e.g. "helloworld":

  %state0.goto.1.0.cmp_mask = icmp eq <10 x i8> %state0.rhs, < i8 104, i8 101, i8 108, i8 108, i8 111, i8 119, i8 111, i8 114, i8 108, i8 100 > ; helloworld
Re:Show HN: Regular expression compilation visualized by burntsushi on Tuesday March 23, 2021 @10:32AM (#26555489)
> It feels to me like it shouldn’t be compilation to a program that processes one character at a time

High performance regex engines do use SIMD in various places. Others have mentioned Hyperscan, which is undoubtedly a showcase of the most sophisticated SIMD techniques when it comes to regex and substring searching. But even something like RE2 uses vectorized code in places, although indirectly.

But, in all instances I can think of, using SIMD is a matter of identifying some optimization opportunity in regex matching that doesn't generalize to handling all cases. At some point, to handle some cases, you'll need that "one character at a time" loop. (Whether it's backtracking or FSM based.) So visualizations like these are still rather helpful, and at the very least, give a basic conceptual understanding of what the most general kind of FSM-based regex might look like internally. (Although, most general purpose regex engines don't actually utilize all of the transformations presented in the OP.)

Re:Show HN: Regular expression compilation visualized by unhammer on Tuesday March 23, 2021 @09:27AM (#26554689)
https://www.microsoft.com/en-us/research/wp-content/uploads/... is an interesting read on ILP with FSM's.

Regex is used all over the place, so it's certainly worthwhile to speed things up. And huge FST's are also used in language tech, e.g. to analyze all frillions of the forms of Finnish verbs into all their ambiguous readings with tags and dictionary forms: https://beta.apertium.org/index.eng.html?choice=fin&qA=Taite... The language supported by that FST is basically infinite due to derivations and compounding, but the zipped binary fits on a handful of floppies.

Re:Show HN: Regular expression compilation visualized by zokier on Tuesday March 23, 2021 @08:54AM (#26554413)
Many high-performance regex libraries use SIMD these days. Hyperscan might be the most prominent example of that, being made by Intel and all.