Day 15 Optimization

[blairfrandeen]

Run time for day 15 part 2 is relatively slow. There are two approaches I could take to optimize it:

1) Come up with a more clever solution to find the coordinates of the one spot that isn't covered by the sensors. I think I heard it has something to do with the centroid of all the sensors around it, since there are bound to be several sensors that are equidistant from that point, and the point is just one square out of the sensors range. 2) Learn something about multithreading & concurrency in Rust, while keeping my existing solution mostly intact. The time required to run this is due to needing to iterate through all rows of the puzzle until a row with missing coverage is found; it seems that having several threads all iterating through separate groups of rows should be quicker.

[blairfrandeen]

My plan here is to use this as an exercise in multi-threading. To start, I'm going to refactor so that the program is a little bit cleaner, with the following goals: 1) Write a parsing function that returns sensors & beacons, separate from main. 2) Write separate functions for part 1 and part 2. These functions should take parameters so that the test input works as well. 3) Write test functions for part 1 and part 2 that run the test input. 4) Write benchmarking tests for part 1 and part 2.

Once this is done I'll go ahead and add in some multi-threading. The plan for this is to spawn individual threads to look through chunks of the rows I need to seaerch in part 2.

[blairfrandeen]

Got benchmarking working. I ran it for part 2 with the full input:

test day_15::tests::bench_part_2 ... bench: 812,836,819 ns/iter (+/- 1,120,760)

Not going to run that again, I'm not sure how to limit the number of cycles. Doing this took a few minutes of wall time. Maybe it's time to learn about how to manually time a function. Running it on the test input gave 2,186 ns, which may be useful as I try multi-threading, but I doubt a solution with only 20 rows will have much improvement when split into several threads.

Simple enough with the following lines:

use std::time;
//..snip
pub fn main(contents: String) {
//...snip
    let start_time = time::Instant::now();
    println!("Part 2: {}", part_2(0..=4_000_000, &sensors, &beacons));
    let end_time = start_time.elapsed();
    println!("Part 2 completed in {} seconds.", end_time.as_secs_f32());
}

It turns out that running this in release mode is an order of magnitude faster! Running the puzzle with cargo run 2022 15 finishes part 2 in ~12.6 seconds, and running cargo run --release 2022 15 finishes in 0.89 seconds! Makes me feel less bad about this solution, but let me continue with threading and try to do better anyway.

[blairfrandeen]

I'm working on refactoring part_2(), including some clean-up with the borrowing functionality that it requires for the range it searches. The first thing I'll want to do is to split the rows it has to search into several sub-ranges that I can pass to the threads I'm going to crate, so I'm writing a split_range() function that takes a single range, and a num_splits: u32 argument and returns a vector of ranges. Ideally all sub-ranges will be the same size, but since we live in a non-ideal world the sub-ranges will not all be the same, so I'll put all of the extra elements in the last range for now:

    #[test]
    fn test_split_range() {
        assert_eq!(split_range(1..=100, 10).len(), 10);
        assert_eq!(split_range(1..=10, 3).len(), 3);
        assert_eq!(split_range(1..=10, 3)[2], 6..=10);
    }

And I can never get enough time to myself.

[blairfrandeen]

Putting a pin in this one, since I'm afraid getting it to work will require a bit more of a re-write than I am willing to do. I think the problem I'm having is that the &sensors and &beacons are getting owned by the threads I'm trying to spawn. The errors I get:

error[E0521]: borrowed data escapes outside of function
  --> src/day_15.rs:58:9
   |
51 |       beacons: &HashSet<Point>,
   |       -------  - let's call the lifetime of this reference `'2`
   |       |
   |       `beacons` is a reference that is only valid in the function body
...
58 | /         thread::spawn(move || {
59 | |             let start_row = *range.start();
60 | |             let end_row = *range.end();
61 | |             println!("Checking from {} to {}", &start_row, &end_row);
...  |
70 | |             }
71 | |         });
   | |          ^
   | |          |
   | |__________`beacons` escapes the function body here
   |            argument requires that `'2` must outlive `'static`

I've spent a lot of time over the last few days reading about borrowing & ownership, which makes me want to start over on a lot of the AOC work I've done so far. What I think the solution here is that I need to be using Rc<T> or Arc<T> for the static data that needs to be passed to the threading function.

Running the rustc explainer for this error isn't too helpful. Maybe it would work if I were passing in owned data, but that would make the threading more awkward than it is.