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.
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:
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.
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:
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.
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).
> Is burntsushi's Rust implementation of memchr notably slower than libc's?
Not as far as I know. A lot of this benchmarksgame code has evolved slowly over time and hasn't been cleaned up yet to use "modern" crates and language features.
> 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.
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.
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."
HotSpot has had great speeds for numeric computation at least since 2005. I was doing financial software in Java in my first job out of college, our CTO was an ex-Sun architect who literally wrote the book on Java, and the speeds we got on numerical computations were basically equivalent to C.
The part where Java really falls down is in memory use & management, which you can see on the binary-tree & mandelbrot benchmarks, where it's roughly 4x slower than C. There are inherent penalties to pointer chasing that you can't get around. While HotSpot is often (amazingly) smart enough to inline & stack-allocate small private structs, typical Java coding style relies on complex object graphs. In C++ or Rust these would all have well-defined object ownership and be contained within a single block of memory, so access is just "add a constant to this pointer, and load". In Java, you often need to trace a graph of pointers 4-5 levels deep, each of which may cause a cache miss.
Rule of thumb while I was at Google was to figure on real-world Java being about 2-3x slower than real-world C++.
> The part where Java really falls down is in memory use & management, which you can see on the binary-tree & mandelbrot benchmarks, where it's roughly 4x slower than C.
binary-tree is not useful for comparing GCed and non-GCed languages. For non-GCed languages, you are allowed to use a memory pool of your choice (the C version uses the Apache Portable Runtime library), for GCed languages you are required to use the standard GC with the default settings (no adjustment of GC parameters permitted). This is apples and oranges.
For mandelbrot, the C version uses handcoded SIMD intrinsics. I.e. it's not even portable to non-x86 processors.
> For non-GCed languages, you are allowed to use a memory pool of your choice (the C version uses the Apache Portable Runtime library), for GCed languages you are required to use the standard GC with the default settings (no adjustment of GC parameters permitted). This is apples and oranges.
Doesn't that match with how a library would be used in the real world? A c library can create it's own memory pool but a GC one has to live with however it's host is configured.
If I were to run a performance-critical application, I'd definitely tune the GC accordingly. It's why the JVM offers several garbage collectors in the first place, for example.
Also, GCed languages aren't prevented from using memory pools, but often they are not part of their common libraries, because there's less need for them.
> If I were to run a performance-critical application, I'd definitely tune the GC accordingly.
But you have to tune it for the performance of the whole application (AFAIK), you can't tune it for an individual algorithm like you can with c. It's a one size fits all approach.
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.
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.
Note that in many of the other benchmarks, the fastest Java program takes 2x to 4x longer than the fastest C program. Still not bad! But knucleotide shows Java in a better light than most:
There are lots of folk programming like the impact of bounds checking or that all game consoles except for XBox use OpenGL.
Also many younger developers believe that C was always fast, and are unaware that early 8 and 16 bit compilers for home computers were like managed languages. The compilers generated way worse code than hobby Assembly developers.
> early 8 and 16 bit compilers for home computers were like managed languages
Yeah, I wrote several published games entirely in assembly back when that was really the only reasonable option.
Of course some of the things we had to deal with meant that even the compilers were good, they couldn't have been good enough.
Extreme limited memory is the obvious one, but pages that need to be swapped out at runtime is the other one. An example: The Game Boy had 64k of memory addressing, but would ship with 128k and larger cartridges. 32k of the memory space was reserved for video memory, RAM, and hardware registers (if I remember correctly). The first 16k of memory was always mapped to the first 16k of ROM, but the second 16k of memory was mapped to arbitrary 16k blocks of ROM. 16k wasn't enough space to hold your entire game, so some code would leak into other pages (hopefully not more than ONE other page), but you also had to be able to swap other ROM pages into that second 16k memory region to, e.g., load graphics and game data.
There isn't a compiler around even today that can juggle all of that automatically. At a minimum you'd need to be marking different functions as belonging to different memory regions, but you'd still have to manually keep track of which function was where and ensure you don't try to call a region-2 function from a region-1 function when region-2 is some arbitrary ROM page instead of the extra code page. But often something in region-2 needs to call region-1 to load graphics into sprite registers and then restore region-2 so that the stack frame becomes valid again. :)
And 32k is SUCH a small amount of memory that being able to chip away at every single function was important. You have a function that does two things, but sometimes you just need to do the second? Put a label halfway through and call directly into the middle. You can save a byte here by loading one register into another, because you know that the registers will have the right values? Or you can save another byte there because you've realized that a particular constant is loaded a lot, and you can store that constant into one of the 128 cheap-memory locations? Do it! We need every byte...
Yes it would be possible to write such a compiler, but the level of effort to customize it to the specific architecture would be extreme. Easier to just make programmers do the hard work.
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, but that doesn't make the results overall any less impressive, especially knowing what it was like before those 20+ years of effort.
I don't see a reason that both Rust and Java's results can't be impressive in their own right. Java's numbers are (for the most part) impressive compared to C and Rust's numbers are also impressive compared to C, just in a different way.
>> 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.
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.
Just be careful to remember that good performance on microbenchmarks does not necessarily translate to good performance on large applications. Some factors to consider are:
1. Cache performance and locality may differ considerably for large applications. For example, a microbenchmark may perform well because it can monopolize the L1 cache in a way that is not possible for larger applications.
It's still useful as a potential filter. If someone's implemented your microbenchmark in langB and it's within 2x of langA, then maybe they're worth comparing. If on the other hand langB is 20x away from langA in microbenchmarks, you can be pretty sure that it won't ever be a good replacement.
As long as you have people of roughly equivalent skill level within their language implementing the microbenchmarks. It's not that hard to get a 10x or even 100x speed improvement in the same language when an expert rewrites the naive code that a newbie wrote.
That's why microbenchmarks that have been on the internet for a while are quite nice: there's a good chance at least some experts from each language will have had a go and submitted a decent implementation.
In my experience, if you're seeing a 20x difference, we're either already talking compilers vs. interpreters or fundamentally different implementations (e.g. one using SIMD intrinsics vs. one not using them).
And some languages are allowed to use FFI to make their impl faster. There's some rule about this that I don't understand, but oh well. It's all for fun, not serious.
But come on, now Rust can legitimately be called "faster than C" ;)
At least until the Clang C version is added... or maybe it will still be faster.
>And some languages are allowed to use FFI to make their impl faster. There's some rule about this that I don't understand, but oh well. It's all for fun, not serious.
Actually it's pretty easy: if you can write a faster version in any language, given whatever is there in the language, even if it's c implemented standard library stuff, do it.
The implementations are not meant to be final -- people can contribute faster ones.
I suspect all languages without exception use some standard library functionality in at least a few of those sample programs, and most "standard" libraries aren't constrained to be self-hosting - so all of em use some native code, probably written in C or C++. I suspect that's true of rust too.
FFI is a fact of life. I can imagine it would be perverting the intent of the game if you explicitly used FFI to delegate the actual core of the benchmark program to C as opposed to using "standard" building blocks, but the distinciton is necessarily vague.
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.
"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."
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.
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.
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.
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.
"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."
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.
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.
> 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?
The thesis of my comment was that we should be surprised that any language does poorly on this benchmark, particularly ones that have similar kinds of targeting, and that if we cared about this benchmark (and I claim we don't), we should all pitch in, possibly upstream to fix various languages and their standard libraries to nail this benchmark. However, I also believe the rules of this benchmark are awkward and even flawed, and that it isn't clear to me that it is worth anyone's time to do that.
I am not lamenting that someone should spend more time on this: I am lamenting that tons of people seem to care about it at all, it is not a "microbenchmark" (as some are calling it), and I think the main lesson we can learn from it is "there is something subtely wrong, either with the implementation that was contributed for this benchmark, the language's runtime, or it's standard library", as given these rules we really should expect every language to be similarly in performance.
And so, if we all cared about this benchmark, I bet we could figure out what is going on and get every open source language down under 25s. Past that point, I think the rules are such that this isn't even a fun game much less a useful metric of anything worth measuring, and you are probably wasting your time contributing. I guess, to make this subthread go somewhere: why do you disagree?
Whatever the motivation for your comments, they did remind me that I'd intended to have background information URLs on other pages (not just the home page).
Oh, I absolutely understand why it is interesting and fast: what I don't understand is how it satisfies the rules, as it is effectively "some random project with a hashtable". Is this particular one so famous that it should be allowed instead of java.util.HashMap? Can I just publish my C++ hashtable and then rely on it, in which case the rule makes no sense? That's why I tack on "?!".
This entire subthread is clearly a digression ;p, but why do you say that? The rules were about using a built-in or standard collection: this Java implementation does not use HashMap and instead uses a random project with a better data structure for this use case. This is a loophole to bypass the restriction on writing your own hashtable: you just have to publish it first? ;P
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.
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.
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).
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)
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.
> 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.
It's in native Rust though. Which is all that matters. And it's a publicly available crate, so anyone who wants to use it can... and easily with cargo/crates.io.
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?
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.
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:
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.
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...
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:
And 5.30s is about 20% faster than 6.46s. We're just throwing around numbers now.
My point was that the cpu load is "about even" compared to if the C version was single-threaded, in which case it would look more like 200-300% bigger cpu load instead of merely 20%.
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?
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
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...
Minor improvements to the Rust programs for "mandelbrot" and "binary-trees" are also awaiting review!