Hi all,
I'd like to report on my progress in working on Freecell Solver since the 4.0.0
release and the "Travis CI" work.
1. Micro-optimisations.
=======================
I applied quite a few micro-optimisations and code cleanups to the Freecell
Solver trunk, partly inspired by the results of the find-ids.rb script. I
recall optimising the Freecell vs. Simple Simon reverse-cards-lookup as well as
getting rid of unused function parameters in the C code.
One thing I learned in the process is that when doing a before-vs-after timing,
one should also time the before-the-changes version again because the system
may now run it slower (or faster).
2. Optimising the solving-and-verifying the first 32K deals process.
====================================================================
I next set out to try and optimise the process of solving the first 32,000
deals with the catch that they are also verified for correctness using
http://fc-solve.shlomifish.org/verify-code/ .
At the start of the process it took 10 minutes. Then I decided to get rid of
excessive process forking/execve/pipelines and embed the C routines for
generating the output inside the program:
https://github.com/shlomif/fc-solve/blob/master/cpan/Games-Solitaire-Verify/benchmark/benchmark-no-backticks.pl
This improved the speed significantly. In the process I discovered this
apparent bug in glibc and had to work around it:
https://sourceware.org/bugzilla/show_bug.cgi?id=19230 .
I also consulted Devel-NYTProf in trying to find potential hotspots in the Perl
5 code of the solving process and did some relatively minor optimisations this
way.
A more significant optimisation came after paraellelising the process using GNU
make's -j flag , and some scripts to wrap it and now I'm down to about 3
minutes, which still seems quite a long.
One option would be to port Games-Solitaire-Verify to a different and
faster programming language in its entirety, but I'm not sure if this will be
worth the trouble of only making the solve+verify faster which I don't care
about as much as the raw solving process.
3. The finding individual scans that solve slow deals quickly branch.
=====================================================================
Now I have some exciting (at least for me) news: I found an effective way to
speed up the solving process. What I did was:
1. Sort the output of freecell-solver-fc-pro-range-solver by their solution
iterations count for the first 32K deals for the -l as process. I used
pipelines like the following:
$ cat ~/Backup/Arcs/fcs-l-as-mod-11.txt | perl -lanE \
'print $1 if /\Q[[Num Iters]]=\E(-?\d+)/' | cat -n | sort -n -k 2 | gvim -
2. Sought individual scans (= "Soft-threads" in Freecell Solver terminology)
that solved the longest deal or deals within a short time. Later I tried to
find searches/scans that solved a certain number of deals (or the numbers below
it) within as shortest number of iterations.
3. Place these scans in strategic places in the beginning of the --prelude of
the modified , switch-tasking, aggregate search.
====
The relevant code and experimentation can be found in these places:
*
https://github.com/shlomif/fc-solve/tree/master/fc-solve/scripts/TEST_OPTIMIZATIONS
*
https://github.com/shlomif/fc-solve/blob/master/fc-solve/scripts/FindSeed.pm
3.1. Optimising the scans process.
==================================
I again optimised the scan process by removing excessive forks/pipelines/execve
by creating the summary-fc-solve C executable, and later by parallelising the
code using this CPAN module and the underlying IO-Async framework:
*
https://metacpan.org/release/Process-Async
I ran into some issues with that module in part because it didn't serialise
Perl data structures automatically and didn't handle whitespace or newlines
well, but they were eventually resolved.
4. Contemplating the upcoming "Gone Wild" branch.
=================================================
In the "Gone Wild" branch, which I'm still undecided on, I'm planning to break
some backward compatibility such as the output of trailing whitespace,
handling "10C" card strings instead of "TC", and the unnecessary code to emit
states in non -p form, in hope of making Freecell Solver faster and lighter. I
hesitate to do that due to these articles:
*
http://blogs.perl.org/users/aristotle/2013/06/decade-scale.html
*
http://www.joelonsoftware.com/articles/APIWar.html
But it's possible doing it in a separate branch won't hurt much for now.
( The name "Gone Wild" is inspired by the name of this Reddit subreddit which is
not safe for work (NSFW) / pornographic / etc.:
https://www.reddit.com/r/gonewild - you have been warned.)
-----------------
Regards and happy holidays,
-- Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
Optimising Code for Speed - http://shlom.in/optimise
One of my most productive days was throwing away 1,000 lines of code.
— Ken Thompson (Attributed)
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Fri Dec 18 2015 - 12:00:36 IST