Live data from Hacker News

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

renato.athaydes.com

21–26 of 26 posts

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

#21

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.

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.

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

#22

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.

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://fitzgeraldn…

> 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-enco...

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

#23
post #22

Earlier quoted context omitted.

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://fitzgeraldn…

> 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'…

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.

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

#24
post #22

Earlier quoted context omitted.

> 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'…

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 byt…

There are a few pull requests that claim to make the code faster, but you can run the benchmarks and see none of them actually did. Why not try to improve the code I posted above and make the apparently small changes you want to make and check if it's faster or not.

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?

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

#25
post #20

Earlier quoted context omitted.

That's only vis-a-vis the Main.java Java implementation, which has a different algorithm, not implementation. The author is not referring to the CL implementation (note that the author explicitly calls out Main2.java, CL, and the Rust versions as being the most similar and worthy of being benchmarked). The Main.java one is more of a curio than anything else, which the author threw in because it was the first implemen…

There are two or three branches with different versions of the Rust code, and the author is using the fastest one. What you believe will make the Rust code faster won't, trust me. 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…

I think you're missing the point of my comments. I know neither enough of CL nor Rust to make a comment on the performance (I have less than ~1000 lines of experience in either and have only built the smallest of toy projects in either language).

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.

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

#26
post #20

Earlier quoted context omitted.

There are two or three branches with different versions of the Rust code, and the author is using the fastest one. What you believe will make the Rust code faster won't, trust me. 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…

I think you're missing the point of my comments. I know neither enough of CL nor Rust to make a comment on the performance (I have less than ~1000 lines of experience in either and have only built the smallest of toy projects in either language). 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 misreadi…

> 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.

Post reply on HN