18

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:

  1. 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.
  2. 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?

Improve this question
3
  • See stackoverflow.com/questions/3799203/… and en.wikipedia.org/wiki/…
    – Gort the Robot
    Mar 7, 2013 at 3:02
  • @StevenBurnap correct me if I'm wrong, but I belief the thread you linked to didn't have any definitive answers. They seemed to be speculating on this exact question as well. I may have misread. If they did provide an answer to the question, if you wouldn't mind, I think it would be helpful to summarize the answer here for future SE users (and myself!)
    – todorojo
    Mar 7, 2013 at 19:28
  • The term for the thing you are talking about is a "moving garbage collector". I frankly don't know how commonly used they are.
    – Gort the Robot
    Mar 7, 2013 at 21:08

1 Answer 1

Reset to default
9

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.)

Improve this answer
4
  • 3
    I would add that I think GC's probably try not to move things on the heap unless they have to. In today's multi-processor world it must be a synchronization nightmare when they need to update all references to something on the heap while a program that uses those references is running. The lookup table would simplify this, but I think that's the exception rather than the norm, so most GC's probably have to lock some references, move the memory, then update the references. +1 Interesting question, +1 good answer.
    – GlenPeterson
    Mar 7, 2013 at 4:36
  • 3
    @GlenPeterson Many GCs do indeed not move things on the heap, and don't face this problem. But a compacting GC by definition moves live objects around to defragment memory.
    – btilly
    Mar 7, 2013 at 5:41
  • @GlenPeterson it's a good observation that moving stuff on the heap is a huge synchronization pain, this is oft overlooked though GC compaction has huge ripple effects on a running process due to this. It's the single largest reason people are told to do everything they can to keep objects as short-lived as possible, to avoid large heap updates causing compaction to hold a long mutex. Ignorance of the way this stuff behaves can lead to what is lovingly referred to as GC Freakout Mode.
    – Jimmy Hoffa
    Mar 8, 2013 at 1:40
  • 2
    The original Macintosh and Palm OS both used a lookup-table approach for its memory management. Pointers into the table were referred to as handles. A relocating GC must know the whereabouts of absolutely positively every reference to any object that it's moving; using a single table for such purposes simplifies things greatly.
    – supercat
    Dec 24, 2013 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.