Making the trains run on time

Automatic memory management techniques aid the development of more robust and maintainable applications. However, these garbage collection services can be disruptive suspending an application for extended periods of time while the heap is traversed and unreachable memory is reclaimed. While many applications do not have hard, real-time requirements, they do require a certain level of responsiveness. To be practical, memory management services must scale with the available system resources and scale with the manner in which the application allocates and uses memory. One promising collection technique for reducing the lengths of these pauses is Train algorithm. This space-incremental copying technique allows a large memory space to be collected incrementally by dividing the heap into blocks and collecting subsets of these blocks in a particular order. By considering only a small portion of the heap at a time, the technique can collect only as much memory as is needed to keep up with the needs of the application. However, garbage collectors based on the Train algorithm have failed to live up to this promise. In addition to introducing significant overheads—for example, in the tracking of references between parts of the heap—the collectors have not moderated pauses or do not keep up with rate at which the application allocates memory. This dissertation demonstrates that the Train algorithm can form the basis of scalable, nondisruptive garbage collectors even for large heaps. We begin with a simple incremental collector to understand the basic mechanisms and costs of the algorithm. From this starting point, we show how the efficiency of the collector may be improved through better processing of roots during collection, more general detection of dead sequences of blocks of memory, more efficient remembered-sets and dynamic detection and isolation of popular objects, and better placement of objects in the generation. Finally, we show how a collector based on the Train algorithm can bound the amount of work performed in each increment