3 ms·
This applies to non-backtracking non-DFAs too: https://github.com/rust-lang/regex/issues/787#issuecomment-1255190748 https://github.com/rust-lang/regex/issues/7
by burntsushi 4y ago
This applies to non-backtracking non-DFAs too: https://github.com/rust-lang/regex/issues/787#issuecomment-1255190748 https://github.com/rust-lang/regex/issues/787#issuecomment-1...
The GitHub issue comment is perhaps a bit high context. I wrote this reddit comment the other day that is lower context and probably more accessible: https://old.reddit.com/r/rust/comments/zsntov/pomsky_08_released_a_powerful_and_modern_regular/j18yr06/ https://old.reddit.com/r/rust/comments/zsntov/pomsky_08_rele...
High level problem: general purpose regex engines that use finite state machines basically never build DFAs. Some of them will build lazy DFAs, but sometimes the lazy DFA can't or shouldn't be used. So you're stuck with an NFA simulation or bounded backtracking. And in those cases, getting rid of the alternation clog can be hugely beneficial (by orders of magnitude).
- gleenn 4y agoDo you know is Java's built-in regex engine builds a DFA? This is all news to me. I built that optimizer because we were doing something pretty naive at work I suppose: we were doing the string concatenation joining with | for a relatively large set of strings and got a notably large speedup so I'm going to assume Java doesn't. It was a very fun project none-the-less :)
- burntsushi 4y agoI don't know much about Java's regex engine, but my understanding is that it's a backtracker. Indeed, such an optimization can make the regex go from intractably slow to quite fast.
- gleenn 4y agoWe used my regex compressor and saw a very large speedup on a large production system so anecdotally it was very useful.