Low-contention grey object sets for concurrent, marking garbage collection

1. 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.

2. A method as claimed in claim 1 , wherein the computer system includes multiple threads, the method further comprising assigning one packet data structure to each thread such that each thread can access its one packet data structure independently of the other threads and packet data structures.

3. A method as claimed in claim 2 , further comprising transferring packet data structures between the threads and a packet manager.

4. A method as claimed in claim 2 , wherein the computer system includes a garbage collector, the method further comprising transferring packet data structures between the garbage collector and a packet manager.

5. A method as claimed in claim 1 , further comprising marking packet data structures accessed by a thread as checked out.

6. A method as claimed in claim 5 , further comprising marking packet data structures not accessed by a thread as checked in.

7. A method as claimed in claim 1 , further comprising destroying at least some of the packet data structures.

8. A method as claimed in claim 7 , wherein destroying at least some of the packet data structures includes merging the contents of partially full packet data structures.

9. A method as claimed in claim 1 , wherein the color is grey.

10. A method as claimed in claim 1 , wherein each packet data structure includes a plurality of slots.

11. A method as claimed in claim 10 , wherein each packet data structure includes one slot per reference to a memory object.

12. A method as claimed in claim 1 , wherein each packet data structure has a fixed size.