This seems like a simple question, but after a lot of reading on the subject, I still haven't found a definitive answer (perhaps because it is so simple).
My question is this: when a garbage collector compacts objects in the heap, how are the references to those objects in the stack updated? I can think of two possible solutions:
- Go through the stack (and references in the heap) and update the reference to point to the new location of the object. In an analogy to moving, this would be like sending a letter to anyone who has your address and asking them to update their address book with your new address.
- Provide some sort of look up table. This would be like leaving a forwarding address with the local post office.
Do garbage collectors predominantly use one of these two methods? Some other method? Both?
Best Answer
I have no specific expertise on this, but my understanding is that the first method is generally used.
The garbage collector has to analyze the stack anyways to find what things in the heap are referred to from the stack. Once it decides to move something, it has to correct references to it anyways, and there is no reason to differentiate between heap and stack at that point.
The lookup table approach in principle could work. However that would make all pointer accesses need to take 2 steps. That would be a huge performance impact on normal run times. Particularly for the use case of many small objects. (Which is a case where state of the art GC programs usually beat reference counting.)