8 ms·

Any rust lovers out there: Could I ask you do a benchmark comparison and a fuzz comparison. I'd be genuinely interested in the result and if (as you might hope)

• gcp 10y ago
  The Rust regex library is written by the same guy who wrote ripgrep. I'd be surprised if it didn't run circles around boost::regex.
• stuckagain 10y ago
  If you were interested in performance you probably would not have been using boost::regex to begin with. RE2 is often an order of magnitude faster. You might choose boost if you require backtracking, but that's crazy anyway due to exponential time.
  • 0xFFC 10y ago
    What is backtracking?
    • bowmessage 10y ago
      http://stackoverflow.com/questions/9011592/in-regular-expressions-what-is-a-backtracking-back-referencing http://stackoverflow.com/questions/9011592/in-regular-expres...
    • Phritzy 10y ago
      https://regex101.com/r/G23xYd/2 https://regex101.com/r/G23xYd/2
      • deleted 10y ago
        [deleted]
    • kbenson 10y ago
      A feature of certain types of regular expression engines. It allows for certain types of regular expressions but at the cost of possibly going exponential if you aren't careful about your expression. [1] 1: http://www.regular-expressions.info/catastrophic.html http://www.regular-expressions.info/catastrophic.html
    • carussell 10y ago
      Looks like there's (a lot of) confusion in these comments about the difference between backtracking and backreferences. The `\2` in Phritzy's snippet is a backreference. Backtracking is an implementation strategy for writing a regular expression engine. I don't know why anyone choosing an engine would "require backtracking". It's an implementation detail, not a feature. (Although the fact that Thompson NFAs avoid exponential time complexity inherent to backtracking is something that I suppose could be considered a feature.) Here's a link to some real literature: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
      • stuckagain 10y ago
        There are features of some regular expressions for which the only known solution is backtracking. If you want those features then you "require backtracking".
        • ue_ 10y ago
          Out of interest, what are some of these? I have a hard time believing that the implementors of the Perl regex engine chose to write it that way for no reason while the Thompson NFA figures are thrown about. I knew there must havevbeen something this 'implementation detail' was good for.
          • eridius 10y ago
            I believe backreferences require backtracking.
            • tatref 10y ago
              No, but variable size lookahead/behind do. This is because the engine has to go back if the remaining part of a regex fails. For some examples, see http://www.regular-expressions.info/recursebacktrack.html http://www.regular-expressions.info/recursebacktrack.html) EDIT: you are correct, backreferences do require backtracking, my bad.
          • 10y ago
  • flogic 10y ago
    In my experience, the exponential time thing isn't really a big deal. I've used Perl regular expressions on a very regular basis for about 16 years now. Exponential time has been an issue only once. Obviously if I were accepting regular expressions from random people, I'd use RE2. But for my day to day purposes, it's pretty much a complete non issue.
    • kbenson 10y ago
      > Obviously if I were accepting regular expressions from random people, I'd use RE2. And if you're using Perl, it's not hard to do so[1]. Pluggable regex engines FTW. :) 1: https://metacpan.org/pod/re::engine::RE2 https://metacpan.org/pod/re::engine::RE2
    • kmike84 10y ago
      re2 is not only about exponential time: matching of regexes like a|b|c is O(N) in backtracking engines and O(1) in DFA-based engines like re2. It can make a big difference in practice for generated regexes - e.g. if you want to check if an URL has one of the thousand substrings in it (think adblock-like use cases). With backtracking regex or with a loop it'd be O(N) regarding the number of options, but with DFA it is O(1) regarding the number of options. I've seen 1000x speedups for similar use cases with re2 vs re from Python stdlib.
      • adrianN 10y ago
        How does the DFA engine match anything without looking at the whole input?
        • haldean 10y ago
          I think s/he meant to say O(nm) vs O(m), n being the number of branches in the regex and m being the length of the input.
  • slavik81 10y ago
    Is there a quick and easy way to check if a particular regex could take exponential time?
    • WildUtah 10y ago
      All regexes run in O(N) where N is the length of the string matched. But some regex engines accept non-regular expressions. [0] The usual notation for it is an escaped number: \1 or \2 or so on. They're used to refer back to capturing groups earlier in the expression, usually marked by parentheses. Regular expressions don't have backreferences but various enhanced expressions add them. If you use those extensions, you are in danger of exponential execution time unless you are careful and know what you're doing. In particular you should know not to use regular expressions as your principal tool to build a parser. [0]https://en.wikipedia.org/wiki/Chomsky_hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy
      • burntsushi 10y ago
        It's worth pointing out that if you're using a regex engine that only uses backtracking, then you can't assume all regular expressions take linear time. For example, running `(a)c` against `aaaaaaaaaa` takes exponential time in the number of `a` characters even though it is regular. A hybrid regular expression engine could, in theory, recognize that a particular expression is regular and therefore use a finite state machine to guarantee linear time and space execution (where the size of the regex is held constant).
        • beeforpork 10y ago
          But unfortunately, converting a non-deteministic finite automaton (i.e., regexp) to a deterministic finite automaton (i.e., engine that can do matches in linear time) may take exponential time and/or space. Yet, I should add, flex does that with extraordinary success. Most grammars are not that bad, it seems.
          • burntsushi 10y ago
  • zintinio5 10y ago
    From my understanding the main benefit of RE2 is not speed, but linearly scaling execution time with respect to the input size, along with bounded memory usage. For certain inputs, it may outperform other engines, but the converse may also be true. As with any feature that may be abused, backtracking may also be useful: for example, you may need to write a script to munge text. Since you're not exposing it to arbitrary user input, it's a reasonable feature.
    • stuckagain 10y ago
      RE2 is not dramatically faster than all other regex implementations, but it is dramatically faster than boost::regex, which is among the slowest I've ever tested.
      • zintinio5 10y ago
        Ah, fair enough.
• gpm 10y ago
  You can look at a well known (but not very complete) benchmark comparison here [0], rust wins, the fastest boost program is c++ g++ #3 and takes 8.5 times as long, the fastest c++ implementation (using re2) takes twice as long. I don't know of a fuzz comparison, but there has been fuzzing done on the rust library without finding anything bad, e.g. see this issue [1]. [0] http://benchmarksgame.alioth.debian.org/u64q/performance.php?test=regexdna http://benchmarksgame.alioth.debian.org/u64q/performance.php... [1] https://github.com/rust-lang/regex/issues/203 https://github.com/rust-lang/regex/issues/203
  • justinmk 10y ago
    > benchmark comparison here [0], rust wins, the fastest boost program is c++ g++ #3 and takes 8.5 times as long With PHP at #2? Doesn't seem credible, or the thing being tested isn't meaningfully language-dependent.
    • dbaupp 10y ago
      Indeed, it is the regex implementation that is being tested (and so the language of that implementation is relevant), which is exactly what this discussion is about and also why that comment is careful to be specific about which programs are using which regex implementation.
    • beering 10y ago
      It's testing each language's implementation of regexes. A lot of the languages are probably linking in a regex library written in C or C++ anyways. It's evidence that if you're writing something that's heavy on regexes, any slowdown probably isn't due to the language itself but its library implementation.
    • deleted 10y ago
      [deleted]
    • deleted 10y ago
      [deleted]
    • barkingcat 10y ago
• thomasahle 10y ago
  Regex seems to be one of the big strengths of Rust, performance wise: https://benchmarksgame.alioth.debian.org/u64q/performance.php?test=regexdna https://benchmarksgame.alioth.debian.org/u64q/performance.ph... (C++ g++ #4 uses Boost)
• dikaiosune 10y ago
  It does look like the afl.rs project (afl for rust code) has been run on regex: https://github.com/frewsxcv/afl.rs#trophy-case https://github.com/frewsxcv/afl.rs#trophy-case Which resulted in just one issue? I'm not sure how long they fuzzed or what the methodology was, but this was the panic they found (still not a memory safety issue, more akin to an unchecked exception in Java than a crash in C++): https://github.com/rust-lang/regex/issues/84 https://github.com/rust-lang/regex/issues/84 Since that issue is from the same time as Rust's 1.0 release, I suspect that either it hasn't been run again recently or that things are pretty stable in the regex crate w.r.t. fuzzing.
  • mastax 10y ago
    Also more recently: https://github.com/rust-lang/regex/pull/262 https://github.com/rust-lang/regex/pull/262
• PudgePacket 10y ago
  It's not related to fuzzing but this article is definitely an interesting one that involved a lot of regex in rust http://blog.burntsushi.net/ripgrep/ http://blog.burntsushi.net/ripgrep/.
• burntsushi 10y ago
  As others have mentioned, Rust's regex library has been fuzz tested. Most of the bugs have been fixed. There are a couple outstanding that I hope to get to soon. None of them have been unsafe memory bugs. :-) Benchmarking is a bit mirkier. The benchmark game has already been linked, but the regex-dna benchmark can't really be used to judge the overall performance of regex engines. It's not that the regex-dna benchmark is bad on its own, but rather, it's not enough. You need more coverage. For example, regex engines with aggressive literal optimizations will do very well on regex-dna. Rust's regex library does have a benchmark harness that compares it to many other popular regex engines: PCRE1 w/ JIT, PCRE2 w/ JIT, RE2, Tcl's engine and Oniguruma. In general, Rust's regex engine is competitive with PCRE{1,2} and RE2, but does quite a bit better than both Tcl and Oniguruma. I haven't added Boost to this harness, but in theory it would be relatively easy. You can see how I did it for RE2[1]. Unfortunately, the set of benchmarks in the harness---while probably better than any other benchmark I've seen---has two major problems with it: 1. It is biased. I wrote most of the benchmarks and I'm not terribly familiar with the types of optimizations performed by sophisticated backtracking engines. Moreover, many of the benchmarks were added to measure optimizations I added to Rust's regex engine, so there will naturally be more benchmarks where Rust does well. 2. The benchmarks themselves lack analysis. Microbenchmarks are too hard to interpret using numbers alone. Someone needs to do the work to explain the results. I've always intended to do this, but it is a gargantuan task. I've just updated the repo to contain the benchmark results as of today[2]. The most interesting comparison is PCRE2, which is quite fast.[3] Most of the interesting benchmarks are defined in sherlock.rs[4], which also contains some Rust specific notes. Another source of benchmarks is my blog post on ripgrep[5]. This isn't really a benchmark for regex engines, but rather, a benchmark for line oriented search tools. Nevertheless, it is a collection of data points. [1] - https://github.com/rust-lang/regex/blob/master/bench/src/ffi/re2.rs https://github.com/rust-lang/regex/blob/master/bench/src/ffi... [2] - https://github.com/rust-lang/regex/tree/master/bench/log/05 https://github.com/rust-lang/regex/tree/master/bench/log/05 [3] - https://github.com/rust-lang/regex/blob/master/bench/log/05/pcre2-vs-rust https://github.com/rust-lang/regex/blob/master/bench/log/05/... [4] - https://github.com/rust-lang/regex/blob/master/bench/src/sherlock.rs https://github.com/rust-lang/regex/blob/master/bench/src/she... [5] - http://blog.burntsushi.net/ripgrep/ http://blog.burntsushi.net/ripgrep/