Files in this item
|(no description provided)|
|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|
|Degree Granting Institution:||University of Illinois at Urbana-Champaign|
|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.
|Rights Information:||Copyright 1991 Llames, Rene Lim|
|Date Available in IDEALS:||2011-05-07|
|Identifier in Online Catalog:||AAI9136665|
This item appears in the following Collection(s)
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Electrical and Computer Engineering
Dissertations and Theses in Electrical and Computer Engineering