Solving Advent of Code 2024 in Under 1ms(github.com) |
Solving Advent of Code 2024 in Under 1ms(github.com) |
*As of today, our solutions are able to solve all 49 problems in <1ms!*
I have obtained consent from all the top participants to post their solutions to a shared repo, for the community to review and learn from! *All solutions are now available at the linked GitHub repo!*
Our solutions have a total runtime of *988936ns*!
# Context/Caveats
- All submissions were run on the same hardware (Ryzen 5950X) to ensure consistency, with the same compiler flags and features available. This was on rustc nightly (updated throughout the course of the contest), and with CPU speed capped at 3400 MHz with boost clock disabled.
- AVX-512 was not available on the machine so none (?) of the solutions utilize that particular set of accelerated instructions, but there is plenty of other SIMD in use.
- All submissions were run against the same inputs to ensure consistency.
- Caching anything that has been fed with input was not allowed to prevent cheating and/or trivial solutions like `Map<Input, Output>`.
- For the same reason, inputs were not directly available to the participants, and were not provided at compile-time.
- Participants were allowed to use compile-time tricks in their answers. Due to limitations in the benchmark bot, the runtime of these optimizations could not be measured. This was considered acceptable as the compiled binaries were expected to otherwise work correctly for arbitrary inputs. This means that participants are allowed to use look-up tables (LUTs) in their answers, but those LUTs are expected to work for arbitrary inputs, not just specific ones.
- I/O is trivial, and was thus not measured as part of the benchmark. That is, participants were provided with an `&str` or `&[u8]` input (their choice) and expected to provide an `impl Display` as part of their result. Therefore, input parsing was measured.
If you are interested, join us in #advent-of-code-2024 on the Discord server for further discussion :)
# Further Reading
If you would like a more in-depth explanation of some of the optimization techniques used, I highly recommend you check out this article by ameo [0] (one of our participants). It covers the process they used to optimize their solution for Day 9 Part 2, and how they got it to the top of our leaderboard. The article provides incredible information on the process of both high-level and micro optimization.
# Credits:
- Thank you to the members of the `Rust Programming Language Community` and `Serenity-rs` Discord servers and everyone else who participated in the challenge!
- Thank you to Eric Wastl for hosting AoC every year!
- Thank you to Noxim [1] for writing the original version of our benchmark bot [2].
- Extra special thank you to yuyuko [3], bend-n [4], and giooschi [5] for their help in maintaining and improving our benchmark bot.
[0]: https://cprimozic.net/blog/optimizing-advent-of-code-2024/
[1]: https://github.com/noxime
[2]: https://github.com/indiv0/ferris-elf
[3]: https://github.com/ultrabear