Copying Garbage Collector

Question

How does a copying garbage collector avoid memory fragmentation? Also, what consequences for heap-space use?

From my understanding, a copying garbage collector, copies all reachable objects from the heap into another section of the heap. All objects that have been left behind are no longer needed and thus removed.

If this is a correct understanding, how does this avoid memory fragmentation?

This process must use a lot of heap-space, because it will have duplicates of all items it copied, right?

Answer 1

If this is a correct understanding, how does this avoid memory fragmentation?

Because when you copy the objects to the "new heap", you stick them right next to each other without leaving any gaps.

This process must use a lot of heap-space, because it will have duplicates of all items it copied, right?

Only during the collection process. After you've done that, all the "originals" are deallocated and that space is freed up again.

Additionally, garbage collectors like this are often "generational" - copying garbage collection is used on short-lived objects, with longer-lived objects being treated differently. This helps ease the space issue, as well as making collections take less time.

Answer 2

Your basic understanding is correct. It avoids fragmentation because as it copies the reachable objects, it can put then close together, leaving free space in one block. it does require lots of space, in fact, it requires potentially 2x the space plus some change for bookkeeping.

Answer 3

Memory fragmentation occurs when chunks of memory are deallocated in between two active chunks. Think of a block of memory like so...

AAAAAAAAAAAAAAAABBBBCCCCCCCCCCCC

Assume that B is no longer needed. If we free up the space that B was using we having something like...

AAAAAAAAAAAAAAAA----CCCCCCCCCCC

Now we have a gap that we can only put rather small objects in. A copying garbage collector might move things around so that we have...

AAAAAAAAAAAAAAAACCCCCCCCCCC---- (more free space here)

Most modern collectors can move things in-place. That is, you can see how C could be "shifted" to take up B's old space and thus there is no memory overhead.