Optimizing a marking phase in mark-sweep garbage collectors by reducing paging activity
View Patent ↗A garbage collector can initialize a garbage collection cycle. The cycle can include a mark phase and a sweep phase. The mark phase can traverses a complete set of objects in a heap. The heap can be associated with a virtual application memory including a primary memory and a secondary memory. The virtual application memory can be managed by a virtual memory manager, which moves pages between the primary memory and the secondary memory. Information can be bidirectionally communicated between a garbage collector and the virtual memory manager. A default order in which the objects are evaluated during the mark phase can be altered to minimize paging activity. The altering of the order can be based at least in part upon information obtained from the virtual memory manager.
1. A method for garbage collection comprising: a garbage collector using a processor initializing a garbage collection cycle, wherein said garbage collection cycle comprises a mark phase and a sweep phase, wherein said mark phase traverses a complete set of objects in a heap, wherein said heap is associated with a virtual application memory comprising a primary memory and a secondary memory, wherein the virtual application memory is managed by a virtual memory manager, which moves pages between the primary memory and the secondary memory; communicating information bidirectionally between the garbage collector and the virtual memory manager; and altering a default order in which the objects are evaluated during the mark phase to minimize paging activity, wherein the altering of the order is based at least in part upon information obtained from the virtual memory manager; wherein a marking of objects in the heap that are not associated with pages in the primary memory is deferred until the associated pages are placed in primary memory, wherein a page load request is submitted each time a marking of an object is deferred, wherein objects that are associated with pages in primary memory are marked while objects that are not associated with pages in primary memory are deferred.
2. The method of claim 1 , further comprising: querying an operating system for an eviction status of every page in the heap at a beginning of the garbage collection cycle; building a page map of pages that indicates which page associated with the heap is included in the primary memory and which page is included in the secondary memory; the garbage collector registering with the virtual memory manager for page events; responsive to the registering, the garbage collector receiving at least one change in page status; and responsive to receiving at least one change in page status, updating the page map to reflect the received at least one change.
3. The method of claim 1 , further comprising: during the mark phase, establishing an active work list and a deferred work list, wherein at the beginning of the garbage collection cycle the active work list comprises all root objects in the heap and the deferred work list comprises a null set; for a each object in the active work list: determining if the object is in the primary memory; when the object is not in the primary memory, moving the object from the active work list to the deferred work list and submitting a request to load all pages associated with the object to the primary memory; when the object is in the primary memory, marking the object as reachable and removing the object from the active work list; and when the active work list is null and the deferred work list includes at least one object, moving all objects in primary memory in the deferred work list to the active work list.
4. The method of claim 1 , wherein the garbage collection cycle executes in a garbage collection environment which is implemented in an abstraction layer above an operating system environment, wherein the virtual memory manager is implemented within the operating system environment.
5. A computer program product for garbage collection, said computer program product comprising a computer readable storage medium having computer usable program code embodied therewith, the computer usable program code comprising: computer usable program code configured to have a garbage collector to initialize a garbage collection cycle, wherein said garbage collection cycle comprises a mark phase and a sweep phase, wherein said mark phase traverses a complete set of objects in a heap, wherein said heap is associated with a virtual application memory comprising a primary memory and a secondary memory, wherein the virtual application memory is managed by a virtual memory manager, which moves pages between the primary memory and the secondary memory; computer usable program code configured to communicate information bidirectionally between a garbage collector and the virtual memory manager; and computer usable program code configured to alter a default order in which the objects are evaluated during the mark phase to minimize paging activity, wherein the altering of the order is based at least in part upon information obtained from the virtual memory manager; wherein a marking of objects in the heap that are not associated with pages in the primary memory is deferred until the associated pages are placed in primary memory, wherein a page load request is submitted each time a marking of an object is deferred, wherein objects that are associated with pages in primary memory are marked while objects that are not associated with pages in primary memory are deferred.
6. The computer program product of claim 5 , further comprising: computer usable program code configured to query an operating system for an eviction status of every page in the heap at a beginning of the garbage collection cycle; computer usable program code configured to build a page map of pages that indicates which pages associated with the heap are resident in the primary memory and which pages are resident in the secondary memory; computer usable program code configured to have the garbage collector register with the virtual memory manager for page events; computer usable program code configured to have the garbage collector receive at least one change in page status; and computer usable program code configured to update the page map to reflect the received at least one change responsive to receiving at least one change in page status.
7. The computer program product of claim 5 , further comprising: computer usable program code configured to, during the mark phase, establish an active work list and a deferred work list, wherein at the beginning of the garbage collection cycle the active work list comprises all root objects in the heap and the deferred work list comprises a null set; computer usable program code configured to, for a each object in the active work list: determine if the object is in the primary memory; when the object is not in the primary memory, move the object from the active work list to the deferred work list and submit a request to load all pages associated with the object to the primary memory; when the object is in the primary memory, mark the object as reachable and remove the object from the active work list; and when the active work list is null and the deferred work list includes at least one object, move all objects in primary memory from the deferred work list to the active work list.
8. The computer program product of claim 5 , wherein the garbage collection cycle executes in a garbage collection environment which is implemented in an abstraction layer above an operating system environment, wherein the virtual memory manager is implemented within the operating system environment.