Regex literals optimization (or how to cheat on benchmarks) (opens in new tab)

(nitely.github.io)

42 pointsnitely5y ago11 comments

11 comments

7 comments · 2 top-level

willvarfar5y ago· 3 in thread

How does it eg googles re2?

I remember a neat feature of re2 was you could give it a bunch of regex, and get it to check for all of them at the same time. Made all the difference in an early spam filter I built.

nitelyOP5y ago

It doesn't. RE2 searches for a prefix of literals. If the regex doesn't start with one or more literals, then the full regex engine is ran.

froh5y ago

With 1960s computer science - regular languages, their equivalent nondeterministic finite state machines or nondeterministic finite automata NFA and the transformation thereof into deterministic ones DFA. In theoretical worst case the size of the DFA is exponential in size to the NFA, in practice, re2, these algorithms are frickin' awesome.

chubot5y ago

In theoretical worst case the size of the DFA is exponential in size to the NFA

That's true, but mostly irrelevant in practice as you say. Because the NFA is linear in proportion to PATTERN size, not input size, and even an exponential blowup from there isn't a problem. (and many patterns may not blow up)

For example I wrote a very large set of regular languages to describe shell syntax. Compiling it all to a full DFA and then assembly via re2c creates something like 30 KiB of machine code. And it runs fast.

https://www.oilshell.org/release/0.8.5/source-code.wwz/_devb...

http://www.oilshell.org/blog/2020/01/parser-benchmarks.html

So as you say, you get the best of both worlds: a concise language, and speed. The only problem is the syntax, which I'm fixing:

http://www.oilshell.org/release/latest/doc/eggex.html

1 more reply

ridiculous_fish5y ago· 2 in thread

How does nim-regex implement capture groups and zero-width assertions (like \b)? Both of those are tricky with DFAs.

nitelyOP5y ago

Yeah, nim-regex is based on NFA. I'm not aware of a pure DFA that is correct and also supports those. I built an hybrid a while ago[0], but it's slower than nim-regex when it needs to capture/assert, I should profile it and find out why some day.

[0] https://github.com/nitely/nregex

ridiculous_fish5y ago

re2 implements captures as "tagged DFAs" (Laurikari algorithm) while zero-width assertions are implemented as running the algorithm "one byte ahead". Neither of these techniques is very well known.

1 more reply

j / k navigate · click thread line to collapse

11 comments

7 comments · 2 top-level

willvarfar5y ago· 3 in thread

How does it eg googles re2?

I remember a neat feature of re2 was you could give it a bunch of regex, and get it to check for all of them at the same time. Made all the difference in an early spam filter I built.

nitelyOP5y ago

It doesn't. RE2 searches for a prefix of literals. If the regex doesn't start with one or more literals, then the full regex engine is ran.

froh5y ago

chubot5y ago

In theoretical worst case the size of the DFA is exponential in size to the NFA

https://www.oilshell.org/release/0.8.5/source-code.wwz/_devb...

http://www.oilshell.org/blog/2020/01/parser-benchmarks.html

So as you say, you get the best of both worlds: a concise language, and speed. The only problem is the syntax, which I'm fixing:

http://www.oilshell.org/release/latest/doc/eggex.html

1 more reply

ridiculous_fish5y ago· 2 in thread

How does nim-regex implement capture groups and zero-width assertions (like \b)? Both of those are tricky with DFAs.

nitelyOP5y ago

[0] https://github.com/nitely/nregex

ridiculous_fish5y ago

re2 implements captures as "tagged DFAs" (Laurikari algorithm) while zero-width assertions are implemented as running the algorithm "one byte ahead". Neither of these techniques is very well known.

1 more reply

j / k navigate · click thread line to collapse