Performance Showdown: Rust vs Javascript (2020)
cesarvr.io
cesarvr.io
The author has a follow up article[1] on their blog about it. They rewrite the rust code to eliminate the extra allocations they identified at the end of this post. It then performs 8 times faster than the javascript version.
However, I think they could have simply iterated on the code from the first post:
There are a lot of allocations because two strings are created every time they are pushed to the queue (.to_string()):
queue.push(candidate.to_string());
queue.push(token.to_string());
This is unnecessary, because candidate and token are both a single character.Rust has a char type that is useful to store single characters. Especially, unlike String which is heap-allocated, char is a primitive value that resides on the stack and CPU registers. Since we are comparing single characters, it's much better to use char.
So if the queue is defined as a Vec<char> instead of a Vec<String>, and the comparison function took as argument char rather than &String, it will spare a lot of allocations and this will speed up the final application.
let mut queue: Vec<char>
// ...
if !compare(candidate, token) {
queue.push(candidate);
queue.push(token);
// ...
fn compare(token1: char, token2: char) -> bool {
This has also the advantage of removing the references, making the code cleaner. Using Vec::with_capacity(n) instead of Vec::new() will also help lowering the allocation load by preemptively allocating a large enough memory slice. With Vec::new(), the vector will reallocate a few times.Yes Rust, C, C++ can be fast. Really fast. Impossible-to-beat fast - if you know what you're doing. If you don't, it's going to be worse than any trivial python, lua or js that does the same thing.
The interesting question is whether the code produced by the average programmer of that language is fast or not. And there language choice matters quite a bit, both because of language design (i.e. how easy is it to generate good machine code for that language) and because of the culture associated with that language (e.g. you can write extremely efficient Java, but typical Java programs chase a lot of pointers and generate a lot of garbage).
1. by how fast it runs when written by a very experienced developer, or
2. by how fast programs run that are written by the "average" programmer, or
3. by how fast it runs when written by a bad or inexprienced programmer?
For each of these I can think of (at least) one language that would beat the performance of any other. There are languages that are "very difficult to use wrong", and there are languages that are difficult to use right. For the latter, C++ is a great example. You will copy and leak yourself out of memory before you terminate, if you dont know what you're doing.
Maybe we should stop comparing random languages from different domains by how fast they run.
Rust makes it surprisingly easy to write code that absolutely thrashes the memory allocator - using String/Box/Vec and adding .clone() everywhere makes a lot of tricky borrowing problems go away. Is that the kind of code I expect to be writing? Or running? And if so, we shouldn’t expect that kind of code to perform much better in most cases than javascript.
* Is language X that we all know suitable?" * Is there a language Y that we could all learn in an acceptable time optimal? * What does the tooling look like? * How would we bring in new people?
CPU runtime is just one aspect to consider
Not just this, but the ceiling of performance improvements matter a lot too.
Rust allows you to write high-level code, where you can "easily" jump into Rust coming from JavaScript. You performance might be on par in your initial versions while you are getting into the language.
It starts to matter a lot when you now have a working application, and you start using it. With JavaScript you will quickly reach a point where your idiomatic JavaScript is about as fast as it'll go.
With Rust, there usually keeps being tricks you can pull to squeeze more performance out of it, and you can do it just for the hot-paths of your code instead of rewriting the entire thing in a new language because you reached your limit.
A good example of this limit is something like the TypeScript compiler. It has huge performance issues with larger codebases, but unfortunately there's not much that can be done without rewriting the entire damn thing in e.g. Rust, because you've reached the limits of JavaScript.
But the floor can matter too. For someone trained to write high-performance JavaScript, JavaScript's performance floor is higher than Rust's, and they can write more JavaScript faster.
> A good example of this limit is something like the TypeScript compiler. It has huge performance issues with larger codebases, but unfortunately there's not much that can be done without rewriting the entire damn thing in e.g. Rust, because you've reached the limits of JavaScript.
Actually, you can fix it by rewriting it as a single-pass compiler to improve the algorithms.
I'm not sure what you mean by the floor here? Experience? The author of the article was experienced in JavaScript and was new to Rust for example.
>Actually, you can fix it by rewriting it as a single-pass compiler to improve the algorithms.
I'd say that's on the same scale of work as rewriting it in a new language.
And even then, this is most likely not a realistic solution, I can almost guarantee you there will be stuff they are currently doing that they cannot do in such an architecture.
The first problem with the words "single-pass" and "Javascript" that come to mind are the out-of-order variable declarations, i.e. var, which bubbles up.
There are a ton of other issues as well.
The biggest reason, I think, is that C encourages you to be memory efficient. Allocating memory is not trivial and you have to keep track of all your pointers. On the other hand, it makes it easy to modify things in place, where other languages favor immutability. But if you do a lot of allocations, create a makeshift garbage collector, and memcpy a lot, then your C code will be really slow, because you are basically doing what makes other languages slower, but worse because other languages are heavily optimized for that use cases and your code most likely isn't.
https://github.com/cesarvr/AOCRust/blob/590270ed268dcd4ff01b...
Rarely see this kind of obscenity outside of beginner's university C++ classes.
int hasz[200];
memset(hasz, 0, 200);
yikes, that initializes the first 200 bytes to 0x00, or only the first 50 integers in the array. this code is... bad.or the first 100 integers https://gcc.gnu.org/wiki/avr-gcc
Memory allocation is expensive. C++ pmr allocators provide powerful tools to manage memory.
No, that is not what this is. Rust IS faster than most languages on earth.
This is FACT.
Some tools ARE better than others. You only heard the "opposite" when a outlier happened or a user misunderstood how use the tool.
Also this apply to interpreted languages too!:
http://lambda-the-ultimate.org/node/5075
IF you hit their sweet spots.
PD: Just check the Rust reddit. Tons of case of naive newcomers with massive improvements on speed/performance just porting to Rust.
---
This kind of history is similar to "A virus happened on OS X/Linux!" Then say "No OS is more secure than others!" is a massive flaw. Some are more secure. Only this time is news precisely because is RARE!
It adds a runtime sanitizer to detect some (but not all) UB.
1. faster when written and optimized by an expert, who writes the best blog on how to optimize X
2. faster when written and optimized by a competent-but-not-necessarily-expert programmer, who reads the best blog on how to optimize X
3. faster when written without speed in mind
It seems like C, C++, and Rust are all more or less tied at the head of the pack for #1 and #2. There's obviously a lot of room for debate here, but it seems like many other languages (Go? JavaScript running on V8?) can get pretty close for #1 but struggle for #2.
For #3, it seems like C is the king, because of the very low-level style that it forces on the programmer. Below that things get murky. I'm inclined to believe Rust does well here, because it doesn't usually allocate without being asked to, but I assume the same logic applies to other languages I'm less familiar with (D, Zig). How well C++ does probably depends on how you interpret the question. (Like does the programmer make even the slightest effort to avoid implicitly copying big data structures, to take things by reference, etc?)
This is inaccurate. Vec<char> will store chars on the heap. & the concept of primitive values exists in Java, whereas in Rust any struct you declare can exist on the stack (or in CPU registers if the optimizer decides to)
But yes, char is a 32 bit integer as opposed to String being a Vec<u8> under the wraps, & Vec<char> is preferable to Vec<Vec<u8>>
Or make a struct with {char, boolean}.
/*
Recursively removes doublets from input. A doublet is a pair of adjacent chars,
identical or differing only in capitalization (eg. "aa" or "aA"). The result is
written to output, which must be at least input_length bytes long.
Returns the number of bytes in the result.
*/
size_t remove_doublets(char * output, const char * input, size_t input_length);
and the body is a dozen lines of pointer pushing and tolower. Do you faff around with malloc? unicode case conversions? hashmaps??? Of course not, that would be too hard, so you just write the stupid C code. For all its faults, the C idiom really does push you towards the simple, stupid answer to code like this.Really, no matter what the language is, people need to actually put some thought into what they're doing.
The whole "I wrote it in JS and then ported it" introduction meant I was expecting exactly that kind of problem.
If the author had provided the input data, I would optimize the JavaScript further so that Rust and JS would be more even.
Most JS VMs have several different string types internally. Looking at V8's source code (https://github.com/v8/v8/blob/master/src/builtins/builtins-s...), it looks like there's a very happy ASCII fast path that makes toLowerCase really fast on ASCII. Actually, it even looks as if it's processing the characters 8 bytes at a time (https://github.com/v8/v8/blob/master/src/strings/string-case...).
Running 100 iterations gives you a much better idea of actual performance (JS is over 10x slower) but then you need to think about what compiler optimizations are being applied.
What Rust, C, C++ and the like actually give you is control. It is up to you, as a developer, to leverage that control to get better performance. Control also gives you nearly limitless rope to hang yourself with.
With a couple changes you could probably eliminate all allocations after the initial one.
* There is no use in first pop()ing a candidate from the "reacts" list and then potentially re-pushing them later. Getting a pointer to the last element, and removing it if it is not needed, is more efficient.
* Reordering the character equality condition could help a tiny bit since the inequality check should be faster than the ignore case check.
I think the given ordering is better: in a conjuction, you typically put the less likely condition first, not the cheaper one.
Out of curiosity, I just did a small benchmark (criterion) using the input.txt provided, and reordering results in a 10% difference:
Old Order time:[307.28 us 309.12 us 311.17 us]
Reversed time:[270.82 us 271.18 us 271.54 us]
This feels weird since the input.txt contains few pairs of equal characters, so there is likely something else going on. The inequality is very inexpensive but the ignore case compare should not be that expensive either.Micro benchmarking remains a fickle beast :)
Anyone who's been writing rust for a little bit will notice the String clone like a sore thumb. The "go-to-perf-guide" also very explicitly states than clones on String/Vec/Box etc will cause an allocation and slow down your code.
https://gist.github.com/jFransham/369a86eff00e5f280ed2512145...
In every one of these micro benchmarks, the comments will then show that by removing the alloc, the Rust version ends up much much faster.
String cloning is one of those things you learn to avoid early on, and any time you type "clone" it should be obvious that there's a better way to write your algorithm.
- Only one program is tested, exercising a very small portion of each language (and its built-in APIs).
- The runtime is too small; less than a second in both cases. I'd really need to see examples where the benchmark has been run in a loop multiple times, preferably with a warmup run beforehand, and an execution time measured in tens of seconds.
At least the author made the effort to figure out the reasons behind the differences (based on the hypothesis that Rust would be faster), so credit is due there.
[0]: https://cesarvr.io/post/rust-vs-javascript/
[1]: https://play.rust-lang.org/?version=stable&mode=debug&editio...
This in itself is not the problem. The problem is that you shouldn't be doing this at code level, but at compiler level. The optimizer is supposed to do these manipulations. At code level, you should be able to describe your problem in lots of details, use identities to simplify your logic, but leave the optimizations to the compiler. From the little I read about rust, I believe its type system is powerful enough to enable the compiler to do this. I believe it is a matter of time until the compiler matures to the point of doing the kind of optimization it is required to do.
1. As far as I'm aware, Haskell isn't able to do any of that at the code level. I'm interested in what a language that is able to do that would look like.
2. I'm curious as to what you consider an "optimization" to be left to the compiler, and what you consider part of the "problem". For example, does the compiler decide which implementation of a set to use?
3. I'm also wondering what you mean by "proving correctness." If you're alluding to formal verification, then that is notoriously hard to scale, which conflicts with the stated goal of making optimization easier to scale.
Some pseudocode would shed light on all these questions.
At best the compiler could ASK the programmer about it.
The mistake here really is trying to do case insensitive string comparison by converting both arguments to the same case, then comparing them with case-sensitivity. It is much better to compare them directly, but case-insensitively.
This is basically the same problem as in C++: convenient and "idiomatic" standard library features may end up doing tons of expensive hidden allocations. Isn't this a pretty big problem for a "systems programming language"?
fn react(token1: &String, token2: &String) -> bool {
token1.to_lowercase() == token2.to_lowercase() && token1 != token2
}
Anyway as soon as I saw the problem I thought "this is either completely trivial or insanely difficult depending on whether you want proper unicode handling or not".I haven't really thought about it but I doubt his solution is fully correct according to unicode. E.g. What happens with `aßSSb`? Who knows what should even happen in that case.
As for the malloc performance, MacOS has a significantly slower system memory allocator than Linux does. If you use jemalloc (https://crates.io/crates/jemallocator) instead I think you will see better performance than Javascript.
Good article anyway.
I'd also be interesting in the performance improvements from replacing those to_lowercase() calls with a lookup from a static lookup array. Something like:
if ( explosion_map[token1] == token2 )
There would need to be duplicates, explosion_map['a'] = 'A' and explosion_map['A'] = 'a'. But that's a small cost to pay for eliminating three function calls and two comparisons. As an added bonus, branch prediction will work really well on this strategy (since the majority of comparisons will have the same result). And doing that is a more of an actual language performance comparison, instead of a the standard library performance comparison this is. perf record -F 99 ./target/release/day-5Don't think I'm the first to mention - what would profile.release do if you're not calling cargo build --release?
Maybe the author is, but a slight suspicion... they're calling older code.
(Also, what's the deal with read_file() and wanting a Vec<String>? Rust has a read_to_string() method as part of std::fs.)
The algorithm in the article would be quadratic in perl 5; not sure about rust or js, but the point still stands: It’s likely to see asymptotic performance differences in different languages.
(Edit: it’s not quadratic in perl. If it used shift to pull from the front of the array it would be.)
In my opinion what matters is how much energy is consumed when executed on a smartphone or IoT device. Because there the main question is, when do I have to recharge the next time. For IoT applications this is highly critical. In this regard fast is not automatically energy efficient, if you consider e.g. big.LITTLE cpu architectures...
If writing this in JS took an hour to deliver acceptable performance, and writing it in Rust took 6 hours of reading documentation and googling to produce a similar or faster by a few milliseconds result, then JS is the clear winner here.
More like: If you tune your code Rust (and any native language) is faster, with naive code however there is a good chance that JavaScript can be faster.
I saw a 10x slowdown porting the Chipmunk2d physics engine to javascript. (Which dropped to 5x or something after a few weeks of JS optimizations). Porting operational transform heuristics from JS to C got me a ~40x speedup. The code in question used heterogeneous data types which V8 hates (causing both heap thrashing and code deopt). In C I handed it with a tagged union and the code needed 0 allocations in the hot path.
Generally the rule is, if your code has complex data types, heterogeneous data types or a lot objects being created and destroyed it be much slower in javascript compared to C/Rust. A lot of that benefit goes away if the native code does sloppy allocations everywhere.
And on the other hand, if your code is Math heavy, operating on simple data types, V8 will do great work.
Carefully written javascript is still pretty slow because you can’t choose to put objects on the stack in JS, or allocate nested objects together in contiguous memory. And that makes a massive difference because you end up thrashing main memory when you could be spending those cycles getting work done.
That is true, however there is a huge domain of problems where that isn't much of a concern, while development time spent on it is a concern.
Then sacrificing a bit of performance over development speed can be quite worthwhile.
Of course not a high frequency trading platform and not an AAA+ Game, but a small Webservice just taking data from a ("slow") database, doing little transformation, and sending over network .... less of a problem