System and method for performing garbage collection on a large heap
First Claim
1. A computer-readable medium having computer-executable instructions for performing ephemeral garbage collection, the instructions comprising:
- obtaining a list of memory locations that have been written into since the last ephemeral garbage collection, each memory location corresponding to one of a plurality of addresses for accessing a card table that identifies marked cards, the marked cards being associated with one or more objects allocated from within a memory heap, the memory heap being divided into a plurality of cards which are grouped into a plurality of bundles, each marked card being one of the plurality of cards;
identifying at least one marked bundle out of the plurality of bundles based on the list;
for each marked bundle, determining the marked cards within the marked bundle;
for each marked card, determining at least one accessed object within the marked card; and
performing garbage collection upon the at least one accessed object.
2 Assignments
0 Petitions
Accused Products
Abstract
The techniques and mechanisms described herein are directed to a system for performing garbage collection on a large heap that is divided into several cards which are grouped into bundles. The techniques include initiating a write-watch mechanism to track accesses to a card table that identifies marked cards. The write-watch mechanism provides a list of the written card table locations to a garbage collection process which determines marked bundles based on the list. For each marked bundle, the marked cards within the marked bundle are scanned to identify the accessed objects. The accessed objects are then collected. Because determining the marked bundles is performed at the start of the garbage collection process and not whenever the memory locations within the bundle are accessed, the present technique reduces the overhead associated with bundle marking and allows the efficiency of the garbage collection process to be less dependent on heap size.
87 Citations
24 Claims
-
1. A computer-readable medium having computer-executable instructions for performing ephemeral garbage collection, the instructions comprising:
-
obtaining a list of memory locations that have been written into since the last ephemeral garbage collection, each memory location corresponding to one of a plurality of addresses for accessing a card table that identifies marked cards, the marked cards being associated with one or more objects allocated from within a memory heap, the memory heap being divided into a plurality of cards which are grouped into a plurality of bundles, each marked card being one of the plurality of cards;
identifying at least one marked bundle out of the plurality of bundles based on the list;
for each marked bundle, determining the marked cards within the marked bundle;
for each marked card, determining at least one accessed object within the marked card; and
performing garbage collection upon the at least one accessed object. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A method for executing statements within a program to support ephemeral garbage collection, the method comprising:
-
specifying a range of card table memory to watch during program execution, the card table memory identifying marked cards that are associated with one or more objects allocated within a memory heap, the memory heap being divided into a plurality of cards which are grouped into a plurality of bundles, each marked card being one of the plurality of cards; and
for each store statement within the program, storing a value at a memory location within the heap memory based on the store statement, marking one of the plurality of cards within the card table based on the memory location, and tracking the card table memory. - View Dependent Claims (13, 14, 15, 16, 17, 18)
-
-
19. A system for performing ephemeral garbage collection, the system comprising:
-
a processor; and
a memory into which a plurality of instructions are loaded and into which a plurality of objects are dynamically allocated, the memory having a heap into which the objects are allocated, the heap being divided into a plurality of cards which are grouped into a plurality of bundles, each card being associated with one or more of the plurality of objects, the plurality of instructions performing a method comprising;
during a garbage collection cycle, obtaining a list of memory locations that have been written into since the last garbage collection cycle, each memory location corresponding to one of a plurality of addresses for accessing a card table that identifies marked cards, each marked card being one of the plurality of cards;
identifying at least one marked bundle out of the plurality of bundles based on the list;
for each marked bundle, determining at least one marked card within the marked bundle the at least one marked card indicating that one or more objects associated with the marked card has been accessed;
for each marked card, determining at least one accessed object within the marked card; and
performing garbage collection upon the at least one accessed object. - View Dependent Claims (20, 21, 22, 23, 24)
-
Specification