The performance of the runtime system will have an impact on the performance of the program being executed. Traditionally an execution environment provides a single mechanism for handling storage allocation and another for handling reclamation, yet it has been shown for both allocators [WJNB95] and collectors [FT00] that different types of applications perform better when mechanisms other than those ``built-in'' to the system are used. In short, the memory usage patterns of an application (or even distinct phases of execution of an application) determine what memory management strategy will result in the best performance.
We are building a memory management simulator to measure the performance of different mechanisms on particular applications, under the assumption that choosing a mechanism which matches a program's allocation behavior will improve performance more than trying to tune a built-in mechanism to the program. The simulator is component-based in the sense that management mechanisms can be prototyped as units and loaded either at startup or dynamically as the simulation system runs. Further, the simulator has the following properties:
Experimental Control. Simulator is controlled by scripts which
allow the user to specify such experimental parameters as heap size, input
format, manager mechanisms to use, and what performance information to
Prototype Framework. Memory management policies and mechanisms can be prototyped in the language to more adequately explore the design space. Simulations for different runtimes can be built quickly and flexibly compared to developing new managers .
Language independence. The user will be able to tailor the system to any specific language model.
Extensibility. Work in memory management systems encompasses a wide range of architectures for runtime systems and new proposals are forthcoming. The runtime components provide a foundation but may be extended so that our studies can proceed from basic systems, to more advanced systems, to newly-proposed systems.
The mark/sweep method periodically "takes over" execution from a running program to examine the objects on the heap. In the mark phase, all heap objects which are reachable through some sequence of references are marked as "live". Then the sweep phase looks at each object currently allocated, and deallocates those which do not have a mark (or, are "dead"). A disadvantage is that every object on the heap must be examined, which for large heaps with many objects can result in a substantial pause time during which the program can do no work.
An improvement intended to address pause times is called copying collectors. The simplest of these divides the heap into to semispaces, and allocation occurs in only one at a time. When the currently allocated semispace is full, all live objects are copied from it into the other semispace and the process continues. In 1981, Lieberman and Hewitt developed the weak-generational hypothesis, which posits that most objects have a short life-time and can be recycled soon after they are allocated [LH83]. This led to the development of generational copying collectors, in which the heap is divided into two or more "generations." All objects are allocated from the first generation (sometimes called the nursery); those objects which are still live when this generation becomes full are "promoted" or "tenured" into a succeeding generation. One special consideration which is specific to this type of collector is how to keep track of references between generations [JL96]. Generational collection is very flexible in the number of partitions in the heap and the way in which each partition is managed. For example, the Java HotSpot Performance Engine manages tenured objects using a mark/sweep collector; it is also possible to use the advanced train algorithm to incrementally manage this generation [HM92].
Memory Simulators. Simulators have been used for a number of years to study both the allocation behavior of specify applications and the behavior of memory management techniques. One of the first described systems was MARS, (Memory Allocation and Reference Simulator), described in Ben Zorn's dissertation [Zorn89]. This simulator was attached to a running Lisp system and allowed the user to study the impact of using different (simulated) garbage collection algorithms with a set of applications. Simulation is also important in the work of Darkovic [DS98], Holzle and Scheider [DH98], and Hanson [Han02]. Of these three, only [DH98] gives details about the simulator framework. Few if any such systems have been made available to the research community.
Runtime System Construction. As an alternative to simulation,
some researchers provide interfaces for replacing existing memory management
systems with newly developed systems. The Jikes Research VM from IBM [IBM-URL]
is a Java virtual machine that allows the programmer to replace the existing
manager at build-time, either with one of several provided managers or
a user-defined manager. A set of Java classes are provided as an example
of the interface to the runtime system. Earlier, the GC Toolkit was a library
for programmers that allowed them to build generational collectors for
Smalltalk and other languages [HMDW]; a
version of this library has been developed to work specifically with the
Jikes RVM [GCtk].
|[DH98]||Sylvia Dieckmann and Urs Holzle. A Study of the Allocation Behavior of the SPECjvm98 Java Benchmarks. Technical Report 1998-33, UCSB Computer Science Department. December, 1998.|
|[FT00]||Robert Fitzgerald and David Tarditi. The Case for Profile-Directed Selection of Garbage Collectors. In Proceedings of the Internation Symposium on Memory Management, October 2000.|
|[GCtk]||A Garbage Collection Toolkit. Architecture & Language Implementation Laboratory, Department of Computer Science, University of Massachusetts.|
|[Han02]||Lars T. Hansen and William D. Clinger. An Experimental Study of Renewal-Older-First Garbage Collection. International Conference on Functional Programming, 247-258, 2002.|
|[HMDW]||Richard L. Hudson, J. Eliot B. Moss, Amer Diwan, and Christopher F. Weight. A language-independent garbage collector toolkit. COINS Technical Report 91-47, University of Massachusetts, Amherst, September 1991.|
|[HM92]||Richard L. Hudson and J. Eliot B. Moss. Incremental garbage collection for mature objects. In Proceedings of International Workshop on Memory Management, Lecture Notes in Computer Science 637. Springer-Verlag, September 1992.|
|[IBM-URL]||Jikes Research Virtual Machine from IBM|
|[JL96]||Richard Jones and Rafael Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. John Wiley and Sons, 1996.|
|[LH83]||Henry Lieberman and Carl Hewitt. A Real-Tim Garbage Collector Baswed on the Lifetimes of Objects, Communications of the ACM 26(6), pp. 419-429, June 1983.|
|[DS98]||Darko Stefanovic. Properties of Age-based Memory Reclamation Algorithms. Ph.D. tehsis, University of Massachusetts, February 1999.|
|[WJNB95]||Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles. Dynamic Storage Allocation: A Survey and Critical Review. In 1995 International Workshop on Memory Management, LNCS 986. Springer, 1995.|
|[Zorn89]||Benjamin Zorn. Comparitive Performance Evaluation of Garbage Collection Algorithms. Published as CSD-89-544 from University of California, Berkeley.|