4 ms·
In a comment, Lemire says: "In my tests, regex is 100x slower". Might he be including the regex compilation time? His snippet literally shows the regex constr
by kazinator 4y ago
In a comment, Lemire says: "In my tests, regex is 100x slower".
Might he be including the regex compilation time?
His snippet literally shows the regex construction and call being in the same scope, by indentation level:
const std::regex txt_regex("(https)|(http)|(ftp)|(file)|(ws)|(wss)");
// later...
bool match = std::regex_match(v.begin(), v.end(), txt_regex);
The const won't help you here, what you want is static?
Also, the parentheses aren't doing anything in that regex; and in many regex languages, parentheses are loaded with complicated semantics of group capture; I'd keep those out.
- yakubin 4y agostatic would move the construction to before main(). In big projects that becomes an issue, when you have tons of little static objects defined here and there.
- kazinator 4y agoIt shouldn't be a problem for something entirely self-contained like a regex. If other static constructions try to use it before main() is called, then that could be a problem.
- yakubin 4y agoI'm not talking about dependencies, but about the time spent before main(). It delays startup. Another thing is that local static variables often compile to fairly horrific long code with branches. Better just move it to a wider scope or a longer-lived struct/class member somewhere.
- gleenn 4y agoAlso, they could compress the regular expressions for speedup by using a trie data structure and then walking the trie to match common-overlap. This is a Java example but you could easily port it or even just run it in Java and then export the regex after running with your fixed set of strings and paste into C++: https://github.com/gleenn/regex_compressor https://github.com/gleenn/regex_compressor
- kazinator 4y agoThe NFA -> DFA subset construction will identify and squeeze out the overlaps. Compressing regexes, I suspect, is a pointless excercise, except as a preprocessing pass before a pseudo-regex engine that does backtracking (e.g. Perl).
- kazinator 4y agoSome of these backtracking regex engines have problem semantics like if both a|abc can match a string, the left match will win, so only "a" gets matched. If you put some compressing pass before that, you have to be careful not to mess that up. Basically "abc" can be deleted in this example. then you compress.
- burntsushi 4y agoThis 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 :)