Method and program for space-efficient representation of objects in a garbage-collected system

1. A system comprising:

a memory which stores plural objects and is divided into plural pages, a page in said plural pages comprising a relocation base table (RBT) which is allocated at startup time based on a maximum heap size; and

a processor for executing a collector program to perform collection on said plural objects by:

encoding a class pointer of an object header for an object of said plural objects with a class index which comprises a class page table index and a class page offset and storing said class pointer in class page table;

storing a relocation address for a first live object of said plural objects in the relocation base table (RBT), and storing a relocation offset in the object header,

the relocation address for said object being given as a sum of a relocation base address for said object plus said relocation offset; and

storing a hashcode of said object in a mashtable which maintains a mapping of said plural objects to hashcode values which are computed based on a current address for said plural objects, said hashcode values being a hash index of said plural objects into said mashtable, said storing comprising:

if an entry is found and a key of the entry is the current address of said object, returning a corresponding value in the mashtable as said hashcode for said object, and

if no entry for the object is found in the mashtable, inserting a key/value pair where the key and the value are a current address for said object;

wherein after the object in said plural objects is determined to be live, and before any object is relocated, collection is performed on said mashtable such that a reference to a dead object is removed, and a key field for a moved object is undated to a new address and is relocated in the mashtable based on a new hashcode.

2. The system according to claim 1 , wherein available space in said object header is used for said relocation offset.

3. The system according to claim 1 , wherein no bits in a header of an object in said plural objects encode a hashcode state for said object.

4. The system according to claim 3 , wherein one bit in said header of said object encodes whether a mashtable entry exists for said object.

5. The system according to claim 1 , wherein said processor consults said mashtable to determine said hashcode for one of said plural objects.

6. The system according to claim 5 , wherein said object header comprises a class pointer and garbage collector state information in a single word.

7. The system according to claim 6 , wherein said processor accesses said class pointer by masking out non-class bits.

8. The system according to claim 1 , wherein said object header during said collection is different than said object header during program execution.

9. A system comprising:

a memory which stores plural objects and is divided into plural pages, a page in said plural pages comprising a relocation base table (RBT) which is allocated at startup time based on a maximum heap size; and

a processor which executes a program to perform collection on said plural objects by:

encoding a class pointer of an object header for an object of said plural objects with a class index which comprises a class page table index and a class page offset and storing said class pointer in a class page table;

storing a relocation address for a first live object of said plural objects in the relocation base table (RBT), and storing a relocation offset in the object header, the relocation address for said object being given as a sum of a relocation base address for said object plus said relocation offset; and

eliminating all extra state from said object header by storing a hashcode of said object in a mashtable which maintains a mapping of said plural objects to hashcode values which are computed based on a current address for said plural objects, said hashcode values being a hash index of said plural objects into said mashtable, said storing comprising:

if an entry is found and a key of the entry is the current address of said object, returning a corresponding value in the mashtable as said hashcode for said object, and

if no entry for the object is found in the mashtable, inserting a key/value pair where the key and the value are a current address for said object;

wherein after the object in said plural objects is determined to be live, and before any object is relocated, collection is performed on said mashtable such that a reference to a dead object is removed, and a key field for a moved object is undated to a new address and is relocated in the mashtable based on a new hashcode.

10. The system according to claim 9 , wherein said mashtable is consulted when a hashCode method for an object in said plural objects is called.

11. A system comprising:

a memory which stores plural objects and is divided into plural pages, a page in said plural pages comprising a relocation base table (RBT) which is allocated at startup time based on a maximum heap size;

a processor for executing a program to perform collection on said plural objects by:

storing a class pointer and garbage collector state information in a single word, comprising:

encoding a class pointer of an object header for an object of said plural objects with a class index which comprises a class page table index and a class page offset and storing said class pointer in class page table;

storing a relocation address for a first live object of said plural objects in the relocation base table (RBT), and storing a relocation offset in the object header, the relocation address for said object being given as a sum of a relocation base address for said object plus said relocation an offset; and

eliminating all extra state from said object header by storing a hashcode of said object in a mashtable which maintains a mapping of said plural objects to hashcode values which are computed based on a current address for said plural objects, said hashcode values being a hash index of said plural objects into said mashtable, said storing comprising:

if an entry is found and a key of the entry is the current address of said object, returning a corresponding value in the mashtable as said hashcode for said object, and

if no entry for the object is found in the mashtable, inserting a key/value pair where the key and the value are a current address for said object;

wherein after the object in said plural objects is determined to be live, and before any object is relocated, collection is performed on said mashtable such that a reference to a dead object is removed, and a key field for a moved object is undated to a new address and is relocated in the mashtable based on a new hashcode.

12. The system according to claim 11 , wherein garbage collector state bits are represented such that said garbage collector state bits comprise 0 when said collection is not in progress.

13. The system according to claim 11 , wherein said class pointer is accessed without masking when said collection is off.

14. A method of collection, comprising:

storing plural objects in a memory which is divided into plural pages, a page in said plural pages comprising a relocation base table (RBT) which is allocated at startup time based on a maximum heap size; and

executing a program by a processor to perform collection on said plural objects, said collection comprising:

encoding a class pointer of an object header for an object of said plural objects with a class index which comprises a class page table index and a class page offset and storing said class pointer in class page table;

storing a relocation address for a first live object of said plural objects in the relocation base table (RBT), and storing a relocation offset in the object header, the relocation address for said object being given as a sum of a relocation base address for said object plus said relocation offset; and

eliminating all extra state from said object header by storing a hashcode of said object in a mashtable which maintains a mapping of said plural objects to hashcode values which are computed based on a current address for said plural objects, said hashcode values being a hash index of said plural objects into said mashtable, said storing comprising:

if an entry is found and a key of the entry is the current address of said object, returning a corresponding value in the mashtable as said hashcode for said object, and

if no entry for the object is found in the mashtable, inserting a key/value pair where the key and the value are a current address for said object;

wherein after the object in said plural objects is determined to be live, and before any object is relocated, collection is performed on said mashtable such that a reference to a dead object is removed, and a key field for a moved object is undated to a new address and is relocated in the mashtable based on a new hashcode.

15. The method according to claim 14 , further comprising:

storing said class pointer and garbage collector state information in a single word of said object header; and

accessing said class pointer by masking out non-class bits.

16. A programmable storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of collection, said method comprising:

storing plural objects in a memory which is divided into plural pages, a page in said plural pages comprising a relocation base table (RBT) which is allocated at startup time based on a maximum heap size; and

executing a program to perform collection on said plural objects, said collection comprising:

encoding a class pointer of an object header for an object of said plural objects with a class index which comprises a class page table index and a class page offset and storing said class pointer in a class page table;

storing a relocation address for a first live object of said plural objects in the relocation base table (RBT), and storing a relocation offset in the object header, the relocation address for said object being given as a sum of a relocation base address for said object plus said relocation offset; and

eliminating all extra state from said object header by storing a hashcode of said object in a mashtable which maintains a mapping of said plural objects to hashcode values which are computed based on a current address for said plural objects, said hashcode values being a hash index of said plural objects into said mashtable, said storing comprising:

if an entry is found and a key of the entry is the current address of said object, returning a corresponding value in the mashtable as said hashcode for said object, and

if no entry for the object is found in the mashtable, inserting a key/value pair where the key and the value are a current address for said object;

wherein after the object in said plural objects is determined to be live, and before any object is relocated, collection is performed on said mashtable such that a reference to a dead object is removed, and a key field for a moved object is updated to a new address and is relocated in the mashtable based on a new hashcode.

17. The programmable storage medium according to claim 16 , wherein said method further comprises:

storing said class pointer and garbage collector state information in a single word of said object header; and

accessing said class pointer by masking out non-class bits.