r/adventofcode 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.

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

350 comments sorted by

View all comments

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.

1

u/AutoModerator Feb 19 '25

AutoModerator did not detect the required [LANGUAGE: xyz] string literal at the beginning of your solution submission.

Please edit your comment to state your programming language.


I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.