Live data from Hacker News

New Rust hash table leads Benchmarks Game

benchmarksgame.alioth.debian.org

141–150 of 156 posts

Re: New Rust hash table leads Benchmarks Game

#141
post #137

Earlier quoted context omitted.

For what it's worth, this alternate implementation has only one line of unsafe code (a call to the libc "memchr" function) and is only 9% slower than the fastest unsafe version: https://github.com/mbrubeck/benchmarksgame-rs/blob/reverse_c... It's very easy to write extremely fast safe Rust code. (The safe Rust version above is faster than the fastest C++ submission, on my computer.) Using "unsafe" for optimization is…

> one line of unsafe code (a call to the libc "memchr" function) Is burntsushi's Rust implementation of memchr notably slower than libc's?

The rust-memchr crate uses libc's memchr if it's available and known to be fast. Otherwise, it falls back to a pure Rust implementation (written by bluss, not me).

I expect this to change once we get SIMD. ;-)

Re: New Rust hash table leads Benchmarks Game

#142
post #130
post #125

Earlier quoted context omitted.

Java #6 => HashMap http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... Java #3 => HashMap http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... Java #5 => HashMap http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... Java #4 => HashMap http://benchmarksgame.alioth.debian.org/u64q/program.php?tes...

Those are different implementations; I know those exist, and which is why I had specifically said there were multiple implementations and pointed at the "faster one", which is obviously the one most people are going to be paying attention to, and which is the one that is also most relevant as we could and probably should expect the implementations for other languages to use some crazy one-off library: it demonstrates…

> I know those exist…

So you knew why I said -- Not "instead of" as-well-as.

> … knee-jerk link to have me contribute a different implementation for C++ …

Improved programs are welcome, period. Hence the link.

> What is going through your head when you read my comments?

Will this sentence never end :-)

> … mostly teaches us about different things than "who is winning"? … the high-level idea of "what are we doing here".

There are links on the home page which provide context.

Re: New Rust hash table leads Benchmarks Game

#143
post #139

Earlier quoted context omitted.

For what it's worth, this alternate implementation has only one line of unsafe code (a call to the libc "memchr" function) and is only 9% slower than the fastest unsafe version: https://github.com/mbrubeck/benchmarksgame-rs/blob/reverse_c... It's very easy to write extremely fast safe Rust code. (The safe Rust version above is faster than the fastest C++ submission, on my computer.) Using "unsafe" for optimization is…

Wonderful, thank you! Producing the safe versions which are that efficient is really the best argument for Rust that I can imagine.

As an update, this pull request now removes most of the unsafe code:

https://github.com/TeXitoi/benchmarksgame-rs/pull/46

Re: New Rust hash table leads Benchmarks Game

#144
post #129

Earlier quoted context omitted.

>> Java is showing quite impressive numbers! 359% more RAM isn't very impressive. Even less so when one considers the 20+ years of effort spent to achieve it. You know what impresses me? A 22 month old language besting everything else while guaranteeing no segfaults or NPEs at compile time. That's impressive.

Not that I don't disagree with the general idea of this post, but it's worth pointing out that while Rust is fairly young based on the 1.0 release date, there was a large amount of time prior to that where the language underwent a number of changes. It's also worth remembering that this is just a game, and as such it's somewhat of an apples-to-oranges comparison. Java's RAM usage may not be impressive compared to C,…

>> while Rust is fairly young based on the 1.0 release date, there was a large amount of time prior to that where the language underwent a number of changes.

Both Rust and Java had similar intervals between start of development and 1.0 release, which is what I carefully referenced my claims to. The comparison is fair; deliberately conservative actually given Java 1.0 in 1995 (now 22 years ago.)

>> I don't see a reason that both Rust and Java's results can't be impressive in their own right.

The state of the art has moved on. There was a time when Java pulling to within 50-ish percent of a 45 year old programming language was impressive; back around 2005 or so. It's old hat now and there is little evidence the gap is going to close much further.

Re: New Rust hash table leads Benchmarks Game

#146
post #116

Earlier quoted context omitted.

> Except through the backdoor, where language implementors can sometimes tweak libraries to circumvent restrictions. Which programming language implementations are doing that to your knowledge? "… Kernels … Toy programs … Synthetic benchmarks … discredited today, usually because the compiler writer and architect can conspire to make the computer appear faster on these stand-in programs than on real applications." htt…

> Which programming language implementations are doing that to your knowledge? My point here is not that this is being done (I'm generally assuming that language implementors have better things to do than to pollute their standard libraries for a benchmark game); I was making a different point, namely the inability to do algorithmic improvement, and mentioned that possibility for the sake of completeness.

There's been a good deal of play, flex and slop in the interpretation of "use the same algorithm" for some of those tasks.

I think your point is more that "Don't optimize away the work." is antithetical to what we do.

Re: New Rust hash table leads Benchmarks Game

#147
post #146

Earlier quoted context omitted.

> Which programming language implementations are doing that to your knowledge? My point here is not that this is being done (I'm generally assuming that language implementors have better things to do than to pollute their standard libraries for a benchmark game); I was making a different point, namely the inability to do algorithmic improvement, and mentioned that possibility for the sake of completeness.

There's been a good deal of play, flex and slop in the interpretation of "use the same algorithm" for some of those tasks. I think your point is more that "Don't optimize away the work." is antithetical to what we do.

All of the benchmark game problems either prescribe using a fixed algorithm or have an obvious optimal asymptotic complexity. The remaining challenge is generally to reduce the constant factor as much as possible.

This is just not what a lot of computationally expensive problems look like in practice. As a simple example, any practical solution for an NP-hard problem will be full of tradeoffs; often you just want something that's good enough and then you get to choose and adjust an algorithm for your particular problem space to find the sweet spot between time complexity and quality of the solution.

The benchmark games also have fairly simple and obvious data structures; most of them just deal with arrays and strings. Real-world problems often require you to make difficult choices about representation (where one is optimal in some situations, another in a different set of situations, but you handle all of them). Example: adjacency matrixes can be represented as bit matrices, integer/float matrices (if edges can have weights), or associate arrays of sets, to name just a few implementation options. Depending on how your graph is structured (sparse vs. dense, connectivity) and what algorithms you require, one or the other can be optimal. Clever choices can make orders of magnitude of difference for performance.

I'll offer you a concrete example: computing the factorial of large numbers basically has three well-known algorithms: (1) naive multiplication, (2) divide-and-conquer, (3) prime decomposition. Each subsequent approach improves performance over its predecessor, but is also increasingly more difficult to implement.

Now, it so happens that this particular problem is well-researched, so you can look it up, but you encounter similar problems all the time where you can't find them on stackoverflow or in the literature. And then you have to consider tradeoffs between the time spent researching better solutions, implementing those better solutions, and the time gained from the increased performance.

Re: New Rust hash table leads Benchmarks Game

#148

When SIMD goes stable rust may dominate that game. Still wish they would use clang so it was apples to apples with c and c++. Edit: actually I wish they would add clang for those languages and leave GCC for comparison. Then I'd want FORTRAN to add gfortran for the same reason.

Yeah, I think SIMD will be the next big jump for these benchmarks. I also wish we could see clang used with the C/C++ cases.

If llvm fixes a misoptimization bug rust can start passing noalias information again and that will cause auto vectorization in many cases. That would show up in the benchmarks too. That is why FORTRAN is winning n-body without any explicit SIMD code.

Re: New Rust hash table leads Benchmarks Game

#149
post #85
post #77

Earlier quoted context omitted.

My understanding was that GCC was better in more scenarios most of the time, but now it seems like Clang has caught up. and Maybe Clang 4.0 is even faster in more. Here are some recent benchmarks from phoronix: http://www.phoronix.com/scan.php?page=article&item=gcc7-clan...

Yeah. But in this kind of tuned benchmark, I doubt clang will do any better across the board - especially not considering the fact that the current programs are likely to be at least somewhat tuned specifically for gcc.

Clang does well enough to be the default compiler for Apple and Google. It can't be that far behind.

Re: New Rust hash table leads Benchmarks Game

#150

Does anybody know what happened to the image charts like this one for example? https://web.archive.org/web/20121218042116/http://shootout.a... This was my favourite feature of the benchmarks game.

Those charts provide an instant without-thought comparison (which can be helpful in other situations and with other data sets).

In this situation: it's helpful to slow-down, look at the source-code, think about what's being compared …

Post reply on HN