Scanning of evacuated objects in a generation managed by the train algorithm
First Claim
1. A method for employing a computer system including memory as a garbage collector that treats a generation of a heap in the memory as divided into cars grouped into trains ordered in a nominal collection order and collects in collection increments respective collection sets of those cars in accordance with the train algorithm, wherein, in at least some of the collection increments:
- A) for a car of said cars in a train of said trains, a remembered set and a virtual table (vtable) are associated with said car and a scratch-pad-list is associated with the train, wherein the vtable is separate from the remembered set;
B) said vtable stores a pointer to an operation related to said car to be performed,wherein said operation to be performed includes the step of modifying the pointer stored in said vtable to reference a different operation related to said car, such that a subsequent reference to said vtable results in the modified pointer invoking the different operation related to said car to be performed by said program;
C) said operation to be performed is an insertion operation;
D) in the case of said car being a normal car, the pointer to said insertion operation invokes an operation in which an entry is inserted into said remembered set associated with said car;
E) in the case of said car being a special car which has a predetermined number of entries in said remembered set associated with said car, the pointer to said insertion operation invokes an operation in which a further entry is not inserted into said remembered set when said further entry relates to an object in a car which car is not younger than all of the cars associated with existing entries in said remembered set; and
F) in the case of said car being a special car which has fewer than said predetermined number of entries in said remembered set associated with the car, the pointer to said insertion operation invokes an operation in which a further entry is inserted into said remembered set, and in the event that said insertion causes the number of entries in the remembered set to reach said predetermined number, said operation modifies said pointer contained in said vtable, such that a subsequent reference to said vtable associated with said car results in the modified pointer invoking the insertion operation according to step C).
2 Assignments
0 Petitions
Accused Products
Abstract
In computer systems including memory which execute programs of instructions, vtables associated with objects contain pointers which invoke operations to be performed by the program which are related to the objects. The operation invoked may include the step of modifying the pointer such that upon a subsequent reference to the vtable a different operation is invoked. In one embodiment, such vtables are utilized in conjunction with garbage collection methodologies such as those that invoke the train algorithm, such that operations such as reference processing, insertion and scanning during garbage collection may be invoked by pointers in vtables associated with cars or objects in the cars, and the vtables may invoke differing versions of the said operations depending on the characteristics and past history of the car or object, and upon an operation being executed the operation may change the pointer so that a different version of the operation is performed upon a subsequent reference to the vtable associated with the car or object.
-
Citations
24 Claims
-
1. A method for employing a computer system including memory as a garbage collector that treats a generation of a heap in the memory as divided into cars grouped into trains ordered in a nominal collection order and collects in collection increments respective collection sets of those cars in accordance with the train algorithm, wherein, in at least some of the collection increments:
-
A) for a car of said cars in a train of said trains, a remembered set and a virtual table (vtable) are associated with said car and a scratch-pad-list is associated with the train, wherein the vtable is separate from the remembered set; B) said vtable stores a pointer to an operation related to said car to be performed, wherein said operation to be performed includes the step of modifying the pointer stored in said vtable to reference a different operation related to said car, such that a subsequent reference to said vtable results in the modified pointer invoking the different operation related to said car to be performed by said program; C) said operation to be performed is an insertion operation; D) in the case of said car being a normal car, the pointer to said insertion operation invokes an operation in which an entry is inserted into said remembered set associated with said car; E) in the case of said car being a special car which has a predetermined number of entries in said remembered set associated with said car, the pointer to said insertion operation invokes an operation in which a further entry is not inserted into said remembered set when said further entry relates to an object in a car which car is not younger than all of the cars associated with existing entries in said remembered set; and F) in the case of said car being a special car which has fewer than said predetermined number of entries in said remembered set associated with the car, the pointer to said insertion operation invokes an operation in which a further entry is inserted into said remembered set, and in the event that said insertion causes the number of entries in the remembered set to reach said predetermined number, said operation modifies said pointer contained in said vtable, such that a subsequent reference to said vtable associated with said car results in the modified pointer invoking the insertion operation according to step C). - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A computer system including memory and configured as a garbage collector that treats a generation of a heap in the memory as divided into cars grouped into trains ordered in a nominal collection order and collects in collection increments respective collection sets of those cars in accordance with the train algorithm, wherein, in at least some of the collection increments:
-
A) for a car of said cars in a train of said trains, a remembered set and a virtual table (vtable) are associated with said car and a scratch-pad-list is associated with the train, wherein the vtable is separate from the remembered set; and B) said vtable stores a pointer to an operation related to said car to be performed, wherein said operation to be performed includes the step of modifying the pointer stored in said vtable to reference a different operation related to said car, such that a subsequent reference to said vtable results in the modified pointer invoking the different operation related to said car to be performed by said program; C) said operation to be performed is an insertion operation; D) in the case of said car being a normal car, the pointer to said insertion operation invokes an operation in which an entry is inserted into said remembered set associated with said car; E) in the case of said car being a special car which has a predetermined number of entries in said remembered set associated with said car, the pointer to said insertion operation invokes an operation in which a further entry is not inserted into said remembered set when said further entry relates to an object in a car which car is not younger than all of the cars associated with existing entries in said remembered set; and F) in the case of said car being a special car which has fewer than said predetermined number of entries in said remembered set associated with the car, the pointer to said insertion operation invokes an operation in which a further entry is inserted into said remembered set, and in the event that said insertion causes the number of entries in the remembered set to reach said predetermined number, said operation modifies said pointer contained in said vtable, such that a subsequent reference to said vtable associated with said car results in the modified pointer invoking the insertion operation according to step C). - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
-
17. A storage medium containing instructions readable by a computer system including memory to configure the computer system as a garbage collector that treats a generation of a heap in the memory as divided into cars grouped into trains ordered in a nominal collection order and collects in collection increments respective collection sets of those cars in accordance with the train algorithm, wherein, in at least some of the collection increments:
-
A) for a car of said cars in a train of said trains, a remembered set and a virtual table (vtable) are associated with said car and a scratch-pad-list is associated with the train, wherein the vtable is separate from the remembered set; B) said vtable stores a pointer to an operation related to said car to be performed, wherein said operation to be performed includes the step of modifying the pointer stored in said vtable to reference a different operation related to said car, such that a subsequent reference to said vtable associated with said car results in the modified pointer invoking the different operation related to said car to be performed by said program; C) said operation to be performed is an insertion operation; D) in the case of said car being a normal car, the pointer to said insertion operation invokes an operation in which an entry is inserted into said remembered set associated with said car; E) in the case of said car being a special car which has a predetermined number of entries in said remembered set associated with said car, the pointer to said insertion operation invokes an operation in which a further entry is not inserted into said remembered set when said further entry relates to an object in a car which car is not younger than all of the cars associated with existing entries in said remembered set; and F) in the case of said car being a special car which has fewer than said predetermined number of entries in said remembered set associated with the car, the pointer to said insertion operation invokes an operation in which a further entry is inserted into said remembered set, and in the event that said insertion causes the number of entries in the remembered set to reach said predetermined number, said operation modifies said pointer contained in said vtable, such that a subsequent reference to said vtable associated with said car results in the modified pointer invoking the insertion operation according to step C). - View Dependent Claims (18, 19, 20, 21, 22, 23, 24)
-
Specification