Cache Performance of Programs with Intensive Heap Allocation and Generational Garbage Collection (thesis)

Abstract:

This dissertation presents a study of cache performance of programs
with intensive heap allocation and generational garbage collection,
such as ML programs compiled by the {em Standard ML of New Jersey}
compiler (SML/NJ). SML/NJ programs allocate objects dynamically in
the heap at a very fast rate, due to the allocation of function
activation records (closures) in the heap.
The memory reference patterns of a set of SML/NJ programs are studied,
showing that nearly all writes are for sequential allocation, and most
reads are to recently allocated objects. The cache performance of the
programs is studied with different cache parameters varied: cache and
block size, associativity, and write-miss policy. The results confirm
the findings of previous studies, that the write-miss policy has the
most significant effect on the performance of these programs. Because
of the way these programs reference memory it is important that the
cache allocates a block on writes, without fetching the block from
memory.
This dissertation also investigates the use of software alternatives
to improve cache performance, that have been suggested but not fully
analyzed in previous studies, such as fitting the allocation space in
the cache. The trade-offs between cache and garbage collection
overhead are quantitatively analyzed. The effects of other garbage
collection parameters on performance, such as the frequency of major
collections, and the algorithm to traverse the graph of reachable
objects are also considered.
The results of this study show that heap allocation, even intensive
heap allocation of closures, can have good cache performance, as long
as the architecture uses a favorable write-miss policy. On machines
with an unfavorable write-miss policy there are alternatives that can
be applied, such as fitting the allocation space in the cache.