After wrapping up the 2.12.0 release, I turned to optimising Freecell Solver
again. First, I profiled it using gprof, which indicated that 45.21% of the
time was spent in the function
freecell_solver_sfs_move_stack_cards_to_different_stacks . This function is
derived from really old code, probably back to Freecell Solver 0.2.0.
Looking at it I found that this function loops over all the cards in the
plateu twice - once to find a source card, and once to find potential
destination cards. However, since there are only four potential parent cards
(or 8 in case it's a two-deck game), then the second loop is wasteful.
The solution was to create a lookup for the cards in the columns based on
their rank, and loop over that. This was implemented here:
http://svn.berlios.de/viewcvs/fc-solve/trunk/fc-solve/source/freecell.c?r1=736&r2=1173
After I benchmarked it, the results were encouraging. The benchmark for before
the optimisation was:
{{{{{{{{{{{{
shlomi:$fcs/benchmark/before-opt$ time ./freecell-solver-range-parallel-solve
1 3000 100 -l gi
Started at 1229097758.883007
Reached Board No. 100 at 1229097759.691596 (total_num_iters=48460)
.
.
.
Reached Board No. 3000 at 1229097788.089174 (total_num_iters=1655270)
28.93user 0.25system 0:29.20elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+45028minor)pagefaults 0swaps
}}}}}}}}}}}}
And afterwards, it was:
{{{{{{{{{{
shlomi:$fcs/benchmark/after-opt$ time ./freecell-solver-range-parallel-solve 1
3000 100 -l gi
Started at 1229098045.144479
Reached Board No. 100 at 1229098045.700899 (total_num_iters=48460)
.
.
.
18.62user 0.03system 0:19.37elapsed 96%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2053minor)pagefaults 0swaps
}}}}}}}}}}
As you can see, it was a 10-seconds difference and roughly 33% of the run-time
was cut.
I think I'll try to optimise FCS further, while I'm in the neighbourhood.
Again, profiling is your friend.
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
Funny Anti-Terrorism Story - http://xrl.us/bjn7t
Shlomi, so what are you working on? Working on a new wiki about unit testing
fortunes in freecell? -- Ran Eilam
Received on Fri Dec 12 2008 - 09:45:28 IST