10.5. Freelists¶
10.5.1. Freelists¶
The new operator is relatively expensive to use.
Garbage collection is also expensive.
A memory manager
handles general-purpose memory requests.
The expense comes from the fact that free store routines must
be capable of handling requests to and from free store with no
particular pattern, as well as memory requests of vastly different
sizes.
This, combined with unpredictable freeing of space by the garbage
collector, makes them inefficient compared to what might be
implemented for more controlled patterns of memory access.
List nodes are created and deleted in a linked list
implementation in a way that allows the Link class programmer
to provide simple but efficient memory management routines.
Instead of making repeated calls to new,
the Link class can handle its own freelist.
A freelist holds those list nodes that are not currently being used.
When a node is deleted from a linked list, it is placed at the
head of the freelist.
When a new element is to be added to a linked list, the freelist
is checked to see if a list node is available.
If so, the node is taken from the freelist.
If the freelist is empty, the standard new operator must then
be called.
So we see that the freelist is simply
an application of a linked stack.
Freelists are particularly useful for linked lists that periodically grow and then shrink. The freelist will never grow larger than the largest size yet reached by the linked list. Requests for new nodes (after the list has shrunk) can be handled by the freelist. Another good opportunity to use a freelist occurs when a program uses multiple lists. So long as they do not all grow and shrink together, the free list can let link nodes move between the lists.
In the implementation shown here, the Link class is augmented with
methods get and release. [1]
class Link<E> { // Singly linked list node with freelist support
private E e; // Value for this node
private Link<E> n; // Point to next node in list
// Constructors
Link(E it, Link<E> inn) { e = it; n = inn; }
Link(Link<E> inn) { e = null; n = inn; }
E element() { return e; } // Return the value
E setElement(E it) { return e = it; } // Set element value
Link<E> next() { return n; } // Return next link
Link<E> setNext(Link<E> inn) { return n = inn; } // Set next link
// Extensions to support freelists
private static Link freelist = null; // Freelist for the class
// Return a new link, from freelist if possible
static <E> Link<E> get(E it, Link<E> inn) {
if (freelist == null) {
return new Link<E>(it, inn); // Get from "new"
}
Link<E> temp = freelist; // Get from freelist
freelist = freelist.next();
temp.setElement(it);
temp.setNext(inn);
return temp;
}
// Return a link node to the freelist
void release() {
e = null; // Drop reference to the element
n = freelist;
freelist = this;
}
}
class Link { // Singly linked list node with freelist support
private Object e; // Value for this node
private Link n; // Point to next node in list
// Constructors
Link(Object it, Link inn) { e = it; n = inn; }
Link(Link inn) { e = null; n = inn; }
Object element() { return e; } // Return the value
Object setElement(Object it) { return e = it; } // Set element value
Link next() { return n; } // Return next link
Link setNext(Link inn) { return n = inn; } // Set next link
// Extensions to support freelists
static Link freelist = null; // Freelist for the class
// Return a new link, from freelist if possible
static Link get(Object it, Link inn) {
if (freelist == null)
return new Link(it, inn); // Get from "new"
Link temp = freelist; // Get from freelist
freelist = freelist.next();
temp.setElement(it);
temp.setNext(inn);
return temp;
}
// Return a link node to the freelist
void release() {
e = null; // Drop reference to the element
n = freelist;
freelist = this;
}
}
The freelist variable declaration uses the keyword static.
This creates a single variable shared among all instances of the
Link nodes.
In this way, a single freelist is shared by all Link nodes.
Note how simple they are, because they need only remove and add an
element to the front of the freelist, respectively.
The freelist methods get and release both run in
\(\Theta(1)\) time, except in the case where the freelist is
exhausted and the new operation must be called.
Here are the necessary modifications to members of the linked list
class to make use of the freelist version of the link class.
// Insert "it" at current position
public boolean insert(E it) {
curr.setNext(Link.get(curr.element(), curr.next())); // Get link
curr.setElement(it);
if (tail == curr) { tail = curr.next(); } // New tail
listSize++;
return true;
}
// Append "it" to list
public boolean append(E it) {
Link<E> temp = Link.get(null, null);
tail.setNext(temp);
tail.setElement(it);
tail = tail.next();
listSize++;
return true;
}
// Remove and return current element
public E remove () {
if (curr == tail) { return null; } // Nothing to remove
E it = curr.element(); // Remember value
curr.setElement(curr.next().element()); // Pull forward the next element
if (curr.next() == tail) { tail = curr; } // Removed last, move tail
Link<E> tempptr = curr.next(); // Remember the link
curr.setNext(curr.next().next()); // Point around unneeded link
tempptr.release(); // Release the link
listSize--; // Decrement element count
return it; // Return value
}
// Insert "it" at current position
public boolean insert(Object it) {
curr.setNext(Link.get(curr.element(), curr.next())); // Get link
curr.setElement(it);
if (tail == curr) tail = curr.next(); // New tail
listSize++;
return true;
}
// Append "it" to list
public boolean append(Object it) {
tail.setNext(Link.get(null, null));
tail.setElement(it);
tail = tail.next();
listSize++;
return true;
}
// Remove and return current element
public Object remove () {
if (curr == tail) return null; // Nothing to remove
Object it = curr.element(); // Remember value
curr.setElement(curr.next().element()); // Pull forward the next element
if (curr.next() == tail) tail = curr; // Removed last, move tail
Link tempptr = curr.next(); // Remember the link
curr.setNext(curr.next().next()); // Point around unneeded link
tempptr.release(); // Release the link
listSize--; // Decrement element count
return it; // Return value
}
How much time is saved by using freelists depends on the language that
you are programming in.
In a language like C++ where the programmer must call new and
delete to manage memory, getting a node from your own freelist
requires less than one tenth of the time required by the new
operator.
In a language like Java that uses garbage collection, it might at
first appear that using your own freelist saves no time, because
Java’s new operator can quickly return space from the current
start of its memory pool.
However, when you do not use a freelist, dropping access to nodes
creates garbage which leads to expensive processing at garbage
collection time.
