Analyzing GC Traces

For the chaos research, I'm building a simulator framework for analyzing garbage collection traces. What I've had in mind up to this point is a simulator for a simple language, which generates traces, an analyzer which runs on traces to simulate collection events. I recently had the idea of using an ILP solver to compute the optimal collection strategy, and compare the results against any online (read: usable) approaches we came up with.

However, I realized yesterday that the branch and bound algorithm for solving ILP problems potentially yields alot of very useful information regarding garbage collection. The algorithm provides a way to analyze the impact of choosing whether or not to collect at a given point, and the shape of the search tree should give some indication as to which points are the most important. This in itself is potentially very useful information. Moreover, it could become a profiling technique in its own right. If a certain point is a useful point for garbage collection in most of the runs of a program, then it could be statically marked as a preferential point for collection.