Patent ID: 7043509

Claim:
A method of garbage collection comprising: A) providing a computer system that includes memory and executes a mutator that modifies references in a dynamically allocated heap in the memory; B) configuring the computer system to act as a garbage collector that executes in a plurality of threads in such a manner that: i) a first, scanning one of the threads can be performing a parsing operation in which the scanning thread parses memory space into memory blocks of which each includes a classifying word while a second, allocating one of the threads is performing an allocation operation for allocating, from a free block that is being parsed by the scanning thread and includes a length word, memory space to an object belonging to a class the length of each instance of which is ascertainable only by reading more than one word of that instance; ii) at least when the allocation operation is being performed for an object that is an instance of a class the length of each instance of which is ascertainable only by reading more than one word of that instance, the allocation operation for allocating memory space from a given free block for a given object comprises: a) placing an uninitialized-indicating value in the given block's classifying word; b) thereafter writing at least one word of the object in another field of the given free block; and c) thereafter replacing the uninitialized-indicating value by updating that classifying word in accordance with the class to which the object belongs; and iii) the scanning operation for a given block comprises: a) reading a classification value from the given block's classifying word; and b) performing a length-determination operation that: (1) if the classification value indicates that the given block contains an object, comprises employing class information located through the given block's classifying word to determine the length of the given block; (2) if the classification value is the uninitialized-indicating value, comprises: (a) re-reading the given block's classifying word; and (b) repeating the length-determination operation for the given block; and (3) if the classification value indicates that the given block is a free block, comprises: (a) reading a provisional length value from the given block's length field; (b) re-reading the given block's classifying word to determine whether the classifying value has changed; (c) if it has, repeating the length-determination operation for the given block; and (d) otherwise adopting the provisional length value as the length of the given block; and C) employing the computer system to execute the garbage collector.