US 2009/0265402 A1Published application

Efficiently marking objects with large reference sets

AssigneeMicrosoft Corporation

InventorsPatrick H. Dussud, Maoni Z. Stephens

Life of this patent

Estimating the term…

Loading patent…

Abstract

Adding references to objects to a mark stack. A limited number of references to objects referenced by an object with a large number of object references are added to the stack. An object is accessed. A determination is made that references in the object should be added to a mark stack using a reference in the mark stack to the object in conjunction with a pointer. The pointer is used to track which references in the object have been placed on the mark stack. A reference to the object on the mark stack is accessed. A pointer is initialized. A reference to another object referenced by the object is pushed onto the mark stack. The pointer is incremented. It is then determined that that more references should be pushed to the mark stack. Acts of pushing references onto the mark stack and incrementing the pointer are repeated.

Claims20

Dependent claims

In a computing environment including application code that implements garbage collection functionality for reclaiming memory for use with new objects, wherein the garbage collection functionality includes pushing object references onto a mark stack, such that objects referenced on the mark stack can be marked so as to prevent memory for the marked objects from being recycled for use with other objects instances, a method of adding references to objects to the mark stack in a manner that allows a limited number of references to objects referenced by an object with a large number of object references to be added to the stack, the method comprising:

(a) accessing an object;
(b) determining that references in the object should be added to a mark stack using a reference or an entry based on the reference in the mark stack to the object itself in conjunction with a pointer, the pointer being used to track which references in the object have been pushed on the mark stack, the mark stack being configured to allow for marking of objects pushed on the marked stack to prevent memory for the objects referenced on the mark stack from being reclaimed for other objects;
(c) accessing the reference or an entry based on the reference to the object on the mark stack;
(d) initializing a pointer;
(e) pushing one or more references to one or more other objects referenced by the object onto the mark stack;
and
(f) updating the pointer.

4 more elements

In a computing environment including application code that implements garbage collection functionality for reclaiming memory for use with new objects, wherein the garbage collection functionality includes pushing object references onto a mark stack, such that objects referenced on the mark stack can be marked so as to prevent memory for the marked objects from being recycled for use with other objects instances, a method of processing references to objects on the mark stack in a manner that allows a limited number of references to objects referenced by an object with a large number of object references to be added to the stack, the method comprising:

(a) determining that a mark stack includes a reference or an entry based on the reference in the mark stack to an object itself used in conjunction with a pointer, the pointer being used to track which references in the object have been pushed on the mark stack the mark stack being configured to allow for marking of objects pushed on the marked stack to prevent memory for the objects referenced on the mark stack from being reclaimed for other objects;
(b) pushing a reference from the object onto the mark stack;
(c) performing act (b) a predetermined number of times;
(d) incrementing the pointer;
(e) after performing act (b) the predetermined number of times and act (c) processing and popping references from the mark stack until the reference or an entry based on the reference in the mark stack to the object itself is in a position to be read from the mark stack.

2 more elements

(a) accessing an object;
(b) determining that references in the object should be added to a mark stack using a reference or an entry based on the reference in the mark stack to the object itself in conjunction with a pointer, the pointer being used to track which references in the object have been pushed on the mark stack, the mark stack being configured to allow for marking of objects pushed on the marked stack to prevent memory for the objects referenced on the mark stack from being reclaimed for other objects;
(c) accessing the reference or an entry based on the reference to the object on the mark stack;
(d) initializing a pointer;
(e) pushing a reference to another object referenced by the object onto the mark stack;
(f) after pushing references to another object, determining that more references should be pushed to the mark stack, and as a result, repeating act (e);
(g) updating the pointer;
(h) processing references from the mark stack until the reference or an entry based on the reference to the object is in a position to be read from the mark stack;
(i) after processing references from the mark stack, determining that more references from the object should be added to the mark stack, and as a result, repeating acts (e), (f), and (g);
(j) determining that no more references from the object should be added to the mark stack, and as a result, popping the reference or an entry based on the reference in the mark stack to the object itself from the mark stack.

7 more elements

Dependencies are inferred from the claim text.