Performing exact garbage collection using bitmaps that identify pointer values within objects
First Claim
1. A method for performing garbage collection for an object defined within an object oriented programming system, the object including a variable storage area for storing both pointer variables and non-pointer variables associated with the object, the method comprising:
- associating a tagging bitmap with the object, each bit in the tagging bitmap specifying whether a corresponding variable in the variable storage area of the object contains a pointer variable;
encountering the object during a garbage collection process, which operates by following pointers between objects in order to determine which objects are reachable through pointers, so that other non-reachable objects can be reclaimed; and
following the pointer variables within the variable storage area of the object to other objects for garbage collection purposes by,using the tagging bitmap associated with the object to index a specific routine from a collection of routines, the collection of routines including a different routine for each possible tagging bitmap pattern, wherein the specific routine can assume by virtue of the prior indexing operation that certain variables in the variable storage area contain pointer variables, allowing the specific routine to follow the pointer variables without individually testing each variable to determine if the variable is a pointer variable, andexecuting the specific routine to follow the pointer variables in the variable storage area of the object to the other objects.
2 Assignments
0 Petitions
Accused Products
Abstract
One embodiment of the present invention presents a method and apparatus for efficiently performing garbage collection on objects defined within an object-oriented programming system. Garbage collection typically involves following pointers to determine which objects are presently being referenced so that other objects, that are not being referenced, can be removed. To this end, the present invention maintains a bitmap for each object that indicates which variables in the object are pointer variables and which variables are non-pointer variables. A garbage collection process examines the bitmap, and on the basis of the pattern contained in the bitmap jumps to a particular routine that is tailored to garbage collect the particular pattern of pointer and non-pointer values in the object. Note that the system includes a routine tailored for each possible bitmap pattern. This technique speeds up the garbage collection process by eliminating the need to read type information one variable at a time to determine which variables within an object contain pointers.
165 Citations
9 Claims
-
1. A method for performing garbage collection for an object defined within an object oriented programming system, the object including a variable storage area for storing both pointer variables and non-pointer variables associated with the object, the method comprising:
-
associating a tagging bitmap with the object, each bit in the tagging bitmap specifying whether a corresponding variable in the variable storage area of the object contains a pointer variable; encountering the object during a garbage collection process, which operates by following pointers between objects in order to determine which objects are reachable through pointers, so that other non-reachable objects can be reclaimed; and following the pointer variables within the variable storage area of the object to other objects for garbage collection purposes by, using the tagging bitmap associated with the object to index a specific routine from a collection of routines, the collection of routines including a different routine for each possible tagging bitmap pattern, wherein the specific routine can assume by virtue of the prior indexing operation that certain variables in the variable storage area contain pointer variables, allowing the specific routine to follow the pointer variables without individually testing each variable to determine if the variable is a pointer variable, and executing the specific routine to follow the pointer variables in the variable storage area of the object to the other objects. - View Dependent Claims (2, 3)
-
-
4. An apparatus for performing garbage collection for an object defined within an object oriented programming system, the object including a variable storage area for storing both pointer variables and non-pointer variables associated with the object, the apparatus comprising:
-
a central processing unit; a memory coupled to the central processing unit; a tagging mechanism configured to associate a tagging bitmap with the object, each bit in the tagging bitmap specifying whether a corresponding variable in the variable storage area of the object contains a pointer variable; a garbage collection mechanism configured to following pointers between objects in order to determine which objects are reachable through pointers, so that other non-reachable objects can be reclaimed; wherein the garbage collection mechanism is configured to follow the pointer variables within the variable storage area of the object to other objects for garbage collection purposes by, using the tagging bitmap associated with the object to index a specific routine from a collection of routines, the collection of routines including a different routine for each possible tagging bitmap pattern, wherein the specific routine can assume by virtue of the prior indexing operation that certain variables in the variable storage area contain pointer variables, allowing the specific routine to follow the pointer variables without individually testing each variable to determine if the variable is a pointer variable, and executing the specific routine to follow the pointer variables in the variable storage area of the object to the other objects. - View Dependent Claims (5, 6)
-
-
7. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for performing garbage collection for an object defined within an object oriented programming system, the object including a variable storage area for storing both pointer variables and non-pointer variables associated with the object, the method comprising:
-
associating a tagging bitmap with the object, each bit in the tagging bitmap specifying whether a corresponding variable in the variable storage area of the object contains a pointer variable; encountering the object during a garbage collection process, which operates by following pointers between objects in order to determine which objects are reachable through pointers, so that other non-reachable objects can be reclaimed; and following the pointer variables within the variable storage area of the object to other objects for garbage collection purposes by, using the tagging bitmap associated with the object to index a specific routine from a collection of routines, the collection of routines including a different routine for each possible tagging bitmap pattern, wherein the specific routine can assume by virtue of the prior indexing operation that certain variables in the variable storage area contain pointer variables, allowing the specific routine to follow the pointer variables without individually testing each variable to determine if the variable is a pointer variable, and executing the specific routine to follow the pointer variables in the variable storage area of the object to the other objects. - View Dependent Claims (8, 9)
-
Specification