Optimizing Advent of Code D9P2 with High-Performance Rust
I took part in Advent of Code 2024 this year. It's a yearly event where a new holiday-themed programming puzzle is released every day of December through Christmas, and people from all across the internet compete to see who can solve them the fastest.
It's a great place to experiment around with writing low-level, high-performance Rust - as well as learn from the extremely smart people who also competing and discussing their solutions in the chat.
It's one of those things where it's easy to get a working solution, but there's a lot of depth to it when striving for maximum efficiency. There were several points where I thought I'd gone as far as I could only to find one extra trick to bring it that one step further.
This post is a summary of the individual optimizations I made to my solution to speed it up. I profiled it at each step to get an idea of how much each change contributed to the overall improvement. There's a nice spread of high-level algorithmic shortcuts, bespoke data structures, and low-level optimizations + SIMD that all contribute to the final program.
