3 ms·

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

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.

zokier 6y ago
Many high-performance regex libraries use SIMD these days. Hyperscan might be the most prominent example of that, being made by Intel and all.
JoelJacobson 6y ago
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
unhammer 6y ago
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf 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=Taiteilijaperheeseen%20syntynyt%20Jansson%20oli%20jo%20lapsuudestaan%20asti%20tuottelias%2C%20ensin%20etenkin%20kuvataiteilijana%20ja%20my%C3%B6hemmin%20kirjailijana%20ja%20kuvittajana.#analyzation 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.
burntsushi 6y ago
> 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.)

zokier 6y ago

Many high-performance regex libraries use SIMD these days. Hyperscan might be the most prominent example of that, being made by Intel and all.

JoelJacobson 6y ago

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

unhammer 6y ago

https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf 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=Taiteilijaperheeseen%20syntynyt%20Jansson%20oli%20jo%20lapsuudestaan%20asti%20tuottelias%2C%20ensin%20etenkin%20kuvataiteilijana%20ja%20my%C3%B6hemmin%20kirjailijana%20ja%20kuvittajana.#analyzation 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.

burntsushi 6y ago

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