On 14/03/2012 16:51, Warp wrote:
> Invisible<voi### [at] devnull>  wrote:
>> The GC engine needs to know quite a bit about the objects it's scanning
>> - how big they are, where their pointer fields are, etc.
>
>    Exactly how does the GC engine know how large a block of allocated
> memory is? Where is this information stored?

Usually the object's class tells you that. You already have a vtable or 
similar structure. (At least, you do in languages where /everything/ is 
dynamically bound by default.)

>    Also, if objects are transparently movable in memory without breaking
> the references pointing to them, that means that in addition to the
> reference the actual raw memory address of the object has to also be
> stored somewhere. Where is this information stored?

Depends on the implementation.

Smalltalk does it by adding a layer of indirection. The address of every 
object in the system is held in a giant "object table". All objects are 
referred to be object IDs, which are merely indices into this table. To 
move an object, merely update its object table entry. (You can also 
store auxiliary information here - e.g., if you wanted to /lock/ the 
object while it's being moved.)

How Haskell does it is to copy each object from its old location to its 
new location, and then overwrite the old copy with a "hey, this is where 
I moved this object to" reference. The GC engine then uses that to 
update any references in other objects as it finds them.

>    You can't avoid bookkeeping when you are allocating blocks of variable
> size.

Sure. At a minimum, you need to know the size of those blocks. 
Realistically, you also need to know what they contain, or you can't 
follow pointers. You probably need to know a little other stuff too.

Most of this information is per-class rather than per-object, however.

Post a reply to this message