regex

for multiple patterns. The performance of Commentz-Walter degrades as the number of patterns increases because there's fewer opportunities for meaningful skips. Nevertheless, small/short alternations are probably the common case with GNU grep. (The state of the art has actually improved for this specific case and GNU grep could probably benefit. Specifically, the Hyperscan folks over at Intel have some really cool SIMD algorithms for matching multiple patterns. I implemented one here (the comments include a description with examples): https://github.com/rust-lang-nursery/regex/blob/master/src/s...) * The actual regex engine is a lazy DFA (similar to RE2) in that its states are computed on-demand as needed. That is, some parts of the DFA that aren't used are never computed at all. If the DFA gets too big in memory, the existing states are dropped and re-computed as needed. In this way, GNU grep gets the performance of a DFA while preserving linear time matching. (At most one new DFA state is computed for each byte of input.) The inner DFA loop is unrolled. * To re-emphazie a point from the post: avoiding line-by-line matching is critical. This makes it much easier to extract literals from a pattern. For example, if your pattern is `\w+foobar\d+`, then GNU grep can still search for `foobar` because it can make an assumption that its haystack is generally a very small slice of the entire search space (i.e., a single line). This type of optimization is much harder to pull off in a general purpose regex engine. A general purpose regex engine might limit itself to looking for prefix or suffix literals only. * GNU grep really doesn't do all that well for multi-byte encodings. e.g., The time difference between `LC_ALL=C egrep -c '\w{5}'` and `LC_ALL=en_US.UTF-8 egrep -c '\w{5}'` on a large file is quite dramatic. (~3 seconds vs ~52 seconds for a ~2GB mostly-ASCII file that is warm in my page cache.) There's really no need for this slow down if you can bake UTF-8 decoding into your DFA (RE2 does this). However, you then lose the ability to `grep` over other character encodings without transcoding them to UTF-8 first. (In fact, GNU grep may be doing this transcoding step today anyway, so maybe baking UTF-8 into your DFA would be a strictly better solution since it would be much faster on a much larger number of inputs, but probably not slower than any inputs. However, I'm not terribly familiar with this part of GNU grep, so I could have this wrong.)

in general by a lot, but, the lazy DFA requires two scans of the candidate: one to find the end position and another to find the start position. That extra scan made processing this regex (on the regex-dna input) slightly slower. I've since fixed some of this by reducing a lot of the match overhead of the lazy DFA, so my hope is that it's back to par, but I haven't done any rigorous benchmarking to verify that. > Wasn't the program relatively faster because you wrote the regex crate to use Aho-Corasick for the matches required by the regex-dna task? Aho-Corasick is principally useful for the second phase of regex-dna, e.g., the regexes that look like `ag[act]gtaaa|tttac[agt]ct`. (In the last phase, all the regexes are just single byte literals, so neither Aho-Corasick nor the regex engine should ever be used.) Performance here should stay the same. On that note, I have a new nightly-only algorithm called Teddy that uses SIMD[1] (which replaces the use of Aho-Corasick for those regexes) and is a bit faster. I got the algorithm from the Hyperscan[2] project, which also does extensive literal analysis to speed up regexes. To clarify, this optimization is generally useful because a lot of regexes in the wild have prefix literals. Even something like `(?i:foo)\s+bar` can benefit from it, since `(?i:foo)` expands to FOO, FOo, FoO, Foo, fOO, fOo, foO, foo, which can of course be used with Aho-Corasick (and also my new SIMD algorithm). One also must wonder how well a C program using PCRE2's JIT would fair on the benchmarks game. From my experience, it would probably be near the top. It's quite fast! [1] - https://github.com/rust-lang-nursery/regex/blob/master/src/s... [2] - https://github.com/01org/hyperscan

ts all states, then `nlist` (which is maintained while following all states at any position in the input) will contain all states. In each subsequent iteration (line 165), even if the state wants to visit all states, it will be immediately stopped at the first check in line 300. No additional states for that state are followed.

mode. (The sherlock::line_boundary_sherlock_holmes benchmark.) We could do this too---I just haven't yet. * The sherlock::word_ending_n benchmark has a word boundary, which the lazy DFA in Rust's regex library doesn't support. (It will be hard to improve here unfortunately.) * In general, I think PCRE probably has less overhead per match, which I haven't worked on too much. (For one, every search requires acquiring and quickly releasing a mutex in Rust's library. All I really need to do is push/pop from a stack, so I bet we could avoid the mutex.) On the rest of the regexes, Rust's library is either competitive or completely smashes PCRE in throughput. There are even a few benchmarks that I had to omit because PCRE was too slow. These are strong words, so my goodness, do I hope I'm benchmarking PCRE right! :P And this was all work done based on what Russ Cox wrote. Actual benchmark code is here: https://github.com/rust-lang-nursery/regex/blob/master/bench...