Freecell Solver 0.2 managed the states collection as an
array in which the states' structs appeared one adjacent
to the other. I also passed the entire struct as a parameter
to solve_for_state
. When I tried to run it on
Microsoft Windows NT, I realized
that sometimes the program ran out of stack. This was because it
descended into a relatively large depth, while passing all
the structs in it. To avoid it, I decided to pass pass pointers
to the stacks, and to store the states as an array of pointers.
I did not want to individually malloc the structs, because I knew memory was often allocated in powers of 2, and so I can have a lot of it wasted. I first tried to allocate the states by allocating them from the end of one array that was realloced when necessary. However, I realized (after a long and frantic debugging session) that the newly allocated array may not retain its original place in memory, thus causing the pointers that were already collected to become defunct.
To avoid this, I devised a better scheme, in which I allocate the states in packs of constant size, and allocate more packs as necessary. Since the packs contain more than one state, and their size can be adjusted to accommodate for the whims of the underlying memory management, it was a good solution as could be found. [4]
With this management of memory, I converted the states collection to use an array of pointers instead of an array of structs. Not only did it consume less stack space, but it also ran much faster. The reason is that swapping and re-organizing pointers (which take 4 or 8 bytes each) is done much more quickly than re-organizing large structs. Plus, passing pointers on the stack is more efficient than passing and duplicating entire stacks.
This time the algorithmic order of growth was not reduced, but still there can be a difference of heaven and earth between a large O(n2) and a small O(n2)...
[4] What I could have also done was to manage indices to the states inside the allocation block, instead of pointers. However, I preferred not to use this scheme, because I did not want the extra cost of looking up the real pointer from the index.