Concurrent marking garbage collection
AssigneeInternational Business Machines Corporation
InventorsMichihiro Horie, Kazunori Ogata
Life of this patent
Estimating the term…
Abstract
A computer-implemented method is provided for reducing Compare And Swap (CAS) operations in a concurrent marking Garbage Collection (GC) process that operates on objects corresponding to a bit map of multiple blocks. The method includes finding, from among the objects, live objects that belong to a same block in the bit map from among the multiple blocks when traversing object trees of the objects for GC marking. The method further includes loading a latest value of the same block from the bitmap, updating the latest value by setting corresponding marking bits in the bit map, and updating the same block in the bit map with a single CAS operation.
Claims20
A computer-implemented method for reducing Compare And Swap (CAS) operations in a concurrent marking Garbage Collection (GC) process that operates on objects corresponding to a bit map of multiple blocks, the method comprising;
- finding, from among the objects, live objects that belong to a same block in the bit map from among the multiple blocks when traversing object trees of the objects for GC marking by determining if a parent and a child of the parent correspond to a same word in the bit map;
- and
- loading a latest value of the same block from the bitmap, updating the latest value by setting corresponding marking bits in the bit map, comparing set values to previous values in the bitmap, updating the same block in the bit map with a single CAS operation upon a match being detected from the comparison of the set values to the previous values in the bitmap, and swapping out the previous values for the set values upon a mismatch being detected from the comparison of the set values to the previous values in the bitmap,
- wherein the parent has a link going from the parent to the child.
A computer program product for reducing Compare And Swap (CAS) operations in a concurrent marking Garbage Collection (GC) process that operates on objects corresponding to a bit map of multiple blocks, the computer program product comprising a non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computer to cause the computer to perform a method comprising:
- finding, from among the objects, live objects that belong to a same block in the bit map from among the multiple blocks when traversing object trees of the objects for GC marking by determining if a parent and a child of the parent correspond to a same word in the bit map;
- and
- loading a latest value of the same block from the bitmap, updating the latest value by setting corresponding marking bits in the bit map, comparing set values to previous values, updating the same block in the bit map with a single CAS operation upon a match being detected from the comparison of the set values to the previous values in the bitmap, and swapping out the previous values for the set values upon a mismatch being detected from the comparison of the set values to the previous values in the bitmap,
- wherein the parent has a link going from the parent to the child.
A computer processing system for reducing Compare And Swap (CAS) operations in a concurrent marking Garbage Collection (GC) process that operates on objects corresponding to a bit map of multiple blocks, the computer processing system comprising;
- a memory device for storing program code;
- and
- a hardware processor, operatively coupled to the memory device, for running the program code to
- find, from among the objects, live objects that belong to a same block in the bit map from among the multiple blocks when traversing object trees of the objects for GC marking by determining if a parent and a child of the parent correspond to a same word in the bit map;
- and
- load a latest value of the same block from the bitmap, update the latest value by setting corresponding marking bits in the bit map, compare set values to previous values, update the same block in the bit map with a single CAS operation upon a match being detected from the comparison of the set values to the previous values in the bitmap, and swapping out the previous values for the set values upon a mismatch being detected from the comparison of the set values to the previous values in the bitmap,
- wherein the parent has a link going from the parent to the child.
Dependencies are inferred from the claim text.