Hi Mr. Parker!
On Thursday 22 April 2004 07:26, Randall Parker wrote:
> Running freecell-solver-range-parallel-solve.exe on Windows 2000 and
> Windows NT. The exe was built with MSVC v6.
>
It would help to know what is the exact command line that you are using. The
default (i.e: configuration-less) Freecell Solver command line does not
perform very well on many boards. One can configure it at run-time to use a
configuration that is better performing on average by specifying a lot of
command line options. (Check for example the files under the path
"Presets/presets" in the Freecell Solver distribution).
Now, since such long command lines are not very user-friendly, and because I
think Windows cannot handle such long command lines, FCS 2.8.0 introduced a
few usability features. One of them is the --read-from-file option (see the
--help display or the USAGE) file that can read command line options from a
file. The other are the command line presets (the "-l" flag), which work only
if you set up the presets directories correctly. This is much easier to do on
UNIX than on Windows, but it is still doable on the latter.
> I'm running thru many Freecell game numbers and occasionally hitting
> game numbers that use large amounts of memory. In the NT and Win2k
> Task Manager a small number of games take a long time (a minute or 2)
> to be solved. the Mem Usage column gets up to about 230 Megs on some
> game numbers but the VM Size gets up to 1.2 Gigs and more. I have to
> cancel out of a few of the worst of them because the swap disk doesn't
> go higher than 1.4 gigs.
>
Well, you can easily limit the number of boards Freecell Solver scans before
it gives up. This way it won't go berserk on your memory. To limit it to
100,000 iterations say:
$ freecell-solver-range-parallel-solve 1 32000 1 -mi 100000
Of course, 100,000 states consume much less than the amounts of memories you
mentioned. On my previous 320 MB system, I could easily handle limits of
millions of states and more.
It still sounds like you haven't used anything more sophisticated than the
default configuration.
> I think a lot of memory fragmentation is going on. I'd like to
> understand why this happens. Is memory allocated on one long deep
> stack? Is the Freecell algorithm deeply recursive?
>
OK, let me explain. Freecell Solver uses a Depth-First-Search scan. Thus, it
is by definition recursive. There are two variants of this: "Hard DFS" and
"Soft DFS". Hard DFS uses the processor's recursion stack. Soft DFS uses its
own stack that is allocated out of the heap (using malloc/realloc/free). Soft
DFS is the default. Note that Soft-DFS is also recursive, but it's a userland
recursion.
Now, there's also the states collection which is by default a hash, whose
elements are either individually malloced or allocated out of memory pools
(which in turn also use malloc). There's also the stack collection in case
you use INDIRECT_STACK_STATES which is similar. And there may be some other
data structures involved. (check the definitions of the "instance",
"soft_thread" and "hard_thread" data structures in "fcs.h").
> I'm also wondering what the INDIRECT_STACK_STATES versus
> COMPACT_STATES flags do.
>
Well, the states in COMPACT_STATES are basically one MAX_NUM_CARDS_IN_STACK+1
stacks one after the other. That way, each state always occupies a constant
amount of memory, which may be quite large, and also increases a lot as the
number of stacks and the maximal number of cards per stack increase.
In INDIRECT_STACK_STATES (which is actually more compact than COMPACT_STATES),
the states are a vector of pointers to stacks. These stacks in turn are
registered in their own stack collection. It used to be slower than
COMPACT_STATES, but after a few algorithmic optimazations, it became somewhat
faster. Thus, it is now the default.
> Also, do you happen to know how from the Microsoft NMake command to
> pass a definition of either of those flags down to the compiler?
>
You can use cl.exe's /D[MACRO][=[VALUE]].
Hope it helps. To further your understanding, you may wish to read the
Freecell Solver architecture document:
http://fc-solve.berlios.de/arch_doc/
Regards,
Shlomi Fish
---------------------------------------------------------------------
Shlomi Fish shlomif_at_iglu.org.il
Homepage:
http://shlomif.il.eu.org/
Quidquid latine dictum sit, altum viditur.
[Whatever is said in Latin sounds profound.]
Received on Thu Apr 22 2004 - 03:53:32 IDT