Hi, I decided to use Odin to implement a solution to a phone encoding problem which I used for analysing solutions in many different languages before.
The problem and my motivation behind this are explained in my blog post: Renato Athaydes
I initially implemented the solution in Java, based on the Common Lisp implementation by Peter Norvig, and then I changed the solution to be more Java-idiomatic and used a Trie data structure which made it much faster.
I then implemented it in Rust as an exercise to learn Rust, so obviously my initial solution was very bad (just like my current Odin solution, I imagine).
I ended up writing a series of blog posts about the Rust improvements people suggested to me:
As a new user here, I cannot post more than 2 links, so sorry but I am posting only the paths after the website domain, which is
renato.athaydes.com:
/posts/how-to-write-slow-rust-code
/posts/how-to-write-slow-rust-code-part-2
/posts/how-to-write-fast-rust-code
And did the same for Common Lisp as well:
/posts/revenge_of_lisp
/posts/revenge_of_lisp-part-2
There are solutions also in Dart, Julia, Zig, C, D and probably more I can’t even remember, both by me and by people who read my posts and decided to contribute… if you’re interested, check the many branches in the repository:
Finally, here’s my initial Odin solution which I wrote while learning Odin (please keep that in mind, I don’t know idiomatic Odin and likely made many bad choices):
this is under my github project: renatoathaydes/prechelt-phone-number-encoding
/commit/debd4b92e71dba9e218e7c87cc67e319ae8a442b
This is currently running about 10x slower than the fastest solution, which is the Rust one: /blob/fastest-implementations-print-or-count/src/rust/phone_encoder/src/main.rs
The Odin solution is a nearly-port of the D solution (which gets pretty close in performance to Rust): /blob/debd4b92e71dba9e218e7c87cc67e319ae8a442b/src/d/src/dencoder.d
I am posting here to ask for help with the following:
- how to profile my Odin code?
- can you see obvious mistakes I need to fix to improve performance?
- would you like to submit a PR with your own solution?
I knew that my solution would be much slower because of two issues I didn’t know how to fix:
- Odin map does not allow customizing the hash function, as it seems. That’s important for this problem. I guess I would need to implement my own Map, but that’s a bit too much to ask for in general, I think. Perhaps it’s simple enough in Odin?
- The key is supposed to be a byte slice, but because that is not “simply comparable”, I had to use an array instead. That’s slow because it will compare all bytes when it should only check a few - those which are used.
Notice that one of the program “modes” is to just print solutions, so yeah, I know that will be a bottleneck for the large inputs and I need to buffer the printing, but please don’t focus on that because even for the count variation, which only prints the number of solutions that were found, the Odin solution is still too slow.
Thanks for any feedback!