Performance analysis of garbage collection and dynamic reordering in a Lisp system
Llames, Rene Lim
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/19302
Description
Title
Performance analysis of garbage collection and dynamic reordering in a Lisp system
Author(s)
Llames, Rene Lim
Issue Date
1991
Doctoral Committee Chair(s)
Iyer, Ravishankar K.
Department of Study
Electrical and Computer Engineering
Discipline
Electrical Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
