Apparatus and method for fast filtering read and write barrier operations in garbage collection system
First Claim
1. A method of reducing execution write/read barrier procedures in a computer system, comprising the steps of:
- (A) storing in a computer memory objects and object references for accessing the objects, each object reference including a State flag;
(B) executing instructions stored in the computer memory, a subset of the executed instructions having associated therewith a write/read barrier procedure;
wherein each instruction in the subset processes an object reference to a respective one of the objects stored in the computer memory;
(C) when executing each instruction that has an associated write/read barrier procedure,(C1) determining whether the State flag of the object reference being processed is set to a first predefined value;
(C2) when the determination in step C1 is positive, skipping execution of the write/read barrier procedure associated with the instruction being executed and proceeding with execution of a next instruction; and
(C3) when the determination in step C1 is negative, executing the write/read barrier procedure associated with the instruction being executed.
2 Assignments
0 Petitions
Accused Products
Abstract
In a computer system that utilizes write or read barriers to perform a garbage collection function, instruction execution logic avoids unnecessary calls to the write or read barrier procedure. Each object'"'"'s header includes a State flag. Each object reference also includes a State flag. Each time an instruction that is the subject of a write or read barrier (e.g., a object reference write instruction) is executed, the State flag of the object reference being processed is inspected by the instruction execution logic. If the State flag in the object reference is set, the write or read barrier procedure is not invoked, because the target object has already been processed by a previous call to the write or read barrier procedure. Otherwise the write or read barrier procedure is invoked. The write or read barrier procedure first checks the State flag in the target object'"'"'s header. If it is set, the State flag in the target object reference is set and then the procedure exits. Otherwise, if the State flag in the target object header is not set, a predefined garbage collection function is performed and then the State flag in the target object'"'"'s header and the State flag in the target object'"'"'s reference are both set. In some embodiments the setting of the State flags is conditional on the outcome of the garbage collection operation performed by the write or read barrier procedure.
118 Citations
20 Claims
-
1. A method of reducing execution write/read barrier procedures in a computer system, comprising the steps of:
-
(A) storing in a computer memory objects and object references for accessing the objects, each object reference including a State flag; (B) executing instructions stored in the computer memory, a subset of the executed instructions having associated therewith a write/read barrier procedure;
wherein each instruction in the subset processes an object reference to a respective one of the objects stored in the computer memory;(C) when executing each instruction that has an associated write/read barrier procedure, (C1) determining whether the State flag of the object reference being processed is set to a first predefined value; (C2) when the determination in step C1 is positive, skipping execution of the write/read barrier procedure associated with the instruction being executed and proceeding with execution of a next instruction; and (C3) when the determination in step C1 is negative, executing the write/read barrier procedure associated with the instruction being executed. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 18)
-
-
9. A method of executing an object reference write bytecode in a computer program in a computer system using generational garbage collection and a remembered set to store pointers to objects that may store references to other objects, comprising the steps of:
-
(A) executing an object reference write bytecode by writing a specified object reference into a specified field of a target object identified by a target object reference; (B) testing a State flag in the target object reference to determine whether the State flag is set or clear; (C) when the testing step determines that the State flag in the target object reference is clear, invoking a predefined write barrier procedure to perform a predefined write barrier operation; (D) when the testing step determines that the State flag in the target object reference is set, proceeding with execution of a next bytecode. - View Dependent Claims (10, 11)
-
-
12. A computer system that include a garbage collection mechanism, comprising:
-
a memory for storing objects and object references for accessing the objects, each object reference including a State flag; and a data processor for executing instructions stored in the computer memory, a subset of the executed instructions having associated therewith a write/read barrier procedure;
wherein each instruction in the subset processes an object reference that references a respective one of the objects stored in the computer memory;the data processor including instruction execution logic that, when executing each instruction that has an associated write/read barrier procedure, (C1) determines whether the State flag of the object reference being processed is set to a first predefined value; (C2) when the State flag value determination is positive, skips execution of the write/read barrier procedure associated with the instruction being executed and proceeds with execution of a next instruction; and (C3) when the State flag value determination is negative, invokes execution of the write/read barrier procedure associated with the instruction being executed. - View Dependent Claims (13, 14, 15, 16, 17)
-
-
19. A computer system that includes a generational garbage collection mechanism, comprising:
-
a memory for storing objects, object references for accessing the objects, and a predefined remembered set data structure, the predefined remembered set data structure storing a list of object references, each object reference including a State flag; and a data processor for executing bytecode instructions, including object reference write bytecode instructions for writing a datum into a specified field of a target object identified by a target object reference;
the object reference write bytecode instructions having associated therewith a write barrier procedure;the data processor including instruction execution logic that, when executing each object reference write bytecode instruction; (C1) determines whether the State flag of the target object reference is set to a first predefined value; (C2) when the State flag value determination is positive, skips execution of the write barrier procedure and proceeds with execution of a next bytecode instruction; and (C3) when the State flag value determination is negative, invokes execution of the write barrier procedure. - View Dependent Claims (20)
-
Specification