PERFORMING EXACT GARBAGE COLLECTION USING BITMAPS THAT IDENTIFY POINTER VALUES WITHIN

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.