Linear time processing of weak properties in a garbage collected environment

摘要

A method includes traversing pointers reachable from a root node, identifying an object, determining whether the identified object has a weak property, determining, when the identified object has a weak property, whether the key object referenced by the identified weak property is traversed by the garbage collector, if the key object associated with the identified weak property is traversed by the garbage collector, queuing the value object for later traversal, otherwise, marking the key object as being watched and appending an entry in a table mapping the key objects to a list with value object pointer locations as an entry and determining whether the identified object is visited for the first time by the garbage collector.

主权项

1. A computer-implemented method for linear time processing of weak properties in a computer program written in a garbage-collected programming language, the method comprising:
traversing, during a tracing routine performed by a garbage collector, pointers reachable from a root node; identifying an object, wherein the object represents a discrete storage location; determining whether the identified object has a weak property, the weak property including a pointer to a key object and a pointer to a value object; determining, when the identified object has a weak property, whether the key object referenced by the identified weak property is traversed by the garbage collector, wherein in a case the key object referenced by the identified weak property is traversed by the garbage collector, queuing the value object for later traversal, otherwise, marking the key object as being watched and appending an entry in a table mapping the key objects to a list with value object pointer locations; and determining whether the identified object is visited for the first time by the garbage collector, wherein in a case the identified object is visited for the first time:
checking whether the identified object is marked as being watched;retrieving a list of pointers watching the identified object;queuing the list of pointers for later traversal;removing a mark for watching the identified object; andremoving the identified object from the table mapping key objects to the retrieved list of pointers.