Re: Incremental Data Structures

[David Mechner <mechner@xxxxxxxxxxxxxxxxx>]

Matt Gokey wrote:
> I took a look at your implementation.  It looks like a pretty
> straightforward design and easy to use, but I would think its 
> performance in a search examining many positions would not be 
> all that good.   Could you comment on your revertable system's 
> performance characteristics with regard to memory usage, memory 
> fragmentation, and CPU cycles?  Thanks in advance, Matt.

Tim gave the real answer - we don't know - but I'm curious what's behind
your intuition. As Tim pointed out, the biggest factor affecting the
savings of caching values instead of recomputing them will be the
proportion of the values that change. But even in the worst case, where
all the objects change value, considering the per-object cost of caching
and reverting vs. recomputing, it's hard to see how caching could be any
worse. 

At least in our program, the algorithms we use to generate the objects
that make up our state are /extremely/ computationally expensive
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
revertable system is favorable (requires 1/2 the de/allocations per
state traversed over freeing and regenerating everything on each state
transition). 

-David

-- 
David A. Mechner            Center for Neural Science
mechner@xxxxxxxxxxxxxxxxx         4 Washington Place, New York, NY 10003
212.998.3580                http://cns.nyu.edu/~mechner/