Implement / optimize the shootout benchmarks

[kud1ing]

This is supposed to be a meta issue for optimization efforts like http://www.reddit.com/r/rust/comments/2j2ij3/benchmark_improvement_reverse_compliment/

The benchmarks to optimize (where rustc is slower than g++, according to http://benchmarksgame.alioth.debian.org/u64q/rust.php):

• binary-trees
• pidigits
• mandelbrot
• fannkuch-redux (fixed by Update fannkuchredux benchmark #16999)
• fasta
• k-nucleotide
• n-body
• reverse-complement (fixed by Improve shootout-reverse-complement #18143, simplify shootout-reverse-complement.rs #18357)
• spectral-norm (fixed by bench: Improve the spectralnorm shootout benchmark #17989)
• regex-dna
• fasta-redux (Rust version missing)

Secondary benchmarks:

• meteor-contest
• chameleos-redux
• thread-ring
• binarytrees-redux

[kud1ing]

cc @brson @TeXitoi

[TeXitoi]

see #17989 for spectral-norm

You can add secondary benchmarks: meteor-contest, chameleos-redux, thread-ring, binarytrees-redux

[kud1ing]

Thank you, done.

[TeXitoi]

You can tick spectral-norm :)

[kud1ing]

@TeXitoi Done

[thestinger]

The comparison should be with either C or C++, depending on which has a faster implementation. The C solutions are also valid C++ solutions so even a comparison to C++ would take them into account. These are typically the most optimized ones, not the higher-level ones taking advantage of C++ language features.

[kud1ing]

We probably all share a dislike for microbenchmarks, but i think we need to play this game since many people judge Rust by it. And since Rust is seen as a C++ alternative, they will probably look at how Rust compares to the C++ shootouts. If Rust turns out to be faster than any language/implementation, i'd be more than happy.

[thestinger]

@kud1ing: The C implementations are usable as C++ ones. Rust as seen as an alternative to C and C++, not just C++. If you want to ignore them then I'll happily resubmit the C implementations as slightly modified C++ implementations to move the bar to where it should be.

[kud1ing]

I am not opposed to aim for what falls in the "gcc" category in the benchmarks game.
Aiming for "g++" first, has a smaller scope and thus is more attractive - and even that will take weeks to achieve.