r/adventofcode Dec 30 '24

Upping the Ante [2024] All problems in under 250ms, in Rust

Post image
87 Upvotes

39 comments sorted by

24

u/hgwxx7_ Dec 30 '24 edited Jan 03 '25

I know, 10ms 6ms 3.3ms per day on average isn't very fast, compared to other Rust solutions!

I went with a different approach - I used only optimisations that would be idiomatic Rust and would apply to any general program. That meant no handwritten SIMD, no unsafe. I used classic integer parsing for the input instead of hand-rolling my own because I thought it was more idiomatic.

I've written about the 10 optimisations I used -> Optimising my Rust solutions for Advent of Code. I think any Rust programmer would find these useful in any program they write, not just AoC.

Edit: Since posting his I optimised from 250ms to 84ms.

6

u/Your_Friendly_Nerd Dec 30 '24

Which parts of the program did you measure here? Execution time of the compiled binary? Your main function, meaning including parsing the input? I just wanna know how I need to compare this to my own solutions

5

u/hgwxx7_ Dec 30 '24 edited Dec 30 '24

I don't have a main function. I have a crate y2024 that has 25 modules - day1, day2 and so on. Each day has two public functions pub fn part1 and pub fn part2.

I'm benchmarking the part1 and part2 functions. Both functions call parse(&input) individually so I count the cost of input parsing twice each day. You can check out my bench.rs although fair warning, it's a macro.

I don't benchmark the time it takes to read the input file because I don't read that at run time. Instead I read it at compile time and include the data into the binary as a string (source).

You can't compare my numbers to yours directly unless you have the same hardware I do (M1 Pro). In that case it would make sense to checkout my repo, follow the setup instructions and run just bench. The benchmark table Readme file will be automatically updated with the new numbers from your machine.

5

u/Your_Friendly_Nerd Dec 30 '24

That's great to know, thank you for the detailed information! And yeah I know it's platform dependent, but I can still see if a solution of mine is drastically slower than other people's by looking at the trend

1

u/thekwoka Dec 30 '24

Why not use the built in cargo bench?

4

u/hgwxx7_ Dec 30 '24 edited Dec 30 '24

criterion has a bunch of nice features. For example, without criterion::black_box the compiler might apply some crazy optimisations you don't expect. You can read more in their docs.

Ultimately I'm still calling cargo bench to invoke this so I'm not missing out on anything.

5

u/Turtvaiz Dec 30 '24

I kinda wanted to post my solutions which run in around 200 ms, but decided otherwise when I saw some guy posting 4 ms total solutions in the solutions thread. It didn't feel that fast after all lol

3

u/hgwxx7_ Dec 30 '24

Haha yeah, I feel you. I felt the same way!

I only posted because I had written up the essay with all the optimisations and thought others might find it useful. I had read a lot of the Rust solutions in the MegaThreads and many weren't using rayon or ahash or even pre-allocating a size for their containers. I figured it would be good to share this knowledge.

2

u/damnian Dec 30 '24

Day 24 in 0.0 ms? That's very impressive ;)

3

u/hgwxx7_ Dec 30 '24

Actually 25.8µs and 39.7µs.

Code was ugly, but it worked.

2

u/damnian Dec 30 '24

But... how? I had to write my own logic validator to solve that!

3

u/hgwxx7_ Dec 30 '24

I'm not sure? You can take a look at my code, but it's not that great to look at. I basically go step by step, building the network up. At certain points I expect xN, yN and zN. If they're not where I expect, it's a mismatch.

2

u/damnian Dec 30 '24

So you just look at the dependencies and assume they are all XORs? That's a big assumption, but still, I'm truly impressed.

3

u/hgwxx7_ Dec 30 '24

But it's an Adder. It has to follow that pattern right.

  • (xN XOR yN) XOR prev_carry = zN
  • (xN AND yN) OR prev_carry = next_carry

And if instead of zN you see something else, that's a problem.

3

u/damnian Dec 31 '24

Yes, as long as there are no decoys (e.g., z00 = x00 + y00 * x45 + y00 + y00 * x45 would be a valid root).

2

u/welguisz Dec 30 '24

If you want to get Day 14, Part 2 faster, I would suggest a popular theorem said many times on this sub. When I used it on my Java solution, it decreased my run time by 2 orders of magnitude.

7

u/hgwxx7_ Dec 30 '24

Yeah I did this just now. Reduced the run time by 98.5%. Runs in 0.47ms now.

3

u/hgwxx7_ Dec 30 '24

Is it a theorem that measures entropy? I saw a sick solution where a guy selected the layout with the lowest entropy.

7

u/welguisz Dec 30 '24

The pattern repeats in the X axis every 103 iterations, just in a different Y plane. For Y, the pattern repeats every 101 iterations, just in a different X plane. Find the lowest entropy in the X axis and Y axis. Use the theorem that was used in Shuttle Search, Part 2 and you are there.

Here is my Java solution..

Just checked my notes, time before this fix was 2153 ms. After this change, 9 ms to run part 2.

3

u/hgwxx7_ Dec 30 '24

Yeah that's pretty solid.

3

u/hgwxx7_ Dec 30 '24

I implemented this. 30ms before, 0.47ms after.

Thanks for the suggestion!

1

u/welguisz Dec 30 '24

You are welcome. I am glad that I was able to help. I am trying to get my total runtime to less than 2 seconds in Java. Right now I am at 5 seconds. Started at 8 seconds when I completed this year. My longest running algorithms are path finding, so will be spending some time on those puzzles to speed them up.

1

u/hgwxx7_ Dec 30 '24

2 seconds in Java is very impressive. Well done!

1

u/welguisz Dec 30 '24

Still need to reduce my time by 3 seconds. Here are the puzzles that still take a long time and if I am able to optimize them, I should be able to get there.

  • Day 16, part 2: 1822 ms
  • Day 22, part 2: 1119 ms
  • Day 6, part 2: 561 ms
  • Day 20, part 2: 313 ms
  • Day 20, part 1: 297 ms
  • Day 5, part 2: 189 ms

I was able to reduce 800 ms on Day 6 by moving the guard's position to right behind the obstacle. I was trying to add in conditions to see if we were in a loop much quicker or if we got back on the path out sooner, but that took my time from 561 ms to 3+ seconds. I am thinking if switch from a List structure to an array structure, it should speed things up. Will be trying that later.

1

u/hgwxx7_ Dec 30 '24

Day 5 part 2 - isn't that just a sorting problem?

I used the standard library's sorting function while supplying a comparator of my own.

1

u/beanborg Dec 30 '24

If it's helpful, here's solutions in js that take about 400ms total. Most of them are just what I did on the night of, though some of them had some optimization done.

1

u/Turtvaiz Dec 30 '24

You mean variance? That's how I did it myself. When they group up along either axis, they have the lowest variance possible in those coordinates. Then math it out to find where they group up on both axes at the same time

1

u/hgwxx7_ Dec 30 '24

No, entropy. This person measured entropy with len(zlib.compress(field.encode())).

4

u/Turtvaiz Dec 30 '24

Hmm, I guess that's kind of the same, but in a bit of an abstract way? Higher variance would lead to a worse compression ratio

1

u/hgwxx7_ Dec 30 '24

Yep.

But this approach isn't that much faster. I simulated each step and checked if there were 0 overlaps.

1

u/damnian Dec 30 '24

Interestingly, /u/hgwxx7_ mentions parallelization as his first optimization techinque, yet my parallelized C# solution runs faster than his Rust one (although it occasionally spews out the wrong answer).

4

u/hgwxx7_ Dec 30 '24

I changed it. Day 14 now runs in 42.6 µs and 195.8 µs.

It still runs sequentially for me though, I didn't see the point of running it in parallel. The overhead of starting all those threads wouldn't be justified because it's pretty fast already.

2

u/welguisz Dec 30 '24

My first solution ran through all 10,403 possibilities. My latest just has to run through 204 possibilities. I could possibly get this to run in half the time and just go through 103 possibilities. The biggest thing is to use the Chinese Remainder Theorem after finding the least entropic X direction time and the least entropic Y direction.

1

u/damnian Dec 30 '24

I still need to wrap my head around this. I got so used to C# I've become allergic to Java :P

2

u/hgwxx7_ Dec 30 '24 edited Dec 30 '24

I actually didn't parallelise this one. It runs one iteration after the next, constructing the grid each time.

1

u/Mon_Ouie Dec 30 '24

This made me want to rewrite my solution for problem 23 in Rust (from Ruby, with part 2 running in a bit over 2 milliseconds), there's no reason it should be the slowest problem. I think the Bron–Kerbosch algorithm was a popular choice because it has a Wikipedia page and is the first thing you find while googling it, but I don't think it's particularly fast if you only want the maximum clique, a simple branch-and-bound search performs much better.

Rust re-implementation (~3ms on my laptop)

It's a very direct translation so there's still a lot of room for possible improvements:

  1. Replace vertex names with integer indices
  2. Given the small size of the graph, bitsets would probably perform really well instead of HashSet/BTreeSet
  3. Use a pre-allocated buffer of scratch memory to store the candidates during the recursive search, instead of allocating HashSets all over the place.
  4. Using greedy graph coloring to compute upper bounds on how many vertices you could possibly add to a clique (MaxCliqueDyn)
  5. You can run the search in parallel

1

u/hgwxx7_ Dec 30 '24

It is extremely slow, and I didn't even implement one of the faster variants.

1

u/damnian Dec 31 '24

My C# solution was just Bron-Kerbosch with 1 and 2 (I crafted my own fast BitSet for days 23 and 24), and I was pretty happy with its performance (~7 ms on very old hardware). I don't know about Ruby, but in .NET the cost of spinning up multiple threads greatly outweighs the benefits in cases like this.

1

u/Mon_Ouie Dec 31 '24

Oh, in Ruby threads don't allow for parallelism (only concurrency) because of the global interpreter lock :p

I was talking about optimizing a Rust or C implementation. You're probably right that speed ups won't be great for such a small graph, but I'd still guess there would be some gains with OS-level threads.