Current Questions on Garbage Collection and Chaos

My investigations into garbage collection and chaos have produced two main areas of interest so far. Both are motivated by the previous question of "how can one choose the points at which to perform collections wisely?"

First, garbage collection actions by definition, have no effect on execution from the standpoint of semantics. Collection actions replace the memory graph with a subset of the same memory graph, which is isomorphic with respect to the root set. Therefore, collections can be performed anywhere during execution. Typically, there is a maximum size which garbage collection must keep the program under.

Assuming that the cost of collection is roughly equivalent to the number of objects preserved, then we can usually have a profound impact on the total cost of collection depending on exactly where we perform collections. There are three general schemes for doing this:

1) The perfect world, where we know the execution ahead of time, and we pick collection points using arbitrary computing power. This is obviously unrealistic, but it's the goal. This is a basic constraint-solving problem, and it yields the optimal result. Call this mode "hindsight".

2) We know the program ahead of time, and can do arbitrary full-program analysis, compilation, and the like, but we don't know the specifics of any execution. Call this mode "full-program".

3) We don't know anything about the program. Call this mode "online".

The first major question is whether there is a gap between hindsight, full-program, and online. I suspect there is. Specifically, I'm almost certain that hindsight > full-program, and I'm pretty sure full-program > online.


The second specifically concerns the full-program scheme. I'll call programs whose execution patterns and allocation patterns are predictable knowing all inputs "regular", and those who aren't "chaotic". It's pretty obvious that you can have a regular program with regular allocation behavior. An example is a program that builds up a list to a specific length, then empties it, then fills it again. Once you know the length of the list, you can plan to do collections when you empty the list. I'm almost certain that one can produce a chaotic program with chaotic allocation behavior by adapting a real-life chaotic system like Lorenz's water-wheel. It's fairly easy to get from this point to chaotic programs with regular allocation behavior. The real question is, can you have a regular program with chaotic allocation behavior.

On that, I'm split. Intuition would seem to say "no", but there is alot of work on things like chaotic iterated maps that leads me to suspect otherwise.

So the real second question is whether or not a regular program can produce chaotic allocation behavior.