17 ms·

New Rust hash table leads Benchmarks Game

198 points by joseraul 10y ago

galangalalgol 10y ago
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.
- staticassertion 10y ago
  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.
  - Sean1708 10y ago
    Is there any reason why we can't have a "C clang"? Or has just nobody bothered yet?
    - masklinn 10y ago
      Circa 2011 the maintainer of the benchmark game decided to mostly only allow one implementation of each language[0] following pypy developers trying to get program alternatives which weren't pypy-pessimal. [0] some languages get a bye for some reason e.g. MRI and JRuby, but no pypy, and which implementation is blessed is also arbitrary e.g. javascript is v8 but lua is lua.
      - bluejekyll 10y ago
        2011 didn't have as widespread Clang/LLVM usage. Now that it is so ubiquitous, probably a good time to revisit for C... C needs to defend its reputation now!
        0xFFC 10y ago
        I am saying this as someone who loved C for my entire life, when I was in college I did implement most of the assignments in C when prof said python is okay, but I did in C because I loved it and I thought I would learn more by doing them in C. So no hard feeling involved. There is no reputation to defend. You mean security problems everywhere ? do you mean old, broken, nasty build systems ? Do you mean not having single good package management ? The language (C/C++) is clearly intractable (parsing wise), it is 2017 and we don't have single good IDE for them (I don't use IDE at all, but I am sure you agree with me how much an IDE is important for newcomers) If that is the case I think writing assembly would outperform C like shit, and with that logic asm is much better than C. And to be honest, I am in job finding phase and preparing for jobs, if this wasn't my plan right now, I would abandoned C and C++ (even C++{11,14}) for Rust in heartbeat. The language (Rust) clearly is awesome language, well designed, does have perfect build system (have you seen Cargo ? it is wonderful), flexible language design (you can write OS in rust -not having runtime- and you can write web app in Rust). I am stuck with C and C++ for now, but if my opinion counts , Rust is superior in every aspect to C/C++. Even if Rust were slower a little bit (+/- 10%) I wouldn't mind. Because its ecosystem is so healthy I would trade 10% of my program performance to having something as nice as Rust.
        bluejekyll 10y ago
        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 there are some people saying, "but it's not using the same compiler backend and optimizer...", I want this to counter that. Rust all the things.
        0xFFC 10y ago
        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 ?
      - igouy 10y ago
        > alternatives which weren't pypy-pessimal Not true. Back-in-the-day Joe LaFata contributed specially written-for PyPy pi-digits, spectral-norm, mandelbrot programs and they were all shown on the website side-by-side with the CPython programs. Back-in-the-day I noticed the Python n-body program failed with PyPy, I asked about the problem and was told "we have nbody_modified in our benchmarks" and then I asked them to contribute the specially modified for PyPy program -- and it was displayed on the website within 3 hours. https://morepypy.blogspot.com/2010/03/introducing-pypy-12-release.html https://morepypy.blogspot.com/2010/03/introducing-pypy-12-re...
      - igouy 10y ago
        > javascript is v8 Kind-of: Node.js actually.
    - igouy 10y ago
      "If you're interested in something not shown on the benchmarks game website then please take the program source code and the measurement scripts and publish your own measurements." http://benchmarksgame.alioth.debian.org/play.html#languagex http://benchmarksgame.alioth.debian.org/play.html#languagex
  - galangalalgol 10y ago
    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.
- deleted 10y ago
  [deleted]
- igouy 10y ago
  "If you're interested in something not shown on the benchmarks game website then please take the program source code and the measurement scripts and publish your own measurements." http://benchmarksgame.alioth.debian.org/play.html#languagex http://benchmarksgame.alioth.debian.org/play.html#languagex
- rurban 10y ago
  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.
  - sqeaky 10y ago
    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.
deleted 10y ago
[deleted]
insulanian 10y ago
I'm not a system programmer, but it makes me very happy to see Rust taking off, with all its potential to, hopefully, replace currently most used unsafe system languages.
crb002 10y ago
LLVM IR could squeeze out some more. I should take a crack at it. Did something similar to show DuPont why Criterion rocked.
- 0xFFC 10y ago
  Citation ? To be honest I always heard LLVM is slower than GCC in most scenarios.
- crb002 10y ago
  Yeah. This is largely IO bound. Operating system read calls from STDIN dominate the runtime.
- kzrdude 10y ago
  The hash table is implemented in safe Rust (By using std's Vec). It has some inefficiencies that could maybe have been polished off using `unsafe`.
  - Manishearth 10y ago
    I had a quick look at it a while back, there aren't many (any?) inefficiencies there like that.
vegabook 10y ago
quite a decent perf from the ML family at around 19 seconds (F# and Ocaml). Top of the functionals, at least, twice as fast as Haskell. Also look how ginormous the binaries are for all the VM languages. Kinda would have thought it would be the opposite what with not needing to link in as much runtime?
- Wildgoose 10y ago
  You could even argue that Rust is a member of the ML family seeing as the ML family of languages were major inspirations and furthermore I believe the original implementation of Rust was written in OCaml.
  - Lev1a 10y ago
    Before Rust was written in Rust it was indeed written in OCaml.
  - vegabook 10y ago
    As a scientific programmer interested in functional-flavoured (ie undogmatic) languages, I would do Rust immediately if it had a REPL. Dying to dump Python. This post is very convincing on Rust's design decisions: http://science.raphael.poss.name/rust-for-functional-programmers.html http://science.raphael.poss.name/rust-for-functional-program... This post was a total revelation to me, even if I assume it's well known in the community, because it is very credible on the Sophie's Choice issue of mathematical purity versus acknowledgement of the reality of the instruction pointer-based imperative machine that exists underneath. I've looked at other languages that "do" multiprocessing recently. Go is great, but it's essentially about getting large teams of variable-skill people to work together well. It's not an inspiring language, whereas Rust clearly is. Erlang (via Elixir) is very interesting, but the actor model will never be as performant in reality as the shared memory architecture. Julia is just a modern interpretation of matlab. A number of the JVM languages are great, but the "culture" of that ecosystem will always be corporate. This is why I believe the science crowd could really gravitate to Rust, because it may have the ability, like the functional crowd, to satisfy the "search for beauty" aspect which motivates many academics, scientists, and indeed, programmers, all the while staying just the right side of pragmatism. And clearly targeting "where the puck is going" on massively multicore hardware. The trial-and-error nature of scientific/data science discovery inevitably requires a REPL. If I had the right compiler/interpreter skills I would gladly contribute to making a Rust REPL happen. Unfortunately I don't. As it stands, all I can say is that if the REPL happens, I would be axed to contribute on the Rust scientific ecosystem with great motivation and pleasure.
geodel 10y ago
It is new Rust hash table from external crate.
- kazagistar 10y ago
  The default hash table has better security against malicious input by using a slower hashing algorithm. Its the right default, but if you really want performance and to compete with C/C++, you have to use an algorithm that makes different tradeoffs, or you would be comparing apples to oranges.
  - igouy 10y ago
    > or you would be comparing apples to oranges Do the other programs use that same hash table algorithm? http://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/ http://www.sebastiansylvan.com/post/robin-hood-hashing-shoul...
  - CodesInChaos 10y ago
    > The default hash table has better security against malicious input by using a slower hashing algorithm. I think an adaptive hash that switches from fast to secure when collisions are detected would make a better default choice (at the cost of some implementation complexity). Or possibly even an implementation with log(n) worst case complexity.
  - ajross 10y ago
    Do the hash tables in use by the C/C++ entries use low-security hash functions? Seems like that needs evidence.
    - mbrubeck 10y ago
      The first-place Rust program uses this very simple low-security hash function: impl Hasher for NaiveHasher { fn write_u64(&mut self, i: u64) { self.0 = i ^ i >> 7; } } The second-place C program uses the exact same hash function as the Rust program, except it also truncates the result to 32 bits: #define CUSTOM_HASH_FUNCTION(key) (khint32_t)((key) ^ (key)>>7) The third-place C++ program uses the identity function as its hash function: struct hash{ uint64_t operator()(const T& t)const{ return t.data; } }; Sources: - Rust: http://benchmarksgame.alioth.debian.org/u64q/program.php?test=knucleotide&lang=rust&id=4 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... - C: http://benchmarksgame.alioth.debian.org/u64q/program.php?test=knucleotide&lang=gcc&id=1 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... - C++: http://benchmarksgame.alioth.debian.org/u64q/program.php?test=knucleotide&lang=gpp&id=3 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes...
santaclaus 10y ago
Cool! Is Rust's hash table open addressed?
- sanxiyn 10y ago
  Yes. It's open addressing, linear probing, Robin Hood hashing. https://doc.rust-lang.org/std/collections/struct.HashMap.html https://doc.rust-lang.org/std/collections/struct.HashMap.htm...
  - masklinn 10y ago
    The program which reached the top of k-n does not use the standard library's hashmap, it uses ordermap: https://github.com/bluss/ordermap https://github.com/bluss/ordermap Though that's also an open addressed map.
gigatexal 10y ago
The rust version is using multiple cpus using a pool concept (which looks a lot like the multiprocessing module from python so kudos there). But the C version is single threaded from what I can tell. So rust is safe but threaded to be faster than single threaded C which isn't that much slower. Hmm...
- scotty79 10y ago
  Isn't the whole point of Rust to do threaded things safely by keeping strict tabs on who owns what and for how long?
- Etzos 10y ago
  From what I can see the C version is using OpenMP and uses all of the available CPU cores.
  - gigatexal 10y ago
    Yeah I see that now. Missed that; my mistake.
  - gigatexal 10y ago
    Is the C version optimized? Could you conclude that parallelism in rust is faster/ better than C + openMP in this case considering rust is to replace C++ and is safe at least in this submission?
- infogulch 10y ago
  That's not true. If you look at the comparisons, the cpu time taken by C is actually more than rust, and the cpu load looks about even. Note the C version uses: #pragma omp parallel sections
  - gens 10y ago
    >.. and the cpu load looks about even. 318% is 20% bigger then 265%.
chris_overseas 10y ago
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.
- IshKebab 10y ago
  That's why they call it a game.
  - igouy 10y ago
    http://benchmarksgame.alioth.debian.org/sometimes-people-just-make-up-stuff.html#name-game http://benchmarksgame.alioth.debian.org/sometimes-people-jus...
    - IshKebab 10y ago
      Huh, I could have sworn at the time that that was the reason but C2 backs it up: http://wiki.c2.com/?GreatComputerLanguageShootout http://wiki.c2.com/?GreatComputerLanguageShootout Maybe they should remove 'game' from the title if they need an FAQ for it. Or even better they should acknowledge that it is a game.
      - igouy 10y ago
        The word game has several different meanings -- not all of them are dismissive.
- spoiler 10y ago
  > It seems to me that there are a lot of apples-to-oranges comparisons here? So, the usual. :) I stopped taking into account the benchmarks game completely after I saw apples-to-potatoes comparisons a few years back.
richard_todd 10y ago
Just FYI in case it happens to others: I was confused because the page I get shows Rust coming in fourth. I had to reload it/re-sort the columns a couple times to see the new Rust #4 entry.
jeffdavis 10y ago
Does this have anything to do with: https://news.ycombinator.com/item?id=13742865 https://news.ycombinator.com/item?id=13742865 ?
- masklinn 10y ago
  No. The Rust program uses https://github.com/bluss/ordermap https://github.com/bluss/ordermap which is an implementation/variant[0] of Hettinger's naturally ordered hash map.
makmanalp 10y ago
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; } }
- kzrdude 10y ago
  Looks like it only handles u64's being hashed and panics on all other input. That must be because it is known it will be used exactly with `.write_u64`. Not having to implement the general byte buffer hashing is a big benefit, removes the whole partial state tracking of the hasher, which the compiler probably would not optimize out (we don't know until we try though).
- tveita 10y ago
  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.
- msbarnett 10y ago
  It's the Rust equivalent of the CUSTOM_HASH_FUNCTION macro in the C source. The comment from there might help explain things: // Define a custom hash function to use instead of khash's default hash // function. This custom hash function uses a simpler bit shift and XOR which // results in several percent faster performance compared to when khash's // default hash function is used. #define CUSTOM_HASH_FUNCTION(key) (khint32_t)((key) ^ (key)>>7)
mbrubeck 10y ago
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 https://github.com/TeXitoi/benchmarksgame-rs/pull/44 I'm also working on some additional changes that make it even faster than the C version (again, on my computer) by improving how it divides work across CPUs: https://github.com/TeXitoi/benchmarksgame-rs/pull/46 https://github.com/TeXitoi/benchmarksgame-rs/pull/46 These improved Rust programs have not yet been added to the benchmarksgame site. Previous entries are ranked at: http://benchmarksgame.alioth.debian.org/u64q/performance.php?test=revcomp http://benchmarksgame.alioth.debian.org/u64q/performance.php... Minor improvements to the Rust programs for "mandelbrot" and "binary-trees" are also awaiting review!
- kzrdude 10y ago
  Would it be any worse to use `File::open("/dev/stdin")` there, so that it is safe code?
  - mbrubeck 10y ago
    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!
- acqq 10y ago
  Thanks! I like Rust for what it does in advancing the state of the art of the languages, but I also like how this example demonstrates how hard it is to avoid "unsafe" constructs and remain competitive. https://github.com/TeXitoi/benchmarksgame-rs/blob/master/src/reverse_complement.rs https://github.com/TeXitoi/benchmarksgame-rs/blob/master/src...
  - mbrubeck 10y ago
    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_complement_bytes/src/reverse_complement.rs 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 usually only helpful to get a few extra percent speedup in an inner loop. If this were production code rather than the benchmarks game, I'd probably ship the safe version.
igouy 10y ago
Previously std::collections::HashMap was used with the default hash function -- [46.03 secs] http://benchmarksgame.alioth.debian.org/u64q/program.php?test=knucleotide&lang=rust&id=1 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?test=knucleotide&lang=rust&id=2 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?test=knucleotide&lang=rust&id=3 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... and now use of std::collections::HashMap has been replaced with an experimental hash table inspired by Python 3.6's new dict implementation -- [5.30 secs] http://benchmarksgame.alioth.debian.org/u64q/program.php?test=knucleotide&lang=rust&id=4 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... afaict comparing #4 to #5 is all about differences between that experimental hash table and std::collections::HashMap -- [9.14 secs] http://benchmarksgame.alioth.debian.org/u64q/program.php?test=knucleotide&lang=rust&id=5 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes...
- masklinn 10y ago
  > 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 https://github.com/TeXitoi/benchmarksgame-rs/pull/39
  - igouy 10y ago
    Please check the source code for Rust #5.
- gpm 10y ago
  > experimental hash table When discussing whether or not to use this at least someone mentioned that there company was using it in production. I don't think it really counts as experimental.
stcredzero 10y ago
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."
- matt_wulfeck 10y ago
  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.
  - stcredzero 10y ago
    Smalltalk was long castigated for being a "slow, poky interpreted language" long, long after it stopped being that in fact. In all of my time as a consultant for the language vendor, never did I ever come across the VM actually being too slow. In something like 90% of the cases, it was due to IO. Before I left the Smalltalk part of my career behind, someone had the occasion to compare the parser-compiler of one Smalltalk which was implemented in C with Yacc/Lex with one implemented in pure Smalltalk with a JIT VM. IT turns out, once the console logging was disabled, the JIT VM's parser was just as fast as the one in C. In my experience of almost 2 decades, it has been a constant that uninformed programmers are especially uninformed about the relative performance of managed languages.
    - igouy 10y ago
      If only someone was interested in contributing Smalltalk programs written with MatriX to use quad-core -- http://benchmarksgame.alioth.debian.org/u64q/smalltalk.html http://benchmarksgame.alioth.debian.org/u64q/smalltalk.html
kcdev 10y ago
I'm really curious what this benchmark would be for JavaScript V8? Anyone have the time to recreate the same functionality to test in Node?
- steveklabnik 10y ago
  There are two "Node.js" entries on this page.
saurik 10y ago
> Some language implementations have hash tables built-in; some provide a hash table as part of a collections library; some use a third-party hash table library. (For example, use either khash or CK_HT for C language k-nucleotide programs.) The hash table algorithm implemented is likely to be different in different libraries. > Please don't implement your own custom "hash table" - it will not be accepted. > The work is to use the built-in or library hash table implementation to accumulate count values - lookup the count for a key and update the count in the hash table. The C++ implementation is thereby testing an old version of a non-standard extension of libstdc++ that I had never heard of and which was likely contributed once by IBM and never really looked at again (by either maintainers or users ;P), while the C implementation is testing the specified khash library, which is apparently something a number of people actively contribute to and attempt to optimize, giving it some notoriety. If I were to do this in C++, and I wasn't allowed to use my hash table, I would almost certainly not be using __gnu_pbds::cc_hash_table<>. If I were to just want to use something "included", I would use the C++11 std::unordered_map<> (note that this code is compiled already as C++11). But we all know the STL is designed for flexibility and predictability, not performance, and the culture of C++ is "that's OK, as if you actually care about performance no off-the-shelf data structure is going to be correct". If I decided I wanted speed, I know I'd want to check out Folly, and I might even end up using khash. Reading other comments, what happened here is the Rust version is now using some "experimental" hash table based on ongoing work to optimize the Python 3000 dict implementation. This is just not a useful benchmark. What we are benchmarking is "how maintained is the implementation's built in hash table and is it tunable for this particular workload". That's why you should not be surprised to see Java doing so well: the code actually being written here is just some glue... your programming language has to be incompetent to do poorly at this benchmark (especially as many commenters here are using a "within a power of 2" rule of thumb). There are even multiple listings for the Java one, and the one that is faster is using it.unimi.dsi.fastutil.longs.Long2IntOpenHashMap?!? What we really should be asking here is: why is any language doing "poorly" in this benchmark? It just isn't surprising that Rust is competitive with C/C++, nor is it surprising that Java is also; what is surprising is that Swift, Go, Haskell, and C# are not, and so I bet the issue is something (such as "is allocating memory for a thing which is not required") that can be trivially fixed for each (though by the rules of engagement, it might... or might not :/ as Java "cheated", right? ;P... require a minor fix upstream). I mean, since the "work" explicitly is not "write a hash table using nothing but primitives from this language", there is no particular reason why Perl and Python (which is using a non-destructive array .replace, which is likely brutal... again: I bet this is almost always a benchmark of ancillary memory allocations) should be doing as poorly as they are: if we all made "optimize for this benchmark" a top priority for a weekend hackathon, I bet we could get every open source language to nail this under 25s. But do we care?
snakeanus 10y ago
Does anybody know what happened to the image charts like this one for example? https://web.archive.org/web/20121218042116/http://shootout.alioth.debian.org/u64/ats.php https://web.archive.org/web/20121218042116/http://shootout.a... This was my favourite feature of the benchmarks game.
- igouy 10y ago
  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 …

198 points by joseraul 10y ago

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.

staticassertion 10y ago
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.
- Sean1708 10y ago
  Is there any reason why we can't have a "C clang"? Or has just nobody bothered yet?
  - masklinn 10y ago
    Circa 2011 the maintainer of the benchmark game decided to mostly only allow one implementation of each language[0] following pypy developers trying to get program alternatives which weren't pypy-pessimal. [0] some languages get a bye for some reason e.g. MRI and JRuby, but no pypy, and which implementation is blessed is also arbitrary e.g. javascript is v8 but lua is lua.
    - bluejekyll 10y ago
      2011 didn't have as widespread Clang/LLVM usage. Now that it is so ubiquitous, probably a good time to revisit for C... C needs to defend its reputation now!
      - 0xFFC 10y ago
        I am saying this as someone who loved C for my entire life, when I was in college I did implement most of the assignments in C when prof said python is okay, but I did in C because I loved it and I thought I would learn more by doing them in C. So no hard feeling involved. There is no reputation to defend. You mean security problems everywhere ? do you mean old, broken, nasty build systems ? Do you mean not having single good package management ? The language (C/C++) is clearly intractable (parsing wise), it is 2017 and we don't have single good IDE for them (I don't use IDE at all, but I am sure you agree with me how much an IDE is important for newcomers) If that is the case I think writing assembly would outperform C like shit, and with that logic asm is much better than C. And to be honest, I am in job finding phase and preparing for jobs, if this wasn't my plan right now, I would abandoned C and C++ (even C++{11,14}) for Rust in heartbeat. The language (Rust) clearly is awesome language, well designed, does have perfect build system (have you seen Cargo ? it is wonderful), flexible language design (you can write OS in rust -not having runtime- and you can write web app in Rust). I am stuck with C and C++ for now, but if my opinion counts , Rust is superior in every aspect to C/C++. Even if Rust were slower a little bit (+/- 10%) I wouldn't mind. Because its ecosystem is so healthy I would trade 10% of my program performance to having something as nice as Rust.
        bluejekyll 10y ago
        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 there are some people saying, "but it's not using the same compiler backend and optimizer...", I want this to counter that. Rust all the things.
        0xFFC 10y ago
        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 ?
    - igouy 10y ago
      > alternatives which weren't pypy-pessimal Not true. Back-in-the-day Joe LaFata contributed specially written-for PyPy pi-digits, spectral-norm, mandelbrot programs and they were all shown on the website side-by-side with the CPython programs. Back-in-the-day I noticed the Python n-body program failed with PyPy, I asked about the problem and was told "we have nbody_modified in our benchmarks" and then I asked them to contribute the specially modified for PyPy program -- and it was displayed on the website within 3 hours. https://morepypy.blogspot.com/2010/03/introducing-pypy-12-release.html https://morepypy.blogspot.com/2010/03/introducing-pypy-12-re...
    - igouy 10y ago
      > javascript is v8 Kind-of: Node.js actually.
  - igouy 10y ago
    "If you're interested in something not shown on the benchmarks game website then please take the program source code and the measurement scripts and publish your own measurements." http://benchmarksgame.alioth.debian.org/play.html#languagex http://benchmarksgame.alioth.debian.org/play.html#languagex
- galangalalgol 10y ago
  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.
deleted 10y ago
[deleted]
igouy 10y ago
"If you're interested in something not shown on the benchmarks game website then please take the program source code and the measurement scripts and publish your own measurements." http://benchmarksgame.alioth.debian.org/play.html#languagex http://benchmarksgame.alioth.debian.org/play.html#languagex
rurban 10y ago
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.
- sqeaky 10y ago
  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.

deleted 10y ago

[deleted]

insulanian 10y ago

I'm not a system programmer, but it makes me very happy to see Rust taking off, with all its potential to, hopefully, replace currently most used unsafe system languages.

crb002 10y ago

LLVM IR could squeeze out some more. I should take a crack at it. Did something similar to show DuPont why Criterion rocked.

0xFFC 10y ago
Citation ? To be honest I always heard LLVM is slower than GCC in most scenarios.
crb002 10y ago
Yeah. This is largely IO bound. Operating system read calls from STDIN dominate the runtime.
kzrdude 10y ago
The hash table is implemented in safe Rust (By using std's Vec). It has some inefficiencies that could maybe have been polished off using `unsafe`.
- Manishearth 10y ago
  I had a quick look at it a while back, there aren't many (any?) inefficiencies there like that.

vegabook 10y ago

quite a decent perf from the ML family at around 19 seconds (F# and Ocaml). Top of the functionals, at least, twice as fast as Haskell. Also look how ginormous the binaries are for all the VM languages. Kinda would have thought it would be the opposite what with not needing to link in as much runtime?

Wildgoose 10y ago
You could even argue that Rust is a member of the ML family seeing as the ML family of languages were major inspirations and furthermore I believe the original implementation of Rust was written in OCaml.
- Lev1a 10y ago
  Before Rust was written in Rust it was indeed written in OCaml.
- vegabook 10y ago
  As a scientific programmer interested in functional-flavoured (ie undogmatic) languages, I would do Rust immediately if it had a REPL. Dying to dump Python. This post is very convincing on Rust's design decisions: http://science.raphael.poss.name/rust-for-functional-programmers.html http://science.raphael.poss.name/rust-for-functional-program... This post was a total revelation to me, even if I assume it's well known in the community, because it is very credible on the Sophie's Choice issue of mathematical purity versus acknowledgement of the reality of the instruction pointer-based imperative machine that exists underneath. I've looked at other languages that "do" multiprocessing recently. Go is great, but it's essentially about getting large teams of variable-skill people to work together well. It's not an inspiring language, whereas Rust clearly is. Erlang (via Elixir) is very interesting, but the actor model will never be as performant in reality as the shared memory architecture. Julia is just a modern interpretation of matlab. A number of the JVM languages are great, but the "culture" of that ecosystem will always be corporate. This is why I believe the science crowd could really gravitate to Rust, because it may have the ability, like the functional crowd, to satisfy the "search for beauty" aspect which motivates many academics, scientists, and indeed, programmers, all the while staying just the right side of pragmatism. And clearly targeting "where the puck is going" on massively multicore hardware. The trial-and-error nature of scientific/data science discovery inevitably requires a REPL. If I had the right compiler/interpreter skills I would gladly contribute to making a Rust REPL happen. Unfortunately I don't. As it stands, all I can say is that if the REPL happens, I would be axed to contribute on the Rust scientific ecosystem with great motivation and pleasure.

geodel 10y ago

It is new Rust hash table from external crate.

kazagistar 10y ago
The default hash table has better security against malicious input by using a slower hashing algorithm. Its the right default, but if you really want performance and to compete with C/C++, you have to use an algorithm that makes different tradeoffs, or you would be comparing apples to oranges.
- igouy 10y ago
  > or you would be comparing apples to oranges Do the other programs use that same hash table algorithm? http://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/ http://www.sebastiansylvan.com/post/robin-hood-hashing-shoul...
- CodesInChaos 10y ago
  > The default hash table has better security against malicious input by using a slower hashing algorithm. I think an adaptive hash that switches from fast to secure when collisions are detected would make a better default choice (at the cost of some implementation complexity). Or possibly even an implementation with log(n) worst case complexity.
- ajross 10y ago
  Do the hash tables in use by the C/C++ entries use low-security hash functions? Seems like that needs evidence.
  - mbrubeck 10y ago
    The first-place Rust program uses this very simple low-security hash function: impl Hasher for NaiveHasher { fn write_u64(&mut self, i: u64) { self.0 = i ^ i >> 7; } } The second-place C program uses the exact same hash function as the Rust program, except it also truncates the result to 32 bits: #define CUSTOM_HASH_FUNCTION(key) (khint32_t)((key) ^ (key)>>7) The third-place C++ program uses the identity function as its hash function: struct hash{ uint64_t operator()(const T& t)const{ return t.data; } }; Sources: - Rust: http://benchmarksgame.alioth.debian.org/u64q/program.php?test=knucleotide&lang=rust&id=4 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... - C: http://benchmarksgame.alioth.debian.org/u64q/program.php?test=knucleotide&lang=gcc&id=1 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... - C++: http://benchmarksgame.alioth.debian.org/u64q/program.php?test=knucleotide&lang=gpp&id=3 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes...

santaclaus 10y ago

Cool! Is Rust's hash table open addressed?

sanxiyn 10y ago
Yes. It's open addressing, linear probing, Robin Hood hashing. https://doc.rust-lang.org/std/collections/struct.HashMap.html https://doc.rust-lang.org/std/collections/struct.HashMap.htm...
- masklinn 10y ago
  The program which reached the top of k-n does not use the standard library's hashmap, it uses ordermap: https://github.com/bluss/ordermap https://github.com/bluss/ordermap Though that's also an open addressed map.

gigatexal 10y ago

The rust version is using multiple cpus using a pool concept (which looks a lot like the multiprocessing module from python so kudos there). But the C version is single threaded from what I can tell. So rust is safe but threaded to be faster than single threaded C which isn't that much slower. Hmm...

scotty79 10y ago
Isn't the whole point of Rust to do threaded things safely by keeping strict tabs on who owns what and for how long?
Etzos 10y ago
From what I can see the C version is using OpenMP and uses all of the available CPU cores.
- gigatexal 10y ago
  Yeah I see that now. Missed that; my mistake.
- gigatexal 10y ago
  Is the C version optimized? Could you conclude that parallelism in rust is faster/ better than C + openMP in this case considering rust is to replace C++ and is safe at least in this submission?
infogulch 10y ago
That's not true. If you look at the comparisons, the cpu time taken by C is actually more than rust, and the cpu load looks about even. Note the C version uses: #pragma omp parallel sections
- gens 10y ago
  >.. and the cpu load looks about even. 318% is 20% bigger then 265%.

chris_overseas 10y ago

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.

IshKebab 10y ago
That's why they call it a game.
- igouy 10y ago
  http://benchmarksgame.alioth.debian.org/sometimes-people-just-make-up-stuff.html#name-game http://benchmarksgame.alioth.debian.org/sometimes-people-jus...
  - IshKebab 10y ago
    Huh, I could have sworn at the time that that was the reason but C2 backs it up: http://wiki.c2.com/?GreatComputerLanguageShootout http://wiki.c2.com/?GreatComputerLanguageShootout Maybe they should remove 'game' from the title if they need an FAQ for it. Or even better they should acknowledge that it is a game.
    - igouy 10y ago
      The word game has several different meanings -- not all of them are dismissive.
spoiler 10y ago
> It seems to me that there are a lot of apples-to-oranges comparisons here? So, the usual. :) I stopped taking into account the benchmarks game completely after I saw apples-to-potatoes comparisons a few years back.

richard_todd 10y ago

Just FYI in case it happens to others: I was confused because the page I get shows Rust coming in fourth. I had to reload it/re-sort the columns a couple times to see the new Rust #4 entry.

jeffdavis 10y ago

Does this have anything to do with: https://news.ycombinator.com/item?id=13742865 https://news.ycombinator.com/item?id=13742865 ?

masklinn 10y ago
No. The Rust program uses https://github.com/bluss/ordermap https://github.com/bluss/ordermap which is an implementation/variant[0] of Hettinger's naturally ordered hash map.

makmanalp 10y ago

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; } }

kzrdude 10y ago
Looks like it only handles u64's being hashed and panics on all other input. That must be because it is known it will be used exactly with `.write_u64`. Not having to implement the general byte buffer hashing is a big benefit, removes the whole partial state tracking of the hasher, which the compiler probably would not optimize out (we don't know until we try though).
tveita 10y ago
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.
msbarnett 10y ago
It's the Rust equivalent of the CUSTOM_HASH_FUNCTION macro in the C source. The comment from there might help explain things: // Define a custom hash function to use instead of khash's default hash // function. This custom hash function uses a simpler bit shift and XOR which // results in several percent faster performance compared to when khash's // default hash function is used. #define CUSTOM_HASH_FUNCTION(key) (khint32_t)((key) ^ (key)>>7)

mbrubeck 10y ago

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 https://github.com/TeXitoi/benchmarksgame-rs/pull/44 I'm also working on some additional changes that make it even faster than the C version (again, on my computer) by improving how it divides work across CPUs: https://github.com/TeXitoi/benchmarksgame-rs/pull/46 https://github.com/TeXitoi/benchmarksgame-rs/pull/46 These improved Rust programs have not yet been added to the benchmarksgame site. Previous entries are ranked at: http://benchmarksgame.alioth.debian.org/u64q/performance.php?test=revcomp http://benchmarksgame.alioth.debian.org/u64q/performance.php... Minor improvements to the Rust programs for "mandelbrot" and "binary-trees" are also awaiting review!

kzrdude 10y ago
Would it be any worse to use `File::open("/dev/stdin")` there, so that it is safe code?
- mbrubeck 10y ago
  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!
acqq 10y ago
Thanks! I like Rust for what it does in advancing the state of the art of the languages, but I also like how this example demonstrates how hard it is to avoid "unsafe" constructs and remain competitive. https://github.com/TeXitoi/benchmarksgame-rs/blob/master/src/reverse_complement.rs https://github.com/TeXitoi/benchmarksgame-rs/blob/master/src...
- mbrubeck 10y ago
  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_complement_bytes/src/reverse_complement.rs 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 usually only helpful to get a few extra percent speedup in an inner loop. If this were production code rather than the benchmarks game, I'd probably ship the safe version.

igouy 10y ago

Previously std::collections::HashMap was used with the default hash function -- [46.03 secs] http://benchmarksgame.alioth.debian.org/u64q/program.php?test=knucleotide&lang=rust&id=1 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?test=knucleotide&lang=rust&id=2 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?test=knucleotide&lang=rust&id=3 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... and now use of std::collections::HashMap has been replaced with an experimental hash table inspired by Python 3.6's new dict implementation -- [5.30 secs] http://benchmarksgame.alioth.debian.org/u64q/program.php?test=knucleotide&lang=rust&id=4 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... afaict comparing #4 to #5 is all about differences between that experimental hash table and std::collections::HashMap -- [9.14 secs] http://benchmarksgame.alioth.debian.org/u64q/program.php?test=knucleotide&lang=rust&id=5 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes...

masklinn 10y ago
> 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 https://github.com/TeXitoi/benchmarksgame-rs/pull/39
- igouy 10y ago
  Please check the source code for Rust #5.
gpm 10y ago
> experimental hash table When discussing whether or not to use this at least someone mentioned that there company was using it in production. I don't think it really counts as experimental.

stcredzero 10y ago

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

matt_wulfeck 10y ago
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.
- stcredzero 10y ago
  Smalltalk was long castigated for being a "slow, poky interpreted language" long, long after it stopped being that in fact. In all of my time as a consultant for the language vendor, never did I ever come across the VM actually being too slow. In something like 90% of the cases, it was due to IO. Before I left the Smalltalk part of my career behind, someone had the occasion to compare the parser-compiler of one Smalltalk which was implemented in C with Yacc/Lex with one implemented in pure Smalltalk with a JIT VM. IT turns out, once the console logging was disabled, the JIT VM's parser was just as fast as the one in C. In my experience of almost 2 decades, it has been a constant that uninformed programmers are especially uninformed about the relative performance of managed languages.
  - igouy 10y ago
    If only someone was interested in contributing Smalltalk programs written with MatriX to use quad-core -- http://benchmarksgame.alioth.debian.org/u64q/smalltalk.html http://benchmarksgame.alioth.debian.org/u64q/smalltalk.html

kcdev 10y ago

I'm really curious what this benchmark would be for JavaScript V8? Anyone have the time to recreate the same functionality to test in Node?

steveklabnik 10y ago
There are two "Node.js" entries on this page.

saurik 10y ago

> Some language implementations have hash tables built-in; some provide a hash table as part of a collections library; some use a third-party hash table library. (For example, use either khash or CK_HT for C language k-nucleotide programs.) The hash table algorithm implemented is likely to be different in different libraries. > Please don't implement your own custom "hash table" - it will not be accepted. > The work is to use the built-in or library hash table implementation to accumulate count values - lookup the count for a key and update the count in the hash table. The C++ implementation is thereby testing an old version of a non-standard extension of libstdc++ that I had never heard of and which was likely contributed once by IBM and never really looked at again (by either maintainers or users ;P), while the C implementation is testing the specified khash library, which is apparently something a number of people actively contribute to and attempt to optimize, giving it some notoriety. If I were to do this in C++, and I wasn't allowed to use my hash table, I would almost certainly not be using __gnu_pbds::cc_hash_table<>. If I were to just want to use something "included", I would use the C++11 std::unordered_map<> (note that this code is compiled already as C++11). But we all know the STL is designed for flexibility and predictability, not performance, and the culture of C++ is "that's OK, as if you actually care about performance no off-the-shelf data structure is going to be correct". If I decided I wanted speed, I know I'd want to check out Folly, and I might even end up using khash. Reading other comments, what happened here is the Rust version is now using some "experimental" hash table based on ongoing work to optimize the Python 3000 dict implementation. This is just not a useful benchmark. What we are benchmarking is "how maintained is the implementation's built in hash table and is it tunable for this particular workload". That's why you should not be surprised to see Java doing so well: the code actually being written here is just some glue... your programming language has to be incompetent to do poorly at this benchmark (especially as many commenters here are using a "within a power of 2" rule of thumb). There are even multiple listings for the Java one, and the one that is faster is using it.unimi.dsi.fastutil.longs.Long2IntOpenHashMap?!? What we really should be asking here is: why is any language doing "poorly" in this benchmark? It just isn't surprising that Rust is competitive with C/C++, nor is it surprising that Java is also; what is surprising is that Swift, Go, Haskell, and C# are not, and so I bet the issue is something (such as "is allocating memory for a thing which is not required") that can be trivially fixed for each (though by the rules of engagement, it might... or might not :/ as Java "cheated", right? ;P... require a minor fix upstream). I mean, since the "work" explicitly is not "write a hash table using nothing but primitives from this language", there is no particular reason why Perl and Python (which is using a non-destructive array .replace, which is likely brutal... again: I bet this is almost always a benchmark of ancillary memory allocations) should be doing as poorly as they are: if we all made "optimize for this benchmark" a top priority for a weekend hackathon, I bet we could get every open source language to nail this under 25s. But do we care?

snakeanus 10y ago

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

igouy 10y ago
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 …