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

Forking (= Multiprocessed) Freecell Solver-based Solver

Expand Messages
  • Shlomi Fish
    Hi all! Today I took a break from converting the build-system of Website Meta Language ( http://thewml.org/ ) to CMake (which is now also used by Freecell
    Message 1 of 1 , Feb 20, 2010
      Hi all!

      Today I took a break from converting the build-system of Website Meta Language
      ( http://thewml.org/ ) to CMake (which is now also used by Freecell Solver)
      and while I waited for my Mandriva packages upgrade to finish, I started
      writing a fork()-based multi-processed solver program:

      http://en.wikipedia.org/wiki/Fork_%28operating_system%29

      fork() is a system call that duplicates the current process, creating a parent
      and a child. What my program does is create several child processes, each one
      with a single bidirectional pair of pipes for communicating with the master
      process (the parent). Each of these processes solves a range of boards that it
      received from the master process, while reporting the statistics back to it,
      by communicating with it using the pipes.

      It took me quite a lot of time to get everything right. The main thing that
      delayed me was the fact that I didn't realise that the select system call (see
      http://en.wikipedia.org/wiki/Select_%28Unix%29 ) also reported filehandles
      that became end-of-file, and so the read of the protocol's response structs
      from them silently failed which made the master process hang. Changing the
      read to check that it read exactly sizeof(response) bytes solved this problem.

      Then I benchmarked it and the results were encouraging:

      {{{{{{{{{{{{
      Started at 1266685041.258715
      Reached Board No. 4000 at 1266685052.702632 (total_num_iters=2232774)
      Reached Board No. 8000 at 1266685064.422297 (total_num_iters=4507587)
      Reached Board No. 12000 at 1266685075.570034 (total_num_iters=6693689)
      Reached Board No. 16000 at 1266685088.051940 (total_num_iters=9077159)
      Reached Board No. 20000 at 1266685099.088107 (total_num_iters=11274791)
      Reached Board No. 24000 at 1266685110.548054 (total_num_iters=13519808)
      Reached Board No. 28000 at 1266685122.337970 (total_num_iters=15802397)
      Unsolved Board No. 11982 at 1266685076.187721
      Finished at 1266685135.302799 (total_num_iters=18253266)
      }}}}}}}}}}}}

      Finished at 94.04 seconds (solving 340 boards per second) - versus the multi-
      threaded version which took 95.69 seconds, an improvement of over 1.6 seconds.

      I ran it like that:

      {{{{
      ARGS="--worker-step 16 -l by" PROG=./freecell-solver-fork-solve \
      bash scripts/time-threads-num.bash 2 4
      }}}}

      Currently the multi-processed version of the solver is not installed, but
      rather only compiled locally.

      Enjoy and happy upcoming http://en.wikipedia.org/wiki/Purim !

      Regards,

      Shlomi Fish

      --
      -----------------------------------------------------------------
      Shlomi Fish http://www.shlomifish.org/
      What does "Zionism" mean? - http://shlom.in/def-zionism

      Deletionists delete Wikipedia articles that they consider lame.
      Chuck Norris deletes deletionists whom he considers lame.

      Please reply to list if it's a mailing list post - http://shlom.in/reply .
    Your message has been successfully submitted and would be delivered to recipients shortly.