Thursday, September 22, 2011

More on GC

I had been thinking of improving the garbage collector in MIT/GNU Scheme. I carefully measured the current GC performance so I could quantify any improvements. This uncovered a bug (see earlier post), but it also uncovered something more interesting. Here is a plot of the number of garbage collections as a function of heap size for the problem of compiling all the Scheme code in MIT/GNU Scheme:
This graph looks an awful lot like the graph of minimal collections. In fact, if we plot the minimum number of garbage collections necessary for about 6100000 blocks, we get this:
That appears to be a really good fit. This isn't too surprising, because a GC that collects only when it is almost out of memory ought not to be doing much more work than the minimum necessary.

What makes this interesting is this: We can clearly see the “knee” of the curve, and we have enough memory to be “well beyond the knee” when we compile all of Scheme. This means that the total number of garbage collections will be quite low. If the garbage collector is fast enough, the total GC time will also be quite low. For example, when given 40000 blocks of memory, MIT/GNU Scheme will compile itself in about 3 minutes of which only 2.6 seconds total are spent in garbage collection. And as I noted previously, with sufficient memory, there need not be any garbage collection at all.

Notice that the details of the collector are unimportant. MIT/GNU Scheme uses a variation of the Minsky-Fenichel-Yochelson-Cheney-Arnborg algorithm, but it could just as easily use a mark-sweep collector. The point is that when you are only doing a few dozen collections, it doesn't matter much what algorithm you use because changing the algorithm will make little impact on the total run time. (Suppose I had the world's greatest garbage collector that just blows away the current one. Then I could reduce the total time from 182.6 seconds to exactly 180 seconds. This is less than a 5% improvement and not worth pursuing.) (A reference count GC, however, would be a problem because it traces garbage rather than live storage.)

So my original plan is pointless. There is no advantage to improving the garbage collector if it doesn't take more than a small amount of time, and it looks like you can achieve this by simply throwing memory at the process. So long as you have sufficient memory, you can make the cost of a collection be close to (or even equal to) zero.

At least it looks that way...