Re: Incremental Data Structures

[Darren Cook <darren@xxxxxxxxxxxxxx>]

David Mechner wrote:

>> compared to simply copying values. I guess if your state is made up
>> mostly of static rather than dynamically allocated structures perhaps
>> the revertable system's memory allocation calls would offset this
>> savings, but our state (and I suspect the state of most big, complicated
>> programs) is mostly dynamically allocated, so again it seems that the

Rereading this I think I see why some of my caching experiments gave no
speedup. I use practically no dynamic memory allocation. The program
allocates a buffer big enough for the worse case at program start, or
locally in each function. This results in a lot of wastage, but as has been
pointed out before on this mailing list, memory is cheap, speed isn't.
Dynamic memory allocation is slow.

One problem I've had using 'worse-case' buffers in recursive functions is
needing a lot of stack. I can't always predict how deep it will search, and
have had stack overflow errors with a 2Mb stack. None yet with a 3Mb stack,
but on a quicker machine it can search deeper in the same amount of time.

>heap-allocation library.  My intuition about this technique is that the
>system would be quite memory intensive, use considerable cycles copying data
>chunks and cause considerable fragmentation resulting in somewhat frequent
>need to garbage collect.

One object I'm working on at the moment can do an incremental update when a
move is played, and some tests show it's about 10 times quicker than
recalculating from scratch. But I've had problems undoing those updates.
Storing the deltas as you suggest is one option. It can get very complicated
though, e.g. if the last move captured stones in two or more enemy chains,
while joining two friendly chains into one big chain.

An alternative is to write the state to a buffer, and read it back from a
buffer. The buffer is pre-allocated of course. This is similar to copying
the whole object, but if the object is 100Kb, and on average only 5% of that
is used, I'm expecting this way to be a lot quicker, as it will only write
5Kb to the buffer.

So the algorithm is:

  1.Store current object state to buffer (*A).
  2.Make move on board.
  3.Incrementally update the object state.
  4.(Analysis, possibly recursive).
  5.Remove move from board.
  6.Restore object state from buffer (*B).

*A: if buffer is full, set a flag (and write to a log so I know to make
buffer bigger).
*B: or if flag set, recalculate from scratch.


Darren