Java Reference
In-Depth Information
Global pointer
Adjusted Global pointer
Adjusted internal pointer
Object 1
Object 3
Object 5
Figure 12.17: Mark-Sweep Garbage Collection with Compaction
Moreover, heap allocation is greatly simplified. The compacting collector
maintains an “end of heap” pointer. Whenever it receives an allocation request,
it adjusts the end of heap pointer, making heap allocation no more complex
than stack allocation.
However, because pointers must be adjusted, compaction may not be
suitable for languages like C andC
++
, inwhich it is di
cult to unambiguously
identify pointers.
Copying Collectors
Compaction provides many valuable benefits. Heap
allocation is simple and e
cient. There is no fragmentation problem, and
because live objects are adjacent, paging and cache behavior is improved.
An entire family of garbage collection techniques, called
copying collectors
,
have been designed to integrate copying with recognition of live heap objects.
These copying collectors are very popular and arewidely used, especiallywith
functional languages like ML.
The following is a simple copying collector that uses
semispaces
.Westart
with the heap divided into two halves: the
from space
and
to space
. Initially,
we allocate heap requests from the
from space
, using a simple “end of heap”
pointer. When the
from space
is exhausted, we stop and do garbage collection.
Actually, though, we
do not
collect garbage. What we do is collect live heap
objects; garbage is never touched. As was the case for mark-sweep collectors,
we trace through global and local pointers to find live objects. As each object
is found, it is moved from its current position in the
from space
to the next
available position in the
to space
. The pointer is updated to reflect the object's
new location. A “forwarding pointer” is left in the object's old location in case
there are multiple pointers to the same object. (We want all original pointers
properly updated to the new object location.)
This is illustrated in Figure 12.18. The
from space
is completely filled. We
trace global and local pointers, moving live objects to the
to space
and updating
pointers. This is illustrated in Figure 12.19 (dashed arrows are forwarding
pointers). To handle pointers that are internal to copied heap objects, all
copied heap objects are traversed. Objects referenced are copied and internal
pointers are updated. Finally, the
to
and
from spaces
are interchanged, and