Files in this item



application/pdf9136665.pdf (4MB)Restricted to U of Illinois
(no description provided)PDF


Title:Performance analysis of garbage collection and dynamic reordering in a Lisp system
Author(s):Llames, Rene Lim
Doctoral Committee Chair(s):Iyer, Ravishankar K.
Department / Program:Electrical and Computer Engineering
Discipline:Electrical Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
Abstract:Generation-based garbage collection and dynamic reordering of objects are two techniques for improving the efficiency of memory management in Lisp and similar dynamic language systems. An analysis of the effect of generation configuration is presented, focusing on the effect of the number of generations and generation capacities. Analytic timing and survival models are used to represent garbage collection runtime and to derive structural results on its behavior. The survival model provides bounds on the age of objects surviving a garbage collection at a particular level. Empirical results show that execution time is most sensitive to the capacity of the youngest generation. The existence of a range of optimum values demonstrates the potential for the tuning of garbage collection.
A new memory management system integrating dynamic reordering with garbage collection is described. The system supports schemes for preserving object order in virtual memory during garbage collection, both approximately and exactly.
We present a technique, called scanning for transport statistics, for evaluating the effectiveness of reordering, independent of main memory size. Reordering oldspace is scanned for the number of pages containing the transported objects and statistics on their sizes, from which is computed the reduction in working set size due to reordering. The relative reduction in working set size is a measure of the density with which the actively used objects are packed into pages. Since the technique can be applied selectively in space, the portions of memory which are suitable for reordering can be identified. The method can also be used to measure locality improvement due to garbage collection.
Results from two experiments, one involving an extensive interactive session and the other a large application, show overall reductions in working set size of 48% and 58% due to reordering, with up to 93% for individual memory areas. Relative reduction in working set size was found to be greater for list space than structure space, by a factor of about three overall. The large disparity between list and structure object fragmentation in certain areas suggests that the memory management system should be able to treat list and structure space differently.
Issue Date:1991
Rights Information:Copyright 1991 Llames, Rene Lim
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9136665
OCLC Identifier:(UMI)AAI9136665

This item appears in the following Collection(s)

Item Statistics