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.
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?
- Maxime
Afficher les réponses par date
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
On 2011-03-03, at 4:24 PM, Marc Feeley wrote:
In a compacting GC, objects are reached by the GC in 2 ways:
to "mark" them: this is done by following a tagged reference
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.
I should add that the header can be eliminated if objects of a given type are allocated in an area dedicated to that type (the BIBOP GC technique for example). So if floats are allocated in a different region then no header is needed for them. This may sound appealing, but there are other issues:
1) Each region will have its own allocation pointer. When there is just one region, the unique allocation pointer can be stored at all times in a single machine register, so allocation is really cheap. If there are multiple allocation pointers then they need to be fetched from the context, and stored back in the context. An allocation will require more machine code, and it will be slower.
2) Having more than one region can introduce fragmentation because the regions don't fill up at the same rate. When a GC is triggered some of the regions will not be full. This problem can be reduced by reducing the size of regions, but then they overflow more often, and this has a run time cost.
If floats are your only concern there is a solution which avoids headers on floats and uses only one allocation pointer. The idea is to encode the header of objects using a bit pattern which would be a NaN which can't be generated by floating point operations. So that way it is possible to distinguish a memory allocated float from an object header when the GC sweeps through the objects. The problem with this is that fewer bits in object headers are available to encode the type and length information, so for objets (in particular those with variable length), an extra field may be needed.
Marc
-
chevalma＠iro.umontreal.ca -
Marc Feeley