US 2004/0167947 A1 · Space-efficient, depth-first parallel copying collection technique making use of work-stealing on the same structures that maintain the stack of items to be scanned

Abstract

A copying-type garbage collector operates in multiple concurrent threads. Each thread evacuates potentially reachable objects from the from space to the to space in a depth-first manner: if a thread has evacuated an object containing references to any from-space objects, it evacuates all of that object's descendants before it evacuates any other reachable objects. To keep track of descendants that must be evacuated before non-descendants can be, the thread places objects containing references to non-evacuated objects into a linked list maintained by pointers that it installs in the from-space locations from which the objects on the list were evacuated. Additionally, it divides the to space into local-allocation buffers (“LABs”) to which respective threads exclusively evacuate objects, and each thread maintains a LAB stack representing all the LABs it has filled that still contain references to unevacuated from-space objects. When a thread has completed evacuating the descendants of evacuees in all of its LABs, it “steals” work from other threads. It may do so, for instance, by processing a reference in an object belonging to another thread's list, by transferring to its own list one or more objects from another thread's list, or by transferring to its own LAB stack one or more LABs from another thread's LAB stack.

Claims62

Dependent claims

For executing in a plurality of execution threads a copying garbage collector that collects by evacuating to a to space from a from space at least any objects in the from space that are reachable from the to space and reclaiming the from space for re-use, a method comprising:

A) maintaining for each thread at least one linked list, associated with that thread, of evacuated objects containing references to potentially unevacuated objects by writing, in locations in the from space from which that thread has evacuated objects that contained such references, links to other such locations;
B) for each thread, processing objects in the list associated therewith by:
i) scanning those objects for references to objects in the from space that have not been evacuated;
ii) if such a reference exists in an object in that list, evacuating the object to which it refers;
and
iii) if no such reference exists in a given object in that list, removing the given object from that list;
and
C) employing at least one of the threads to:
i) scan for references to objects in the from space that have not been evacuated at least one object in the list associated with another of the threads;
and
ii) if such a reference exists, evacuating the object to which it refers.

8 more elements

For executing in a plurality of threads of execution a copying garbage collector that collects by evacuating potentially reachable objects from a from space to a to space and reclaiming the from space for re-use, a method comprising:

A) dividing the to space into local-allocation buffers;
B) employing at least one of the threads to:
i) maintain a LAB list associated therewith in which is listed at least one said local-allocation buffer into which that thread has evacuated at least one object that contains a reference to an object in the from space that has not been evacuated by that thread therefrom;
and
ii) continue to evacuate objects from the from space to the to space so long as a local-allocation buffer remains in the LAB list associated therewith;
and
C) employing at least one other thread to remove at least one local-allocation buffer from the LAB list associated with another said thread and to evacuate from the from space objects that are referred to by references located in at least one said local-allocation buffer thereby removed.

4 more elements

A computer system containing instructions executable thereby to implement in a plurality of execution threads a copying garbage collector that collects by evacuating to a to space from a from space at least any objects in the from space that are reachable from the to space and reclaiming the from space for re-use, wherein:

A) each thread maintains at least one linked list, associated therewith, of evacuated objects containing references to potentially unevacuated objects by writing, in locations in the from space from which that thread has evacuated objects that contained such references, links to other such locations;
B) each thread processes objects in the list associated therewith by:
i) scanning those objects for references to objects in the from space that have not been evacuated;
ii) if such a reference exists in an object in that list, evacuating the object to which it refers;
and
iii) if no such reference exists in a given object in that list, removing the given object from that list;
and
C) at least one of the threads:
i) scans for references to objects in the from space that have not been evacuated at least one object in the list associated with another of the threads;
and
ii) if such a reference exists, evacuates the object to which it refers.

8 more elements

A computer system containing instructions executable thereby to implement in a plurality of execution threads a copying garbage collector that collects by evacuating potentially reachable objects from a from space to a to space and reclaiming the from space for re-use, wherein:

A) the to space is divided into local-allocation buffers;
B) at least one of the threads:
i) maintains a LAB list associated therewith in which is listed at least one said local-allocation buffer into which that thread has evacuated at least one object that contains a reference to an object in the from space that has not been evacuated by that thread therefrom;
and
ii) continues to evacuate objects from the from space to the to space so long as a local-allocation buffer remains in the LAB list associated therewith;
and
C) at least one other said thread removes at least one local-allocation buffer from the LAB list associated with another thread and evacuates from the from space objects that are referred to by references located in at least one said local-allocation buffer thereby removed.

4 more elements

A storage medium containing instructions executable by a computer system to implement in a plurality of execution threads a copying garbage collector that collects by evacuating to a to space from a from space at least any objects in the from space that are reachable from the to space and reclaiming the from space for re-use, wherein:

A) each thread maintains at least one linked list, associated therewith, of evacuated objects containing references to potentially unevacuated objects by writing, in locations in the from space from which that thread has evacuated objects that contained such references, links to other such locations;
B) each thread processes objects in the list associated therewith by:
i) scanning those objects for references to objects in the from space that have not been evacuated;
ii) if such a reference exists in an object in that list, evacuating the object to which it refers;
and
iii) if no such reference exists in a given object in that list, removing the given object from that list;
and
C) at least one of the threads:
i) scans for references to objects in the from space that have not been evacuated at least one object in the list associated with another of the threads;
and
ii) if such a reference exists, evacuates the object to which it refers.

8 more elements

A storage medium containing instructions executable by a computer system to implement in a plurality of execution threads a copying garbage collector that collects by evacuating potentially reachable objects from a from space to a to space and reclaiming the from space for re-use, wherein:

A) the to space is divided into local-allocation buffers;
B) at least one of the threads:
i) maintains a LAB list associated therewith in which is listed at least one said local-allocation buffer into which that thread has evacuated at least one object that contains a reference to an object in the from space that has not been evacuated by that thread therefrom;
and
ii) continues to evacuate objects from the from space to the to space so long as a local-allocation buffer remains in the LAB list associated therewith;
and
C) at least one other said thread removes at least one local-allocation buffer from the LAB list associated with another thread and evacuates from the from space objects that are referred to by references located in at least one said local-allocation buffer thereby removed.

4 more elements

An electromagnetic signal representing sequences of instructions that, when executed by a computer system, cause the computer system to implement in a plurality of execution threads a copying garbage collector that collects by evacuating to a to space from a from space at least any objects in the from space that are reachable from the to space and reclaiming the from space for re-use, wherein:

A) each thread maintains at least one linked list, associated therewith, of evacuated objects containing references to potentially unevacuated objects by writing, in locations in the from space from which that thread has evacuated objects that contained such references, links to other such locations;
B) each thread processes objects in the list associated therewith by:
i) scanning those objects for references to objects in the from space that have not been evacuated;
ii) if such a reference exists in an object in that list, evacuating the object to which it refers;
and
iii) if no such reference exists in a given object in that list, removing the given object from that list;
and
C) at least one of the threads:
i) scans for references to objects in the from space that have not been evacuated at least one object in the list associated with another of the threads;
and
ii) if such a reference exists, evacuates the object to which it refers.

8 more elements

A) the to space is divided into local-allocation buffers;
B) at least one of the threads:
i) maintains a LAB list associated therewith in which is listed at least one said local-allocation buffer into which that thread has evacuated at least one object that contains a reference to an object in the from space that has not been evacuated by that thread therefrom;
and
ii) continues to evacuate objects from the from space to the to space so long as a local-allocation buffer remains in the LAB list associated therewith;
and
C) at least one other said thread removes at least one local-allocation buffer from the LAB list associated with another thread and evacuates from the from space objects that are referred to by references located in at least one said local-allocation buffer thereby removed.

4 more elements

Dependencies are inferred from the claim text.

Space-efficient, depth-first parallel copying collection technique making use of work-stealing on the same structures that maintain the stack of items to be scanned

Life of this patent

Space-efficient, depth-first parallel copying collection technique making use of work-stealing on the same structures that maintain the stack of items to be scanned

Life of this patent

Abstract

Claims62