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.

[TeXitoi]

@kud1ing you can add #18357 to reverse-complement and ticks it! http://benchmarksgame.alioth.debian.org/u64q/benchmark.php?test=revcomp&lang=all&id=4&data=u64q

Thanks to @mahkoh for this one :)

[kud1ing]

Done, thanks. Awesome.

[bstrie]

Optimizing regex-dna is blocked on #16989. It's also the slowest by far of all our programs on the benchmarks game.

This may seem spurious, but I'm nominating this for 1.0 (with the possible exception of regex-dna, if enhancements to regex! would take too long). Marketing matters!

[thestinger]

@bstrie: There are other slow implementations:

http://benchmarksgame.alioth.debian.org/u64q/compare.php?lang=rust&lang2=gcc

The default baseline language will switch once it gets a bit faster, and then it looks bad again.

[thestinger]

(which is why Python, JavaScript, etc. get compared against Java)

[brson]

P-low. We show pretty well on their already. More effort is desired, but icing.

[steveklabnik]

I'm pulling a massive triage effort to get us ready for 1.0. As part of this, I'm moving stuff that's wishlist-like to the RFCs repo, as that's where major new things should get discussed/prioritized.

This issue has been moved to the RFCs repo: rust-lang/rfcs#665