I also move the determination of auto title loan Indiana n_cups out of the loop, and instead provide it as a parameter of the do_move() function, but it doesn’t really affect the running time either

My guess is that it’s taking so long because of inserting three elements into the vector, which has to make a copy of all the elements that come after the insertion. I am fairly bad at data structures, but I suspect that this might be one of the rare cases where it’s advantageous to use a linked list, since that has quick insertion in the middle. However, before I rewrite the whole thing I change the wasteful 3? insert, to split the vector at the insertion point, and append the three moved cups before sticking the second half of the vector back on:

Rust’s standard library does include a linked list, but it’s a doubly linked list and doesn’t have APIs for detaching and inserting whole ranges, as far as I can tell.

I wonder if, before resorting to rewriting the program with a different linked list data structure from a package, I should profile the existing program to find out what is taking so long. I suspect the insert, but it could be something else, like searching the vector for the destination cup.

I google “rust profiling tools” and land first on cargo-profiler. It looks really easy to install and use, but unfortunately it crashes if you have a digit in the path of your program:

This bug is in a giant-ass regular expression that doesn’t give me a lot of confidence in the robustness this tool. On to the next one.

The cpuprofiler package has pretty decent getting-started documentation. It requires gperftools , so I first install my Linux distribution’s gperftools package, then add this preamble to my program:

I change the number of moves to 1000 and run the program. A 23.profile file appears in my project directory!

So I was wrong. It’s not the insert that is causing the problem at all, and I probably don’t need to use a linked list! The problem is searching the vector for the destination cup.

Interestingly, rewriting that loop not to use position() , cuts the expected running time almost in half, to a little over two days:

However, either of (a) using enumerate() or (b) writing the loop without an iterator at all ( for ix in 0.. and indexing cups[ix] ) increases the expected running time back up to the same neighbourhood as using position() . I’m a bit surprised at that, but I file it away and move on.

According to the documentation, I can then use the pprof tool to check which lines in do_move() are hot (output slightly truncated):

Although I’m pleasantly surprised that profiling a program is so easy with Rust and Cargo, I’m starting to think that profiling and optimizing this code is a red herring, because if I keep this algorithm, then no matter what I’ll still have to search through the vector to find the destination cup, and I’m not sure it’s possible to do that any faster. I can see two possibilities from here: either there a different algorithm that will run faster; or there is a mathematical trick that can be used to figure out the answer in an easier way, like on Day 13.

I try changing the number of cups to 20 and the number of moves to 200, and printing out the order of cups every move, to see if I can see any patterns, but after staring at it for a while, I still don’t see anything.