Java Reference
In-Depth Information
adjacent free blocks, though maintenance of the list in sorted order is now
more expensive.
When a request for
n
bytes of heap space is received, the heap allocator
must search the free space list for a block of su
cient size. But how much
of the free space list is to be searched? (It may contain many thousands of
blocks.) What if no free block exactly matches the current request? There are
many approaches that might be used. We will consider briefly a few of the
most widely used techniques.
Best Fit
The free space list is searched, perhaps exhaustively, for the free
block that most closely matches the requested size. This minimizes wasted
heap space, though it may create tiny fragments too small to be used very
often. If the free space list is very long, a best fit search may be quite slow.
Segregated free space lists (see below) may be preferable.
First Fit
The first free heap block of su
cient size is used. Unused space
within the block is split o
and linked as a smaller free space block. This
approach is fast, but may “clutter” the beginning of the free space list with a
number of blocks too small to satisfy most requests.
ff
Next Fit
This is a variant of first fit in which succeeding searches of the free
space list begin at the position where the last search ended rather than at the
head of the list. The idea is to “cycle through” the entire free space list rather
than always revisiting free blocks at the head of the list. This approach reduces
fragmentation
(in which blocks are split into small, di
cult to use pieces).
However, it also reduces locality (how densely packed active heap objects
are). If we allocate heap objects that are widely distributed throughout the
heap, we may increase cache misses and page faults, significantly impacting
performance.
Segregated Free Space Lists
There is no reason why we must have only
one
free space list. An alternative is to have several, indexed by the size of the
free blocks they contain. Experiments have shown that programs frequently
request only a few “magic sizes.” If we divide the heap into segments, each
holding only one size, we can maintain individual free space lists for each
segment. Because heap object size is fixed, no headers are needed.
A variant of this approach is to maintain lists of objects of special “strate-
gic” sizes (16, 32, 64, 128, etc.) When a request for size
s
is received, a block of
the smallest size
≤
s
is selected (with excess size unused within the allocated
block).
