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.

1 . A method for doing garbage collection (GC) comprising the steps of:
 a) having multiple threads that simultaneously perform work for GC;   b) examining the placement of objects on blocks; and   c) changing the placement of objects on blocks based on step (b).   
     
     
         2 . A method of  claim 1  including the additional step of calculating a placement of object(s) based on step (b), and using the result of the calculation for step (c). 
     
     
         3 . A method of  claim 2 , wherein the calculation increases the frequency of intra-block pointers. 
     
     
         4 . A method of  claim 2 , wherein the calculation increases the frequency of siblings on the same block. 
     
     
         5 . A method of  claim 1 , further comprising the step of enabling interrupting the scanning of a block, and deferring it for later, after every GC operation of scanning one slot or copying one object. 
     
     
         6 . A method of  claim 5  including the additional step of maintaining a scan pointer to the middle of an object in a block that is not actively being scanned by a thread. 
     
     
         7 . A method for doing garbage collection (GC) that uses the following steps:
 a) having multiple threads that simultaneously perform work for GC; and   b) using blocks as the work unit for parallel copying.   
     
     
         8 . A method of  claim 7 , comprising the further steps of:
 d) examining the placement of objects on blocks; and   e) changing the placement of objects on blocks based on step (d).   
     
     
         9 . A method according to  claim 1 , where
 i) roots and remembered sets get scanned to identify target objects in from-space, and the target objects get copied to to-space   ii) after an object gets copied, its to-space copy eventually gets scanned to identify zero or more target objects it points to in from-space, and the target objects also get copied to to-space   iii) to-space copies of objects get scanned in a defined order, which is used to achieve changing the placement of the copies of target objects on to-space blocks   
     
     
         10 . A method according to  claim 9 , where
 for each object that has already been copied to a block in to-space, the object is used to identify zero or more target objects it points to in from-space, and the target objects are copied to another block in to-space, the block of the scanned object having a defined relationship with the block of the copied object.   
     
     
         11 . A method according to  claim 10 , wherein said block of the scanned object is sometimes caused to be the same as said block of the copied object. 
     
     
         12 . A method according to  claim 11 , wherein the step that uses a defined order includes the step of, when one of the target objects is copied, checking to determine whether the block containing the scanned object is the same as the block to which the target object gets copied. 
     
     
         13 . A method according to  claim 12 , wherein the step of checking to determine whether the block containing the scanned object is the same as the block to which the target object gets copied, causes the two blocks to be the same if possible. 
     
     
         14 . A system for doing garbage collection (GC) comprising:
 a) multiple threads that simultaneously perform work for GC;   b) means for examining the placement of objects on blocks; and   c) means for changing the placement of objects on blocks based on said examining.   
     
     
         15 . A system of  claim 14  including the additional means for calculating a placement of object(s) based on said examining, and for using the result of the calculation for said changing. 
     
     
         16 . A system of  claim 15 , wherein the calculation increases the frequency of intra-block pointers. 
     
     
         17 . A system of  claim 15 , wherein the calculation increases the frequency of siblings on the same block. 
     
     
         18 . A system according to  claim 14 , further comprising means for enabling interrupting the scanning of a block, and deferring it for later, after every GC operation of scanning one slot or copying one object. 
     
     
         19 . A system of  claim 18  including the additional means of maintaining a scan pointer to the middle of an object in a block that is not actively being scanned by a thread. 
     
     
         20 . A system according to  claim 14 , where
 i) roots and remembered sets get scanned to identify target objects in from-space, and the target objects get copied to to-space   ii) after an object gets copied, its to-space copy eventually gets scanned to identify zero or more target objects it points to in from-space, and the target objects also get copied to to-space   iii) to-space copies of objects get scanned in a defined order, which is used to achieve changing the placement of the copies of target objects on to-space blocks   
     
     
         21 . A system according to  claim 20 , where
 for each object that has already been copied to a block in to-space, the object is used to identify zero or more target objects it points to in from-space, and the target objects are copied to another block in to-space, the block of the scanned object having a defined relationship with the block of the copied object.   
     
     
         22 . A system according to  claim 21 , wherein said block of the scanned object is sometimes caused to be the same as said block of the copied object. 
     
     
         23 . A system according to  claim 22 , wherein the means that uses a defined order includes means for, when one of the target objects is copied, checking to determine whether the block containing the scanned object is the same as the block to which the target object gets copied. 
     
     
         24 . A system according to  claim 23 , wherein the means for checking to determine whether the block containing the scanned object is the same as the block to which the target object gets copied, causes the two blocks to be the same if possible. 
     
     
         25 . A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for doing garbage collection (GC), said method steps comprising:
 a) having multiple threads that simultaneously perform work for GC;   b) examining the placement of objects on blocks; and   c) changing the placement of objects on blocks based on step (b).   
     
     
         26 . A program storage device of  claim 25 , wherein said method steps include the additional step of calculating a placement of object(s) based on step (b), and using the result of the calculation for step (c). 
     
     
         27 . A program storage device of  claim 26 , wherein the calculation increases the frequency of intra-block pointers. 
     
     
         28 . A program storage device of  claim 27 , wherein the calculation increases the frequency of siblings on the same block. 
     
     
         29 . A program storage device of  claim 25 , wherein said method steps comprise the additional step of enabling interrupting the scanning of a block, and deferring it for later, after every GC operation of scanning one slot or copying one object. 
     
     
         30 . A program storage device of  claim 29 , wherein said method steps include the additional step of maintaining a scan pointer to the middle of an object in a block that is not actively being scanned by a thread. 
     
     
         31 . A program storage device according to  claim 25 , where
 i) roots and remembered sets get scanned to identify target objects in from-space, and the target objects get copied to to-space   ii) after an object gets copied, its to-space copy eventually gets scanned to identify zero or more target objects it points to in from-space, and the target objects also get copied to to-space   iii) to-space copies of objects get scanned in a defined order, which is used to achieve changing the placement of the copies of target objects on to-space blocks.   
     
     
         32 . A garbage collection method of copying objects from a from-space to a to-space, comprising the steps of:
 using a plurality of threads to copy a plurality of said objects simultaneously from said from-space to a plurality of blocks in said to-space;   examining the placement of the objects in said blocks; and   changing the placement of objects in said blocks based on said examining.   
     
     
         33 . A method according to  claim 32 , wherein:
 the using step includes the step of using said multiple threads to scan some of said plurality of blocks;   each of said threads scans one of said plurality of blocks at a time;   each of said plurality of blocks is, at one time, a copy block; and   at least some of said plurality of blocks transition from a copy block to a scan block.   
     
     
         34 . A method according to  claim 33 , wherein:
 a first object is copied into a given one of the blocks, and a second objects is copied into another one of the blocks, said another one of the blocks having a defined relationship with said given one of the blocks;   said given one of the blocks is caused to be the same block as said another one of the blocks; and comprising the further step of   the second object is copied to said another one of the blocks, checking to determine whether said another one of the copy blocks is the same as said given one of the blocks; and if the said determination is that the said another one of the blocks is not the same as said given one of the blocks, then for said second object, the block into which the object is copied is chosen to be the same block as said given one of the blocks, if possible.