Another Significant (and Algorithmic) Optimization in the Trunk
- Hi all!
Profiling Freecell Solver using gprof yielded the following line:
% cumulative self self total
11.60 14.69 5.09 2592757 0.00 0.00
This was a significant percentage of the time. Inspecting this function, I
found that it was indeed coded sub-optimally: it looped over all the cards in
the columns, and then for each one checked if it has a parent in one of the
freecells. Back when I had seen it, I had decided to loop over the freecells
(which are generally significally fewer than the cards in the tableau), and
use the positions_by_rank reverse-mapping (already implemented for
fc_solve_sfs_move_stack_cards_to_different_stacks() ) to find their parents.
However, I didn't get to it immediately, and instead did other FCS-related
stuff (like the hashing tweaks). However, today I finally got to doing it.
Now, before I did it I needed to do some code-re-structuring Yak-shaving
1. I needed to add a re-usable context / baton variable to the states in the
derived_states_list, so they could be sorted accordingly. This was done to
preserve the order of the states from before the optimization.
2. I needed to make sure that the positions_by_rank allocation / calculation /
release/ caching is done globally for the state in the soft_thread because now
two of the move functions used it.
3. And naturally, many bugs crept along the way, but hopefully most of them
were caught by the automated test suite before being committed to the
repository. Investigating and solving the reported bugs was time-consuming
Anyway, now I've benchmarked it and here are the results:
1. Solving the MS 32K with "./configure -r --fc-only" after the optimisation
went down to 159.685534000397s (from 173.935693025589s before the
optimisation). So we saved over 14 seconds and 8% of the run-time and the
range solver now solves 200.393856590168 boards / second.
2. A regular "./configure -r" (without "--fc-only") yielded 186.891037940979s
down from 196.4514939785s , but against me, I can say that I was playing a
video at the same time.
It was a lot of work today, but it was worth it.
P.S: I learned about an Israeli job opportunity today from someone who works
there, and sent them my resume. I've been looking for a job for quite a while.
Wish me luck!
Shlomi Fish http://www.shlomifish.org/
"The Human Hacking Field Guide" - http://xrl.us/bjn8q
God gave us two eyes and ten fingers so we will type five times as much as we