Locality with parallel hierarchical copying garbage collection

Abstract

Disclosed is a garbage collection algorithm that achieves hierarchical copy order with parallel garbage collection threads. More specifically, the present invention provides a garbage collection method and system for copying objects from a from-space to a to-space. The method comprises the steps of (a) having multiple threads that simultaneously perform work for garbage collection (GC), (b) examining the placement of objects on blocks, and (c) changing the placement of objects on blocks based on step (b). Preferably, the method includes the additional step of calculating a placement of object(s) based on step (b), and using the result of the calculation for step (c). For example, the calculation may be used to increase the frequency of intra-block pointers and / or to increase the frequency of siblings on the same block.

Description

BACKGROUND OF THE INVENTION[0001]1. Field of the Invention[0002]This invention generally relates to automatic memory management, and more specifically, the invention relates to methods and systems for copying garbage collection.[0003]2. Background Art[0004]In operation, computer programs spend a lot of time stalled in cache and TLB misses, because computation tends to be faster than memory access. For example, Adl-Tabatabai et al. report that the SPECjbb2000 benchmark spends 45% of its time stalled in misses on an Itanium processor [Ali-Reza Adl-Tabatabai, Richard L. Hudson, Mauricio J. Serrano, and Sreenivas Subramoney. Prefetch injection based on hardware monitoring and object metadata. In Programming Language Design and Implementation (PLDI), 2004]. Better locality reduces misses, and thus improves performance. For example, techniques like prefetching or cache-aware memory allocation improve locality, and can significantly speedup the performance of a program.[0005]Locality is in...

AI Technical Summary

Benefits of technology

[0008]An object of this invention is to reduce cache and TLB misses by changing the order in which a parallel garbage collector copies heap objects.

[0011]Another object of the invention is to provide a garbage collection algorithm that both reduces cache and TLB misses through hierarchical copying and also maintains good scaling on multiprocessors.

[0013]The preferred embodiment of the invention, described in detail below, reduces cache and TB misses and, in this way, improves program run time. Also, parallel garbage collection improves scaling on multi-processor machines.

Problems solved by technology

In operation, computer programs spend a lot of time stalled in cache and TLB misses, because computation tends to be faster than memory access.

Images