Loading ...
Sorry, an error occurred while loading the content.

Another Significant (and Algorithmic) Optimization in the Trunk

Expand Messages
  • Shlomi Fish
    Hi all! Profiling Freecell Solver using gprof yielded the following line: {{{{{{ % cumulative self self total 11.60 14.69 5.09
    Message 1 of 1 , Apr 26, 2009
      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
      (http://en.wiktionary.org/wiki/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.


      Shlomi Fish

      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
    Your message has been successfully submitted and would be delivered to recipients shortly.