Parallel, single-pass compaction in a region-based garbage collector

Abstract

A method to implement parallel, single-pass compaction in a garbage collector is described. In one embodiment, such a method includes conducting a planning phase for multiple regions to be compacted. During the planning phase, the method determines new locations for data entities in the multiple regions. The method then performs a move phase for the multiple regions to move the data entities to their new locations. During the move phase, the method initiates multiple compaction threads to move the data entities to their new locations. While executing, the compaction threads dynamically build a dependency graph of the regions being compacted. The dependency graph guarantees that no data entity is moved to its new location until all data entities that it overwrites have been moved to their new locations. A corresponding computer program product and apparatus are also disclosed and claimed herein.

1 - 8 . (canceled) 
     
     
         9 . A computer program product to implement parallel, single-pass compaction in a garbage collector, the computer program product comprising a computer-usable storage medium having computer-usable program code embodied therein, the computer-usable program code comprising:
 computer-usable program code to conduct a planning phase for a plurality of regions to be compacted, wherein conducting the planning phase comprises determining new locations for data entities in the plurality of regions;   computer-usable program code to perform a move phase for the plurality of regions to move the data entities to their new locations, wherein performing the move phase comprises:
 initiating a plurality of compaction threads to move the data entities to their new locations; and 
 dynamically building a dependency graph of the regions being compacted as the compaction threads move the data entities to their new locations, wherein the dependency graph guarantees that no data entity is moved to its new location until all data entities that it overwrites have been moved to their new locations. 
   
     
     
         10 . The computer program product of  claim 9 , wherein the plurality of compaction threads are configured to operate in parallel. 
     
     
         11 . The computer program product of  claim 9 , wherein the data entities are at least one of objects and groups of objects. 
     
     
         12 . The computer program product of  claim 9 , wherein performing the move phase comprises performing the move phase in a single pass over the plurality of regions. 
     
     
         13 . The computer program product of  claim 9 , wherein the compaction threads are configured to pop regions from a work stack to determine which regions need to be compacted. 
     
     
         14 . The computer program product of  claim 13 , wherein each region includes a blocked regions list indicating the regions that are blocked on the region. 
     
     
         15 . The computer program product of  claim 14 , further comprising computer-usable program code to, upon completing a region, push all regions in the region's blocked regions list onto the work stack. 
     
     
         16 . The computer program product of  claim 14 , further comprising computer-usable program code to, upon encountering a first data entity that cannot be moved because a second data entity that it overwrites has not yet been moved, place the region associated with the first data entity in the blocked regions list of the region associated with the second data entity. 
     
     
         17 . An apparatus to implement parallel, single-pass compaction in a garbage collector, the apparatus comprising:
 a planning module to conduct a planning phase for a plurality of regions to be compacted, wherein conducting the planning phase comprises determining new locations for data entities in the plurality of regions; and   a move module to perform a move phase for the plurality of regions to move the data entities to their new locations, wherein performing the move phase comprises:
 initiating a plurality of compaction threads to move the data entities to their new locations; and 
 dynamically building a dependency graph of the regions being compacted as the compaction threads move the data entities to their new locations, wherein the dependency graph guarantees that no data entity is moved to its new location until all data entities that it overwrites have been moved to their new locations. 
   
     
     
         18 . The apparatus of  claim 17 , wherein the plurality of compaction threads are configured to operate in parallel. 
     
     
         19 . The apparatus of  claim 17 , wherein the data entities are at least one of objects and groups of objects. 
     
     
         20 . The apparatus of  claim 17 , wherein performing the move phase comprises performing the move phase in a single pass over the plurality of regions. 
     
     
         21 . The apparatus of  claim 17 , wherein the compaction threads are configured to pop regions from a work stack to determine which regions need to be compacted. 
     
     
         22 . The apparatus of  claim 21 , wherein each region includes a blocked regions list indicating which regions are blocked on the region. 
     
     
         23 . The apparatus of  claim 22 , wherein the move module is further configured to, upon completing a region, push all regions in the region's blocked regions list onto the work stack. 
     
     
         24 . The apparatus of  claim 22 , wherein the move module is further configured to, upon encountering a first data entity that cannot be moved because a second data entity that it overwrites has not yet been moved, place the region associated with the first data entity in the blocked regions list of the region associated with the second data entity.