Properties of Age Based Automatic Memory Reclamation Algorithms

Dynamic memory management enables a programmer to allocate objects for arbitrary preiods of time. It is an important feature of modern programming languages, and is fundamental to object-oriented languages. Automatic reclamation, also known as garbage collection, automates the detection of the time when a data item can no longer be used. The work described herein considers garbage collection algorithms that base their decisions solely upon the relative age of data. This age-based class of algorithms generalizes previously defined generational garbage collection algorithms and includes promising new algorithms. The work identifies relevant performance factors and reports them for a set of object-oriented benchmark programs, establishing a fair comparison by imposing uniform maximum space constraints. A precise tracing and garbage collection algorithm evaluation framework provides accurate results and thus meaningful comparisons. The results indicate, contrary to assumptions in the literature, that the new algorithms copy less data than the generational algorithms, even though they retain a higher percentage of reclaimable data. In agreement with the assumptions in the literature, the results indicate that generational algorithms do less pointer-tracking work. Thus, given suitable relative costs of copying and pointer-tracking, the new algorithms perform better. Estimations of the relative costs for a typical modern processor suggest that the new algorithms are usually superior.

3

PhD dissertation, University of Massachusetts