Hi all!
A few days ago, I was bored, and decided to work on Freecell Solver in order
to avoid being bored. What I decided to do was to split the various
ptr_state_with_locations, which are currently defined as:
struct fcs_struct_state_with_locations_t
{
fcs_state_t s;
fcs_locs_t stack_locs[MAX_NUM_STACKS];
fcs_locs_t fc_locs[MAX_NUM_FREECELLS];
struct fcs_struct_state_with_locations_t * parent;
fcs_move_stack_t * moves_to_parent;
int depth;
/* More stuff here. */
}
Into a separate fcs_state_t which in turn is associated with a separate struct
fcs_state_extra_info_struct which contains the rest of the information about
the struct, that is not necessary to uniquely identify. Thus, in the context
of handling the dictionary of states one may now think of fcs_state_t as a key
and of fcs_state_extra_info_t as its value. This analogy is carried forward
with the code.
To do this, I started a new branch in the Subversion repository -
http://xrl.us/beiwb6 in order to perform this relatively large-scale
refactoring. I initially thought I could use
http://www.emn.fr/x-info/coccinelle/ (a tool for semantic patching) for that,
but I found it too poorly documented, and too hard-to-get-right, and could not
get it to yield even basic results. So I ended up doing the conversion semi-
manually and by using several hacky Perl scripts I wrote for the purpose.
(Which you can find under scripts).
That way I was able to convert most of the code to use the new key/value
scheme. I think I spent most of my time debugging the complex macros which had
to be edited in-place to adapt to the new scheme.[Macros]
However, as I was debugging the code, I discovered a bug: apparently the
"Iteration: $NUMBER" lines in the -s -i display were not consistently and
immediately ascending. And as I discovered this problem existed in the
Subversion trunk (and the latest Freecell Solver release), where my key/value
pairs did not hold. So I had to fix it there first.
I switched to the main Subversion branch and worked on fixing this bug. It
took me a long time because the Soft-DFS scan code lately incorporated many
ultra-micro-optimisations that made it hard to get right. Today however, I was
finally able to re-order all the operations there, so the order of iterations
will be acceptable in all my tests. As a result we now have:
1. More tests.
2. More optional TRACE0(...) calls in scans.c that can aid in debugging if
toggled on using a compile-time *and* setting an environment variable.
3. A fixed code.
4. All previous tests passing.
-------
I should note that this is one area of the cleanliness of the Freecell Solver
code that I'm also unhappy with, and would like to remedy, but couldn't
because I was fixing bugs.
Fixing these bugs reminded me of this quote by Brian Kernighan:
http://fishbowl.pastiche.org/2003/10/08/sig_quote_of_the_day/
(
http://en.wikiquote.org/wiki/Brian_Kernighan )
I really need to make the Freecell Solver code less clever if I don't want to
spend so much time weeding out such bugs from it.
So what I need to do now is merge the differences from the trunk to the new
key-value branch and go on with the rest of the key-value conversion.
Regards,
Shlomi Fish
[Macros] - I'm no longer sure having such long macros that are expanded inside
each one of the test functions (in freecell.c, etc.) is a good idea, because
they probably occupy a lot of memory, and as a result cause many cache misses.
I'd like to try and see if converting them to functions would speed things up
(and also facilitate future maintenance).
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
What does "Zionism" mean? - http://xrl.us/bjn8u
<mauke> I'm not interested in what you're doing; what are you trying to
achieve?
<PerlJam> mauke: I'm trying to achieve world peace and this regex is
the last thing standing in my way! ;)
Received on Mon Mar 09 2009 - 10:22:32 IST