10 ms·

Optimising Common Lisp to try and beat Java and Rust on phone encoding 2/2

78 points by mark254 5y ago

rob74 5y ago
In case anyone else is wondering what the author means by "phone encoding": it's an algorithm trying to map telephone numbers to words (via the letters usually printed on telephone keypads). Would have been better to call it "phone number encoding" IMHO...
hajile 5y ago
Those are pretty impressive results for what didn't amount to a huge amount of changes (mostly just adding some types).
Cryptonic 5y ago
The Rust code is bar far not optimized. For example while loading the dictionary, why creating a Vec and returning it instead of operating on a max word size array and reusing it. Also why not write everything at the end. I'm not a Rust Professional also, but maybe get a review by one please before benchmarking against something else.
- brabel 5y ago
  Commenting without having to get to the trouble of showing your code is faster is cheap. Your suggestions would make the code much slower. There may be ways to make it a bit faster, but not with your silly suggestions.
- chrismorgan 5y ago
  Another point where it’s doing something that to me as a Rust expert is obviously inferior: it’s using Unicode-aware string stuff although anything non-ASCII will either be ignored (if non-alphabetic) or panic (if alphabetic). It’d certainly be better to treat the input throughout the program as a sequence of bytes rather than as UTF-8. This type of thing reminds me of the three articles ending in https://fitzgeraldnick.com/2018/02/26/speed-without-wizardry.html https://fitzgeraldnick.com/2018/02/26/speed-without-wizardry... (which has links to the first two parts of the saga), where one guy rewrote stuff in Rust for performance, another demonstrated how it was possible to make the JavaScript version faster than the Rust by some algorithm changes and by various painful and fragile tricks requiring detailed knowledge of the runtime environment, and finally the first guy applied the applicable parts of that back to the Rust, after which it handily beat the JavaScript again while also being more consistent and dependable.
  - nerdponx 5y ago
    It's worth distinguishing between algorithmic optimizations, optimizations that generally take advantage of the language standard/runtime, and optimizations that are highly specific for one machine/platform/implementation. It's also worth keeping track of relative programmer effort to optimize. I think most people are moderately-optimized benchmarks, i.e. moderate effort expended relative to baseline implementation effort. That is, people are interested in getting the most performance out of the least amount of effort. Obviously some people want and need to care about extreme peak optimization. But if you are writing benchmarks for a wide audience, that probably should not be your priority.
  - brabel 5y ago
    > it’s using Unicode-aware string stuff Rust uses UTF-8 internally for Strings, so it's very efficient to parse a file into a String, then using slices to go through it... this is probably the best you can get as parsing ASCII input as UTF-8 is very efficient (the 0-bit is always zero in ASCII, the unicode decoder only needs to check that's the case for every byte, so it's not some kind of complicated computation it's doing to decode)... If you use bytes for everything, you will make the whole code much harder to follow and it still won't run faster. Check for yourself: https://github.com/renatoathaydes/prechelt-phone-number-encoding/blob/c93a961d30144f2fd8469b767f6a853df82b9fc9/src/rust/phone_encoder/src/lib.rs https://github.com/renatoathaydes/prechelt-phone-number-enco...
    - chrismorgan 5y ago
      The code will be somewhat faster (I don’t care to predict how much) from removing the variable-width character encoding in favour of bytewise access. Yes, pure ASCII stuff has some fast paths in string access, but they’re still decidedly slower than the fixed-width encoding that is [u8]. Using strings also gives the incorrect impression that it can cope with non-ASCII. The code will be easier to follow if you use bytes throughout, because currently it’s a mixture of bytewise and charwise operations, so that you need to think a little about whether you’re dealing with char or u8 in each place (and half of them are even mislabelled); and there are suitable alternative ASCII methods for every place that uses charwise methods (e.g. char.is_digit(10) → u8.is_ascii_digit()) so that no extra burden is added. In the end the only place slightly complicated by it is printing the solutions, but more code will have been decomplicated—hotter path code, too—so that it’s easily worth it. I don’t know where the code you’re citing came from, it’s newer than what’s on the master branch but in its changes includes some pretty bad stuff like DIGITS, using &str for something that is always a single-character ASCII digit, accessed by already having had the digit as a u8 and turning it back into a string prematurely. Admittedly the optimiser is going to fix a fair bit of that badness, but not all.
geospeck 5y ago
There are a lot of interesting comments in the Lisp subreddit regarding the second part of the blog: https://www.reddit.com/r/lisp/comments/q5f7u5/revenge_of_lisp_part_22_optimising_common_lisp_to/ https://www.reddit.com/r/lisp/comments/q5f7u5/revenge_of_lis...
tonetheman 5y ago
And here come the Rust fan boys telling us the correct way to write the code so it will be faster than anything ever written, much safer than anything ever written and better than any programming language ever written.
- Tanjreeve 5y ago
  If there's easy out the box ways to write things that a normal Dev would do without pushing the language to its limits then it seems a bit unfair to ignore it. If I declared python to be the world's most performant concurrent language by hand wiring Cython and the deepest depths of the language and then completely ignored the out the box constructs in other languages that would be a bit misleading too.
- Zababa 5y ago
  As a Rust fanboy, Rust's advantage is that I wouldn't be afraid of dropping to its level, while I definitely wouldn't feel comfortable with C++ or C. Once the program is written, it's the usual cycle of optimizations: benchmark, flamegraph, cachegrind, etc.
- chrismorgan 5y ago
  Refer to my other comment here and the cited articles for a fair rebuttal: Rust lets you get equivalent or better performance (than Common Lisp or Java, in this instance) without significant special effort or deep knowledge of the environment, while being much more predictable; and if you do apply deeper knowledge of the language, then it’ll pull well ahead.

78 points by mark254 5y ago

In case anyone else is wondering what the author means by "phone encoding": it's an algorithm trying to map telephone numbers to words (via the letters usually printed on telephone keypads). Would have been better to call it "phone number encoding" IMHO...

hajile 5y ago

Those are pretty impressive results for what didn't amount to a huge amount of changes (mostly just adding some types).

Cryptonic 5y ago

The Rust code is bar far not optimized. For example while loading the dictionary, why creating a Vec and returning it instead of operating on a max word size array and reusing it. Also why not write everything at the end. I'm not a Rust Professional also, but maybe get a review by one please before benchmarking against something else.

brabel 5y ago
Commenting without having to get to the trouble of showing your code is faster is cheap. Your suggestions would make the code much slower. There may be ways to make it a bit faster, but not with your silly suggestions.
chrismorgan 5y ago
Another point where it’s doing something that to me as a Rust expert is obviously inferior: it’s using Unicode-aware string stuff although anything non-ASCII will either be ignored (if non-alphabetic) or panic (if alphabetic). It’d certainly be better to treat the input throughout the program as a sequence of bytes rather than as UTF-8. This type of thing reminds me of the three articles ending in https://fitzgeraldnick.com/2018/02/26/speed-without-wizardry.html https://fitzgeraldnick.com/2018/02/26/speed-without-wizardry... (which has links to the first two parts of the saga), where one guy rewrote stuff in Rust for performance, another demonstrated how it was possible to make the JavaScript version faster than the Rust by some algorithm changes and by various painful and fragile tricks requiring detailed knowledge of the runtime environment, and finally the first guy applied the applicable parts of that back to the Rust, after which it handily beat the JavaScript again while also being more consistent and dependable.
- nerdponx 5y ago
  It's worth distinguishing between algorithmic optimizations, optimizations that generally take advantage of the language standard/runtime, and optimizations that are highly specific for one machine/platform/implementation. It's also worth keeping track of relative programmer effort to optimize. I think most people are moderately-optimized benchmarks, i.e. moderate effort expended relative to baseline implementation effort. That is, people are interested in getting the most performance out of the least amount of effort. Obviously some people want and need to care about extreme peak optimization. But if you are writing benchmarks for a wide audience, that probably should not be your priority.
- brabel 5y ago
  > it’s using Unicode-aware string stuff Rust uses UTF-8 internally for Strings, so it's very efficient to parse a file into a String, then using slices to go through it... this is probably the best you can get as parsing ASCII input as UTF-8 is very efficient (the 0-bit is always zero in ASCII, the unicode decoder only needs to check that's the case for every byte, so it's not some kind of complicated computation it's doing to decode)... If you use bytes for everything, you will make the whole code much harder to follow and it still won't run faster. Check for yourself: https://github.com/renatoathaydes/prechelt-phone-number-encoding/blob/c93a961d30144f2fd8469b767f6a853df82b9fc9/src/rust/phone_encoder/src/lib.rs https://github.com/renatoathaydes/prechelt-phone-number-enco...
  - chrismorgan 5y ago
    The code will be somewhat faster (I don’t care to predict how much) from removing the variable-width character encoding in favour of bytewise access. Yes, pure ASCII stuff has some fast paths in string access, but they’re still decidedly slower than the fixed-width encoding that is [u8]. Using strings also gives the incorrect impression that it can cope with non-ASCII. The code will be easier to follow if you use bytes throughout, because currently it’s a mixture of bytewise and charwise operations, so that you need to think a little about whether you’re dealing with char or u8 in each place (and half of them are even mislabelled); and there are suitable alternative ASCII methods for every place that uses charwise methods (e.g. char.is_digit(10) → u8.is_ascii_digit()) so that no extra burden is added. In the end the only place slightly complicated by it is printing the solutions, but more code will have been decomplicated—hotter path code, too—so that it’s easily worth it. I don’t know where the code you’re citing came from, it’s newer than what’s on the master branch but in its changes includes some pretty bad stuff like DIGITS, using &str for something that is always a single-character ASCII digit, accessed by already having had the digit as a u8 and turning it back into a string prematurely. Admittedly the optimiser is going to fix a fair bit of that badness, but not all.

geospeck 5y ago

There are a lot of interesting comments in the Lisp subreddit regarding the second part of the blog: https://www.reddit.com/r/lisp/comments/q5f7u5/revenge_of_lisp_part_22_optimising_common_lisp_to/ https://www.reddit.com/r/lisp/comments/q5f7u5/revenge_of_lis...

tonetheman 5y ago

And here come the Rust fan boys telling us the correct way to write the code so it will be faster than anything ever written, much safer than anything ever written and better than any programming language ever written.

Tanjreeve 5y ago
If there's easy out the box ways to write things that a normal Dev would do without pushing the language to its limits then it seems a bit unfair to ignore it. If I declared python to be the world's most performant concurrent language by hand wiring Cython and the deepest depths of the language and then completely ignored the out the box constructs in other languages that would be a bit misleading too.
Zababa 5y ago
As a Rust fanboy, Rust's advantage is that I wouldn't be afraid of dropping to its level, while I definitely wouldn't feel comfortable with C++ or C. Once the program is written, it's the usual cycle of optimizations: benchmark, flamegraph, cachegrind, etc.
chrismorgan 5y ago
Refer to my other comment here and the cited articles for a fair rebuttal: Rust lets you get equivalent or better performance (than Common Lisp or Java, in this instance) without significant special effort or deep knowledge of the environment, while being much more predictable; and if you do apply deeper knowledge of the language, then it’ll pull well ahead.