Mike said:
Peter said:
In fact, even the example Lew gives of a Stack is in reality
unlikely
to require specific handling. In particular, if you're actually
_done_ with the Stack, simply getting rid of the reference to the
Stack itself is sufficient for releasing all the objects that the
Stack itself references.
The issue witrh stacks (and ArrayLists) is that a naive implementation
retains unnecessary references to objects. Assume something like:
(not tested or compiled, so please ignore any typos, as well as the
fact that neither overflow nor underflow is handled.)
public class SimpleStack
{
private Object stack[] = new Object[MAX_SIZE];
int size = 0;
public void push(Object o)
{
stack[++size] = o;
}
public Object pop()
{
return stack[--size];
}
}
If you push three objects and then pop two of them, the stack still
references all three, and will continue to do so for an indefinite
period of time. The solution is to replace pop()
The solution is a really simple stack. Also gets rid of that MAX_SIZE wart:
public class SimpleStack<T> {
private final class Entry {
public T item = null;
public Entry next = null;
}
private Entry top = null;
public void push (T item) {
Entry novus = new Entry();
novus.item = item;
novus.next = top;
top = novus;
}
public T pop () {
if (top == null) throw new NoSuchElementException();
Entry popped = top;
top = top.next;
return popped.item;
}
}
Only slightly longer code, no array, no MAX_SIZE, and no packratting:
pop leaves the former top Entry object unreachable, and therefore the
item in it is no longer reachable through the stack object. If the
caller of pop discards the reference (when done using it) and no other
references to the item linger, both the Entry object and the item become
eligible for garbage collection.
Speed efficiency: assuming decent optimizations, push does a pointer
bump and a couple of assignments to an object header for "new Entry()"
(assuming a decent JVM and a non-full TLAB), and three more pointer
assignments, some stack pushes (for item and novus), and some stack
pops. The other implementation used one push and one pop (o), an integer
addition, an integer comparison and conditional branch (for the bounds
check), a pointer addition and a pointer dereference (indexing into the
array) and a pointer assignment (assignment of o to dereferenced array
cell).
Probably about comparable.
Pop does a pointer comparison, conditional branch, two pointer
assignments, and one push and pop (assuming the optimizer eliminates
"popped" and its output just pushes the return value, does the top =
top.next assignment, then executes RET). The other implementation uses
one push and pop (return value), an integer subtraction, an integer
comparison and conditional branch (bounds check), a pointer addition and
a pointer dereference (array cell), and a pointer assignment (return
value extraction). Avoiding packratting means adding one more pointer
assignment (stack[size] = null; assumes the optimizer gets rid of the
temporary holding the return value and its output just pushes the return
value, sets stack[size] = null, and executes RET).
Again, probably about comparable.
Space efficiency: The other implementation chews up MAX_SIZE + 1 object
references worth of memory at all times, plus two object headers (stack
and array); mine, 2*(actual size of stack) + 1 object references and
(actual size of stack) + 1 object headers. Mine's better for stacks that
need to be able to get large but spend most of their time small; yours
is better for stacks of known bounded size that tend to stay close to
full (depth-first traversals of balanced trees of known max depth, say).
(The above assumes sensible JITting of the methods, without inlining
which would eliminate some of the pushes and pops. It also does not
consider the items stored in the stack to contribute to the space
complexity of the algorithms, only the stack's infrastructure.)
