TR #: 04-14

TR title: Automomic Heap Sizing: Taking Real Memory Into Account

Author (s): Ting Yang, Emery D. Berger, Matthew H. Hertz, 
	    Scott F. Kaplan, J. Eliot B. Moss

Address   Computer Science Department
           140 Governors Drive
           University of Massachusetts
           Amherst, MA  01003-4601

Date: March 19, 2004

Keywords: Memory management, garbage collection, heap size, paging

			       ABSTRACT

The selection of heap size has an enormous impact on the performance
of applications that use garbage collection. A heap that barely meets
the application's minimum requirements will result in excessive garbage 
collection overhead, while a heap that exceeds physical memory will 
cause paging. Choosing the best heap size a priori is impossible in 
multiprogrammed environments, where physical memory allocated to each 
process constantly changes. This paper presents an autonomic heap-sizing 
algorithm that one can apply to different underlying garbage collectors 
with only modest modifications. It relies on a combination of analytical
models and detailed information from the virtual memory manager. The 
analytical models characterize the relationship between collection 
algorithm, heap size, and footprint. The virtual memory manager tracks 
recent reference behavior, and reports the current footprint and 
allocation to the collector. The garbage collector then uses those 
values as inputs to its model to compute a heap size that maximizes 
throughput while minimizing paging. We show that by using our adaptive 
heap sizing algorithm, we can reduce running time over fixed-sized heaps 
by as much as 90%.