Forking (= Multiprocessed) Freecell Solver-based Solver
- 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:
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 !
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 .