8 ms·

The point on the unicode to_lowercase is quite interesting. I wonder if the javascript version is faster because it's less safe or because the JIT compiler iden

The point on the unicode to_lowercase is quite interesting. I wonder if the javascript version is faster because it's less safe or because the JIT compiler identifies properly that unicode-awareness is useless and specializes the code. 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. [1] https://cesarvr.io/post/rust-vs-javascript/ https://cesarvr.io/post/rust-vs-javascript/

mathw 6y ago
Yes I read the Rust code and just knew it would likely not be dramatically faster than the JS - certainly not as fast as it could be. This is why all languages reward study and depth of knowledge, as you just avoid some of the patterns which kill your performance almost instinctively after a while. The whole "I wrote it in JS and then ported it" introduction meant I was expecting exactly that kind of problem.
lionkor 6y ago
This is why no language is "just faster" than another. The languages that are commonly associated with being "fast" can be way slower than any "slow" language if written wrong. 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.
- adrianN 6y ago
  Yeah well it's pretty obvious that you can write slow code in any language. 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).
  - lionkor 6y ago
    It's a really interesting and important question though; Do you measure a languages "performance" 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.
    - josephg 6y ago
      My first take at an answer is, what sort of code do I anticipate writing in each language? And what sort of code do I expect to see from my peers? 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.
__s 6y ago
> char is a primitive value that resides on the stack and CPU registers 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>>
silvestrov 6y ago
They also call to_lowercase() too many times. They should start out by creating an char array with all letters lowercased and a boolean array to tell if the char originally was lowercased. Or make a struct with {char, boolean}.
edflsafoiewq 6y ago
IMO this is no small part of why C still has its reputation for speed. Think how you'd write this in C. Maybe /* 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.
- ziml77 6y ago
  That's also a problem with C though. Because the complex answer is such a pain to write, people go for the simple answer that doesn't handle all the cases that it actually should. Like ignoring Unicode case conversions means that it will only work as expected on English input. Really, no matter what the language is, people need to actually put some thought into what they're doing.
  - brundolf 6y ago
    Both good points. C gives you rope to hang yourself with when it comes to correctness; Rust gives you rope to hang yourself with when it comes to performance. Personally I prefer the latter, but awareness and understanding of what's really going on is important no matter what language you're using.
    - bobthebuilders 6y ago
      The other thing is say algorithm selection. Some data structures may be more performant for the job at hand, but do you really want to package or build them yourself? A lot of the time the answer is no.
- higerordermap 6y ago
  Among new languages, zig aims to make all allocations obvious.
crazypython 6y ago
Node.js incurs a fixed initialization time of 0.09s on my machine, which in a real-world scenario has already occurred, and isn't a factor in runtime performance. That makes Rust only 5 times faster. If the author had provided the input data, I would optimize the JavaScript further so that Rust and JS would be more even.
- creata 6y ago
  There's some input data over at https://github.com/cesarvr/AOCRust/blob/master/day-5/rewrite/input.txt https://github.com/cesarvr/AOCRust/blob/master/day-5/rewrite... .
- pdimitar 6y ago
  The input data is there in the repo. Go on, do the JS version, I'm curious.
jcranmer 6y ago
> I wonder if the javascript version is faster because it's less safe or because the JIT compiler identifies properly that unicode-awareness is useless and specializes the code. 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-string.cc#L347 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.cc#L43 https://github.com/v8/v8/blob/master/src/strings/string-case...).
brundolf 6y ago
IMO Rust's main performance advantages come from avoiding allocations. Not only does it give you more control over them like C and C++ do, it also lets you do things that you could technically do in those languages, but wouldn't, because they're too dangerous. So you avoid even more allocations in practice (you don't need to defensively clone strings, for example)

mathw 6y ago

Yes I read the Rust code and just knew it would likely not be dramatically faster than the JS - certainly not as fast as it could be. This is why all languages reward study and depth of knowledge, as you just avoid some of the patterns which kill your performance almost instinctively after a while. The whole "I wrote it in JS and then ported it" introduction meant I was expecting exactly that kind of problem.

lionkor 6y ago

This is why no language is "just faster" than another. The languages that are commonly associated with being "fast" can be way slower than any "slow" language if written wrong. 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.

adrianN 6y ago
Yeah well it's pretty obvious that you can write slow code in any language. 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).
- lionkor 6y ago
  It's a really interesting and important question though; Do you measure a languages "performance" 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.
  - josephg 6y ago
    My first take at an answer is, what sort of code do I anticipate writing in each language? And what sort of code do I expect to see from my peers? 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.

__s 6y ago

> char is a primitive value that resides on the stack and CPU registers 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>>

silvestrov 6y ago

They also call to_lowercase() too many times. They should start out by creating an char array with all letters lowercased and a boolean array to tell if the char originally was lowercased. Or make a struct with {char, boolean}.

edflsafoiewq 6y ago

IMO this is no small part of why C still has its reputation for speed. Think how you'd write this in C. Maybe /* 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.

ziml77 6y ago
That's also a problem with C though. Because the complex answer is such a pain to write, people go for the simple answer that doesn't handle all the cases that it actually should. Like ignoring Unicode case conversions means that it will only work as expected on English input. Really, no matter what the language is, people need to actually put some thought into what they're doing.
- brundolf 6y ago
  Both good points. C gives you rope to hang yourself with when it comes to correctness; Rust gives you rope to hang yourself with when it comes to performance. Personally I prefer the latter, but awareness and understanding of what's really going on is important no matter what language you're using.
  - bobthebuilders 6y ago
    The other thing is say algorithm selection. Some data structures may be more performant for the job at hand, but do you really want to package or build them yourself? A lot of the time the answer is no.
higerordermap 6y ago
Among new languages, zig aims to make all allocations obvious.

crazypython 6y ago

Node.js incurs a fixed initialization time of 0.09s on my machine, which in a real-world scenario has already occurred, and isn't a factor in runtime performance. That makes Rust only 5 times faster. If the author had provided the input data, I would optimize the JavaScript further so that Rust and JS would be more even.

creata 6y ago
There's some input data over at https://github.com/cesarvr/AOCRust/blob/master/day-5/rewrite/input.txt https://github.com/cesarvr/AOCRust/blob/master/day-5/rewrite... .
pdimitar 6y ago
The input data is there in the repo. Go on, do the JS version, I'm curious.

jcranmer 6y ago

> I wonder if the javascript version is faster because it's less safe or because the JIT compiler identifies properly that unicode-awareness is useless and specializes the code. 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-string.cc#L347 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.cc#L43 https://github.com/v8/v8/blob/master/src/strings/string-case...).

brundolf 6y ago

IMO Rust's main performance advantages come from avoiding allocations. Not only does it give you more control over them like C and C++ do, it also lets you do things that you could technically do in those languages, but wouldn't, because they're too dangerous. So you avoid even more allocations in practice (you don't need to defensively clone strings, for example)