Optimising Common Lisp to try and beat Java and Rust on phone encoding 2/2(renato.athaydes.com) |
Optimising Common Lisp to try and beat Java and Rust on phone encoding 2/2(renato.athaydes.com) |
This type of thing reminds me of the three articles ending in 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.
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.
I'm sure if you submitted a better implementation he'd be happy to add it in.
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-enco...
Your suggestions would make the code much slower.
There may be ways to make it a bit faster, but not with your silly suggestions.
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.
I've tried a few myself and I am almost sure your hints will not work.
> 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.
The end result needs to be printing the strings so I don't see how you can work around that. Can you at least post your code doing that in a way that won't totally destroy the performance gains you may have obtained elsewhere?
> The objective is to get the fastest implementation possible, and having optimised Java and Rust implementations to compare against is a motivator to keep going until there really isn’t anything else that can be tried!
> Do you think Common Lisp can run as fast as well-optimised Rust? Read on if you want to find out.
Hence if you want it to get even better you should provide feedback to the author, and while I absolutely respect your right to decide you can't be bothered, I don't think it's his fault that he's using code that was well-optimized according to the rustaceans who -did- talk to him.
I'm reacting to your comment here:
> The author was pretty explicit in the article that the rust implementation was suboptimal.
This is not the way the article portrays it.
The main comparison of the article is Main2.java, main.rs, and main.lisp, as the author both calls out in the article and the attached GitHub repo (as is apparent in the author's choice of optimizations; if it was a comparison of algos, then the CL and Rust versions would be rewritten to use tries as well).
The point is the author did not explicitly call out this current Rust iteration as explicitly suboptimal RE CL. The closest the article comes to calling the Rust iteration suboptimal is
> However, the Java and Rust implementations were, as CL’s, written without much thought given to performance, after all the description of the original study which introduced the problem asked participants to focus on correctness and readability, not performance.
which is referring to the previous iteration of the code, not the current one.
(It's also evident from Cryptonic and chrismorgan's comments they are talking about implementation-level concerns, not algo-level ones such as Main2.java vs the other implementations)
If you think I'm wrong, could you please submit a PR and link here?
@Cryptonic 's suggestions are laughable. Try using arrays as HashMap keys in Rust :D nope, won't even compile let alone be fast. There was a way smarter attempt here to do something *based on* arrays: https://github.com/renatoathaydes/prechelt-phone-number-enco...
The DigitBytes struct is needed because just using arrays (I guess they mean slices, as arrays are obviously wrong) is incredibly slow - it would need to consider the whole array every time instead of just the relevant bytes - far slower than `Vec`. This is indeed fast, but slower than Vec.
The other suggestion: print everything at the end?? Do we even know what the objective is here? It's not to finish first, but to show to the user the results as soon as possible. It's like people don't even read the problem proposition and still think it's ok to criticize... also, Rust is using buffered IO... ALSO, the benchmark only prints a single line at the end for the two last runs, essentially doing "print it all at the end".
This is my original sentiment:
https://news.ycombinator.com/item?id=28842546
mst stated that the author explicitly called out the Rust code as suboptimal. That is a misreading of the original text, which was referring to a previous iteration. The author (and you) clearly does not think the current Rust code is suboptimal.
Sorry if it looked like I was being harsh on you particularly, I was not... I was being harsh on people making comments like "this Rust code is very slow" without showing their faster code, making suggestions that would almost certainly be slower or not even compile and other similar things I observed in this thread.
Never believe anyone saying "this could be much faster" without showing their code so people can actually check it.
I will believe the OP's code is slow when I see a faster implementation, which I haven't.