On 2011-03-03, at 4:02 PM, chevalma@iro.umontreal.ca wrote:
I have been wondering if we could save a little space by only including object headers on some objects but not all. If we can refactor to eliminate the ref type, then all object references will be boxed. Right now, some heap-allocated objects have reserved tag bits (eg: floats, strings, objects, functions, arrays), and others do not (e.g.: the hash consing table). The objects that don't have tags of their own all share the "other" tag.
If all we need a header for is for the GC to identify what kind of object it's dealing with, then perhaps we only need a header for the objects that share the "other" tag. Other object kinds could be identifier through the tag bits. This would allow small objects like floats to be heap-allocated without requiring a tag.
Marc, you mentioned the need for a size field in objects as well. I think we may be able to only require objects that have a variable size to have such a field. Strings, for example, can have a variable length, and contain a field to say how many characters they contain, from which the total object size in bytes can be computed. Objects like heap-allocated floats, however, have a fixed size determined solely by the object type.
So, the real question is, do we need a header for any other purpose besides identifying the object type? If we need a certain amount of status bits on all objects, for example, then we may want to include the header on all objects, but if not, then this optimization could be implemented without much difficulty.
In a compacting GC, objects are reached by the GC in 2 ways:
1) to "mark" them: this is done by following a tagged reference
2) to "move" them (or "update" them): this is done by sweeping the objects, so a tagged reference is not available... it is the object's header which identifies which type of object it is and the length (which are necessary to know the object's layout).
So we need a header on all objects that may be moved. We could avoid headers on objects that are not moved. On the other hand, having a uniform layout simplifies other things.
A last issue I would like to know your opinion about is the alignment of fields within objects. Do you think that fields within objects should be aligned to pointer size boundaries? I believe on 32 bit MIPS you can only load at 4 byte boundaries. Does this matter on x86 32-64? For example, if an object header on a 64 bit machine is 32 bits, should there be 32 bits of padding between it and the next field, assuming that next field is 64 bits in size?
Yes. If you don't do this, then a 32 bit slot may overlap two cache lines, so it may burden the caches needlessly.
Marc