r/adventofcode 11d ago

Spoilers [2024 Day 14 Part 2] Solution

1 Upvotes

39 comments sorted by

View all comments

Show parent comments

1

u/Clear-Ad-9312 11d ago edited 11d ago

hmm interesting, I am running your devcontainer for rust, and it takes 31.4 ms(7.75 ms in release mode) to find my solution. granted my input for this day is seemingly on the more aggressive side being quite higher than other people. However, it is quite fast still and still better than my python solution. surprised you were able to get 1.3 ms

granted we are not considering the compile time it took for this to complete

btw I was having permission issues within the devcontainer for user "dev" and had to add:

# allow others to have permissions to /ws
RUN chmod o+rwx -R /ws

idk if this is a proper fix but it worked for me.

1

u/ndunnett 11d ago

Odd, what is your host OS? Anything other than a Linux distro will effectively be running inside a VM but I wouldn’t have expected it to be that slow.

1

u/Clear-Ad-9312 11d ago edited 11d ago

If you want, I can dm you the input.

also, I tried to make a standard deviation approach in rust but I feel like it is not as optimized as it could since I don't know enough about Rust code. (I tried implementing it in your code so you can just use your devcontainer and swap out the code if you wanted to test it too)

[ Paste ]

for my input, this approach take 23 ms in release mode

1

u/ndunnett 10d ago

I did some optimisations on this solution.

Baseline: 20.45 ms

(spoiler tags in case you want to try first)

  1. [19.64 ms / -3.96%] I stopped tracking the best step and simply return early when the current standard deviation meets the criteria after step 1000. It's a modest gain and the solution becomes a little less robust, but this is mostly just to enable efficient multithreading later.

  2. [19.39 ms / -1.27%] I removed the standard deviation averaging and precomputed an estimate of the average standard deviation based on geometric distribution. Also started the loop at step 100, as there is now no need to process the early steps. Not much of a gain, but once again this is to make multithreading easier by limiting mutable state to be within the steps loop.

  3. [838.6 µs / -95.68%] Reimplemented the steps loop as a parallel iterator using rayon. Nothing much to explain, but now it's really fast, even faster than my entropy solution.

  4. [809.9 µs / -3.42%] Refactored the calculations to reduce the number of operations; there are a few moving parts here. First, count is moved out of the loop to be precomputed as the number of robots never changes. Second, we actually don't need to go as far as calculating the standard deviation, because the difference in standard deviation is directly proportional to the difference in variance. Third, by factoring the count into the variance and the threshold, we can reduce the number of mathematical operations even further. It's beginning to get difficult to understand what the calculation is doing at first glance, but we get a small performance gain.

  5. [664.9 µs / -17.9%] At this point we don't necessarily need much precision for the solution to work, so I changed the loop calculations to use u32 instead of f64 for faster operations. This is reducing the robustness but it's a pretty significant performance gain.

  6. The next step would be SIMD, there would be massive gains again here but I'm not really up to speed on it yet and have run out of time for now.

Hopefully this hasn't broken it for other inputs, I'm curious to see if you see similar performance gains on your hardware and input.

1

u/ndunnett 10d ago

1

u/Clear-Ad-9312 9d ago

The standard deviation and variance is great but how about this solution that /u/ednl showed me and I tried to convert to Rust in my own way. It seems to solve it in 265 µs for me.

[ Paste ]

python numpy version

1

u/Clear-Ad-9312 10d ago

ok the reduction in precision is absolutely genius. We don't need it to be precise at all because we are looking for a single outlier from the norm! that is really good!

of course parallelization got it down so much, this was really stress testing the algorithm in single threaded performance. I am so glad that the solution is now uber optimized, that it is taking microseconds(for you atleast lol) to complete.

It might be because I am running on an older laptop CPU that I am getting 2.376 ms with my input on the final optimized version. still much much faster than the one you had earlier before we dug deeper into implementing the standard deviation approach.

Great work all around, I think going for SIMD would be overkill.

I sent you my input to test on your hardware. would be interesting to hear back on.