tail of the list points to the head), then every object in the list has a reference to it—even
though no object in the list can actually be used, since no objects reference the list itself.
So references cannot be tracked dynamically via a count; instead, the JVM must periodically
search the heap for unused objects. When it finds unused objects, the JVM can free the
memory occupied by those objects and use it to allocate additional objects. However, it is
usually insufficient simply to keep track of that free memory and use it for future allocations;
at some point, memory must be coalesced to prevent memory fragmentation.
Consider the case of a program that allocates an array of 1,000 bytes, then one of 24 bytes,
and repeats that process in a loop. When that process fills up the heap, it will appear like the
top row in Figure 5-1 : the heap is full, and the allocations of the array sizes are interleaved.
Figure 5-1. Idealized GC heap during collection
When the heap is full, the JVM will free the unused arrays. Say that all the 24-byte arrays are
no longer in use, and the 1,000-byte arrays are still all in use: that yields the second row in
Figure 5-1 . The heap has free areas within it, but it can't actually allocate anything larger
than 24 bytes—unless the JVM moves all the 1,000-byte arrays so that they are contiguous,
leaving all the free memory in a region where it can be allocated as needed (the third row in
Figure 5-1 ).