Patent ID: 6925637

Claim:
A method of carrying out garbage collection in a computer system having a plurality of memory objects in at least one memory group, the method comprising: tracing a state of each memory object in the at least one memory group; allocating an identifier to each memory object according to a three-color abstraction including; coloring a memory object a first color if that memory object has not been encountered during the tracing process; coloring a memory object a second color if that memory object and all objects to which that memory object refer have been encountered during the tracing process; coloring a memory object a third color if that memory object is a partially traced memory object that itself has been encountered, but some of the objects to which the partially traced memory object refers have not yet been encountered; allocating the memory objects colored the first color into a first set of unencountered memory objects represented as a first color data structure; allocating the memory objects colored the second color into a second set of encountered memory objects represented as a second color data structure differing from the first color data structure; allocating the partially traced memory objects colored the third color into at least one set of partially traced memory objects represented as a third color data structure differing from the first color data structure and the second color data structure; dividing the at least one set of partially traced memory objects into a plurality of discrete packet data structures for containing the partially traced memory objects in the packet data structures separate from the objects in the first color data structure and the second color data structure; creating new packet data structures to store additional partially traced objects on a demand basis; merging partially full packet data structures to optimize memory allocation; and destroying unneeded packet data structures to free up memory on a demand basis.