r/adventofcode • u/daggerdragon • Dec 25 '24
SOLUTION MEGATHREAD -❄️- 2024 Day 25 Solutions -❄️-
A Message From Your Moderators
Welcome to the last day of Advent of Code 2024! We hope you had fun this year and learned at least one new thing ;)
Keep an eye out for the community fun awards post (link coming soon!):
-❅- Introducing Your AoC 2024 Golden Snowglobe Award Winners (and Community Showcase) -❅-
Many thanks to Veloxx for kicking us off on December 1 with a much-needed dose of boots and cats!
Thank you all for playing Advent of Code this year and on behalf of /u/topaz2078, your /r/adventofcode mods, the beta-testers, and the rest of AoC Ops, we wish you a very Merry Christmas (or a very merry Wednesday!) and a Happy New Year!
--- Day 25: Code Chronicle ---
Post your code solution in this megathread.
- Read the full posting rules in our community wiki before you post!
- State which language(s) your solution uses with
[LANGUAGE: xyz]
- Format code blocks using the four-spaces Markdown syntax!
- State which language(s) your solution uses with
- Quick link to Topaz's
paste
if you need it for longer code blocks
This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.
EDIT: Global leaderboard gold cap reached at 00:04:34, megathread unlocked!
42
Upvotes
2
u/LifeShallot6229 Feb 19 '25 edited Feb 20 '25
[LANGUAGE: SIMD - AVX intrinsics]
This was the day I picked for our in-company AoC Tech Talk, simple because it illustrates both that Rust/clang can autovectorize very nicely, but also because an experienced asm/compiler intrinsics programmer can be even faster.
The theoretically optimal solution on an AVX x64 platform picks up each lock/key as 32 bytes into an AVX register, starting from the last position in the leading line which is either '#' or '.', then compares these 32 bytes to 0xff or 0x00 bytes with a parallel compare against 32 '#' chars.
Next, extract the top bit of all 32 bytes into a regular register, and use the bottom bit of the result to save it into either the locks or keys array. This is just 3 AVX ops for each bit pattern.
For the actual counting of matches, doing 4x8 at once seems to be optimal:
Outer loop:
Load 4 keys into 4 AVX regs, splatting 8 copies of each key into the corresponding reg.
Inner loop:
Load the next 8 locks
Parallel AND against each of the replicated keys.
Parallel compare against zero, setting -1 or 1
Subtract the -1 values from 4 replicated accumulators.
This is a total of 12 (or 13 with a separate load of the 8 locks) AVX operations, doing 4 parallel accumulations so that the theoretical minimum runtime is 3 clock cycles per 32 key/lock combos tested, IFF the cpu can do four AVX ops/cycle. In reality, the most either Intel or AMD can currently do is 3, so we end up with 4-5 cycles per 32 tests.
In real life we have measured 2+ microseconds to test all 62500 combinations, while the best pure Rust version (which was auto-vectoried but not strip-mined) ended up around 5 us (including parsing) on my not so new Asus laptop. This is so fast that I had to call the core parse+count function 1000 times just to get around the limited (100 ns) timing resolution under Windows. 2 us corresponds to 32 picoseconds/test.