On dynamic storage allocation
Both
Oscar and
Symbolic use dynamic storage allocation for many purposes, and this feature helps with the goal of avoiding fixed limits on search depth, game length, etc. The difference between the two programs is that
Oscar has its own heap while
Symbolic uses a heap controlled by C++ library routines.
Oscar and
Symbolic dynamically allocate memory only when necessary and recycle the memory using their own routines whenever possible. The result is that beyond a small fraction of a second after program start-up, the library/system overhead for dynamic allocation is far too small to be measurable; it's something like O(log log N). When the program shuts down, there is also a very small library/system overhead where the program gracefully releases all of its dynamically allocated objects, because
Oscar and
Symbolic are good boys and play nicely with others.
Recycling is done among dynamically allocated nodes of the same type. Each node has prev/next pointers, and each node belongs to a list which has head/tail pointers. A node is recycled by detaching it from one list (usually at the tail) and attaching it to second list (also, usually at the tail). Simple stuff; easy with C++ templates, a bit more verbose with regular C code.
Were you around in the mid 1970s? There was a popular dance called "The Bump" where two dancers would bump tails to exchange momentum. It's the same thing with
Oscar and
Symbolic; the tails of two lists are bumped to transfer an allocated node.
Code: Select all
// Save the move
if (positionptr->freemovelistptr->count == 0)
MoveListAppendNode(positionptr->freemovelistptr, MoveNodeNew());
MoveNode * const movenodeptr = MoveListDetachTail(positionptr->freemovelistptr);
movenodeptr->move = move;
MoveListAppendNode(positionptr->usedmovelistptr, movenodeptr);