Cache Performance of Programs with Intensive Heap Allocation and Generational Garbage Collection (thesis)
Report ID: TR-492-95Author: Goncalves, Marcelo Jose de Rezende
Date: 1995-05-00
Pages: 124
Download Formats: |Postscript|
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.