3 ms·

It is worth noting that the implementations for those benchmarks are contributed by a community, not all written by the same person (IIRC), so if someone is int

It is worth noting that the implementations for those benchmarks are contributed by a community, not all written by the same person (IIRC), so if someone is interested in using a language to the best of its hypothetical performance ceiling, they can definitely submit a solution. I'm not sure about the details for the "fasta" benchmark, but I know it's at least partly I/O bound, and many implementations for the benchmark are single-threaded: https://benchmarksgame.alioth.debian.org/u64q/performance.php?test=fasta https://benchmarksgame.alioth.debian.org/u64q/performance.ph... Notably, Rust also edges out a multi-threaded C implementation for that one. I'm sure they've done some very hairy optimizations to get to the top on that board, but it's cool to see that it's possible. On the subject of regexes, I am not familiar with the C++ std::regex implementation, but it does look like (some rather slow) C++ implementations are using a boost regex library. Those are generally fairly "standard" in C++, right?

petke 11y ago
I cant be sure about Rust, but C++ should at least be as fast as C for any fair benchmark. About the regex example. https://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexdna&lang=gpp&id=2 https://benchmarksgame.alioth.debian.org/u64q/program.php?te... The boost regex library is fast and widely used. It doesnt look like the example is using it though, but a library called "re2". Never heard of it before. Googling turned up this https://github.com/google/re2 https://github.com/google/re2
- dikaiosune 11y ago
  Re: regex, I was referring to some of the other C++ implementations: https://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexdna&lang=gpp&id=4 https://benchmarksgame.alioth.debian.org/u64q/program.php?te... https://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexdna&lang=gpp&id=3 https://benchmarksgame.alioth.debian.org/u64q/program.php?te... I have no idea whether it's the regex implementations that are causing the comparative slowness, to be honest. Just seemed interesting that some C++ implementations using what I would think are common techniques fall behind many other languages' implementations. Of course, benchmarks are always arbitrary, and some of them will just disadvantage approaches that would be perfectly realistic ways to solve "real-world" problems, so it's always a grain-of-salt situation. However I'm not sure it's necessarily fair to say that "C++ should be at least as fast as C for any fair benchmark." Doesn't that expose you to the danger of redefining fair benchmarks as "those benchmarks which reinforce my preconceived notions of which tools have what performance characteristics"?
  - petke 11y ago
    Probably bad wording by me. Cpp vs c has been benchmarked so extensively that it would be big news if C was quicker than Cpp at anything. Cpp is often faster though because of inlining of templates. Finally c is mostly just a subset of cpp. Its difficult to see how compiling the same code would be slower with a cpp compiler.
- burntsushi 11y ago
  There are 4 C++ benchmark submissions for regex-dna. One of them does indeed use boost, but it is significantly slower than RE2: https://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexdna&lang=gpp&id=3 https://benchmarksgame.alioth.debian.org/u64q/program.php?te... --- I don't know much about boost's regex support, but after a quick search, it does support backreferences, so it's likely a backtracking implementation. It's no surprise to me that it is beaten handedly by an implementation that uses DFAs (RE2, and in this case, Rust's regex library as well).
burntsushi 11y ago
> Notably, Rust also edges out a multi-threaded C implementation for that one. I'm sure they've done some very hairy optimizations to get to the top on that board, but it's cool to see that it's possible. The most important optimization I did was to avoid regex machinery as much as possible. In particular, Rust's regex library has very good support for prefix literal optimizations. In particular, regexes like `abc[x-z]foo|bar` will compile down to an aho-corasick[1] automaton over the strings `abcxfoo`, `abcyfoo`, `abczfoo` and `bar` with the failure transitions completely evaluated. (The end result is an automaton represented by a matrix. This is memory intensive, so only prefix literals of a certain size can be accommodated. But you don't need a lot to realize huge gains!) I wrote more about it here: https://www.reddit.com/r/rust/comments/39unje/ahocorasick_fast_multisubstring_matching/cs6lnxp https://www.reddit.com/r/rust/comments/39unje/ahocorasick_fa... Hint: most of the benchmark game regexes are relatively simple and compile down to either simple `memchr` calls (most regex engines will do that, nothing special) or a aho-corasick DFA that completely avoids the traditional regex evaluation machinery. In general, regex implementations differ dramatically in the optimizations they perform. It's hard to draw conclusions about them without some explicit knowledge of how it is implemented. [1] - https://github.com/BurntSushi/aho-corasick https://github.com/BurntSushi/aho-corasick

petke 11y ago

I cant be sure about Rust, but C++ should at least be as fast as C for any fair benchmark. About the regex example. https://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexdna&lang=gpp&id=2 https://benchmarksgame.alioth.debian.org/u64q/program.php?te... The boost regex library is fast and widely used. It doesnt look like the example is using it though, but a library called "re2". Never heard of it before. Googling turned up this https://github.com/google/re2 https://github.com/google/re2

dikaiosune 11y ago
Re: regex, I was referring to some of the other C++ implementations: https://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexdna&lang=gpp&id=4 https://benchmarksgame.alioth.debian.org/u64q/program.php?te... https://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexdna&lang=gpp&id=3 https://benchmarksgame.alioth.debian.org/u64q/program.php?te... I have no idea whether it's the regex implementations that are causing the comparative slowness, to be honest. Just seemed interesting that some C++ implementations using what I would think are common techniques fall behind many other languages' implementations. Of course, benchmarks are always arbitrary, and some of them will just disadvantage approaches that would be perfectly realistic ways to solve "real-world" problems, so it's always a grain-of-salt situation. However I'm not sure it's necessarily fair to say that "C++ should be at least as fast as C for any fair benchmark." Doesn't that expose you to the danger of redefining fair benchmarks as "those benchmarks which reinforce my preconceived notions of which tools have what performance characteristics"?
- petke 11y ago
  Probably bad wording by me. Cpp vs c has been benchmarked so extensively that it would be big news if C was quicker than Cpp at anything. Cpp is often faster though because of inlining of templates. Finally c is mostly just a subset of cpp. Its difficult to see how compiling the same code would be slower with a cpp compiler.
burntsushi 11y ago
There are 4 C++ benchmark submissions for regex-dna. One of them does indeed use boost, but it is significantly slower than RE2: https://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexdna&lang=gpp&id=3 https://benchmarksgame.alioth.debian.org/u64q/program.php?te... --- I don't know much about boost's regex support, but after a quick search, it does support backreferences, so it's likely a backtracking implementation. It's no surprise to me that it is beaten handedly by an implementation that uses DFAs (RE2, and in this case, Rust's regex library as well).

burntsushi 11y ago

> Notably, Rust also edges out a multi-threaded C implementation for that one. I'm sure they've done some very hairy optimizations to get to the top on that board, but it's cool to see that it's possible. The most important optimization I did was to avoid regex machinery as much as possible. In particular, Rust's regex library has very good support for prefix literal optimizations. In particular, regexes like `abc[x-z]foo|bar` will compile down to an aho-corasick[1] automaton over the strings `abcxfoo`, `abcyfoo`, `abczfoo` and `bar` with the failure transitions completely evaluated. (The end result is an automaton represented by a matrix. This is memory intensive, so only prefix literals of a certain size can be accommodated. But you don't need a lot to realize huge gains!) I wrote more about it here: https://www.reddit.com/r/rust/comments/39unje/ahocorasick_fast_multisubstring_matching/cs6lnxp https://www.reddit.com/r/rust/comments/39unje/ahocorasick_fa... Hint: most of the benchmark game regexes are relatively simple and compile down to either simple `memchr` calls (most regex engines will do that, nothing special) or a aho-corasick DFA that completely avoids the traditional regex evaluation machinery. In general, regex implementations differ dramatically in the optimizations they perform. It's hard to draw conclusions about them without some explicit knowledge of how it is implemented. [1] - https://github.com/BurntSushi/aho-corasick https://github.com/BurntSushi/aho-corasick