New Rust hash table leads Benchmarks Game • Hacker News Board

Re: New Rust hash table leads Benchmarks Game

#71

Post by kzrdude » Mon, Feb 27, 2017, 7:04 PM UTC

mbrubeck wrote: post #58

In other Rust/benchmarksgame news, I just submitted a simple fix to the Rust program for "reverse-complement" that makes it faster than the fastest C++ program, on my computer. The old version was spending 2/3 of its time just reading the input into memory, because it wasn't allocating a large enough buffer up front. https://github.com/TeXitoi/benchmarksgame-rs/pull/44 I'm also working on some additional changes that…

Would it be any worse to use `File::open("/dev/stdin")` there, so that it is safe code?

Re: New Rust hash table leads Benchmarks Game

#72

Post by tveita » Mon, Feb 27, 2017, 7:04 PM UTC

makmanalp wrote: post #57

Is there something fishy going on with the NaiveHashMap here? What's happening? impl Hasher for NaiveHasher { fn finish(&self) -> u64 { self.0 } fn write(&mut self, _: &[u8]) { unimplemented!() } fn write_u64(&mut self, i: u64) { self.0 = i ^ i >> 7; } }

NaiveHasher (declared as "struct NaiveHasher(u64);") is a tuple with one 64-bit field named "0". (Tuple fields are implitly named as 0, 1, 2 ...)

It implements a very simple hashing function for 64-bit numbers, each hashed number n overwrites the state with n xor (n >> 7). finish() will return the last written state.

This seems to work okay since the hashed structure "Code" contains exactly one 64-bit field.

I don't know if it's fishy, but it's certainly very custom. For a generic hashing implementation you'd at least want to mix in the previous state. I assume it was done more for brevity than performance though.

Re: New Rust hash table leads Benchmarks Game

#73

Post by masklinn » Mon, Feb 27, 2017, 7:06 PM UTC

igouy wrote: post #69

Previously std::collections::HashMap was used with the default hash function -- [46.03 secs] http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... ) and then the hash function was changed to FnvHasher -- [17.10 secs] http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... and then better use of quad core with futures_cpupool -- [9.44 secs] http://benchmarksgame.alioth.debian.org/u64q/program.php?tes…

> afaict comparing Rust program #4 [5.30 secs] to Rust program #5 [9.14 secs] is all about differences between std::collections::HashMap and that experimental hash table.

There was also a small contribution (~6%) of working on bytes rather than strings according to the original PR: https://github.com/TeXitoi/benchmarksgame-rs/pull/39

Re: New Rust hash table leads Benchmarks Game

#74

Post by igouy » Mon, Feb 27, 2017, 7:10 PM UTC

masklinn wrote: post #73

igouy wrote: post #69

Previously std::collections::HashMap was used with the default hash function -- [46.03 secs] http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... ) and then the hash function was changed to FnvHasher -- [17.10 secs] http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... and then better use of quad core with futures_cpupool -- [9.44 secs] http://benchmarksgame.alioth.debian.org/u64q/program.php?tes…

> afaict comparing Rust program #4 [5.30 secs] to Rust program #5 [9.14 secs] is all about differences between std::collections::HashMap and that experimental hash table. There was also a small contribution (~6%) of working on bytes rather than strings according to the original PR: https://github.com/TeXitoi/benchmarksgame-rs/pull/39

Please check the source code for Rust #5.

Re: New Rust hash table leads Benchmarks Game

#75

Post by mbrubeck » Mon, Feb 27, 2017, 7:14 PM UTC

kzrdude wrote: post #71

mbrubeck wrote: post #58

In other Rust/benchmarksgame news, I just submitted a simple fix to the Rust program for "reverse-complement" that makes it faster than the fastest C++ program, on my computer. The old version was spending 2/3 of its time just reading the input into memory, because it wasn't allocating a large enough buffer up front. https://github.com/TeXitoi/benchmarksgame-rs/pull/44 I'm also working on some additional changes that…

Would it be any worse to use `File::open("/dev/stdin")` there, so that it is safe code?

Oh, that's a good idea. (It's unfortunate that neither my code nor yours is portable to non-Unix platforms like Windows.)

UPDATE: Pushed a commit to my latest PR to replace the unsafe `File::from_raw_fd` with your `File::open`. Thanks!

Re: New Rust hash table leads Benchmarks Game

#76

Post by 88e282102ae2e5b » Mon, Feb 27, 2017, 7:17 PM UTC

chris_overseas wrote: post #17

It seems to me that there are a lot of apples-to-oranges comparisons here? Some implementations are using the language's standard library hashtable implementation while others are using 3rd party version (with different algorithms and data structures across all of them), some are using multiple threads while others are single threaded etc. As a result, I wouldn't read too much into the rankings you see here.

Sure, but I'm less worried about absolute rank and more interested in whether the language I'm using is on the order of C/C++/Fortran.

I can sell a 2x slowdown to my boss if I can show that that's the only cost of a significantly more elegant and productive language, but at 100x that's a much harder sell.

Re: New Rust hash table leads Benchmarks Game

#77

Post by sqeaky » Mon, Feb 27, 2017, 7:33 PM UTC

0xFFC wrote: post #51

bluejekyll wrote: post #46

Earlier quoted context omitted.

Right. The only thing C had going for it was that it was the fastest non-assembly language. I'm biased, I want all C development halted and moved over to Rust. If C is no longer the fastest , for some definition of that, then no one should be defending it at this point. Honestly, I want the LLVM optimized C version specifically so that this last argument for C in any context will be taken off the table. I'm sure ther…

I am asking this genuinely, I always thought and heard LLVM optimizer is inferior to GCC's. Am I wrong ? is there any scientific benchmark for this ?

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...

Re: New Rust hash table leads Benchmarks Game

#78

Post by sqeaky » Mon, Feb 27, 2017, 7:34 PM UTC

rurban wrote: post #62

galangalalgol wrote: post #2

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.

rust and C are only lucky that the real fast languages are not included in this benchmark comparisons. e.g. felix or pony would dominate it then, over C++ with OpenMP. Here only a missing fast C/C++ hash table is scewing the picture.

I have never heard of either of those, do you have any benchmarks?

EDIT, Nevermind Felix compiles to C++ and Pony looks like an academic project. If you want to provide benchmarks or try to change my mind, I am open to it, but it would require significant evidence.

Re: New Rust hash table leads Benchmarks Game

#79

Post by stcredzero » Mon, Feb 27, 2017, 7:42 PM UTC

Java is showing quite impressive numbers! 50% overhead over native C implementations was often cited as a good guess for the ultimate efficiency of JIT code generation back in the Self Hotspot days.

People who were trying to castigate Go early on as having "Java-like speeds" were really just showing their ignorance of the state of the art of JIT compilation for managed languages and the JVM. Such outdated folk knowledge of performance in the programming field seems to be a constant over the decades. (Programmers have had such distorted views since the mid 80's at least.) Maybe this kind of knowledge needs to be a used in job interview questions for awhile? Very soon, people will just memorize such trivia for interviews, but it would serve to squash this form of folk programming "alternative fact."

Re: New Rust hash table leads Benchmarks Game

#80

Post by matt_wulfeck » Mon, Feb 27, 2017, 7:52 PM UTC

stcredzero wrote: post #79

Java is showing quite impressive numbers! 50% overhead over native C implementations was often cited as a good guess for the ultimate efficiency of JIT code generation back in the Self Hotspot days. People who were trying to castigate Go early on as having "Java-like speeds" were really just showing their ignorance of the state of the art of JIT compilation for managed languages and the JVM. Such outdated folk knowle…

Probably because people are intelligent enough not to compare speeds inside of a vacuum. When someone denigrates a language as "java-like" they're really just comparing it anecdotally to the sum of all Java projects they've worked with. Rarely is the project a single-purpose, optimized pet-project.