I was assuming LinkedList.Clear() was O(1) on a project I'm working on, as I used a LinkedList to drain a BlockingQueue in my consumer that needs high throughput, clearing and reusing the LinkedList afterwards.
Turns out that assumption was wrong, as the (OpenJDK) code does this:
Entry<E> e = header.next;
while (e != header) {
Entry<E> next = e.next;
e.next = e.previous = null;
e.element = null;
e = next;
}
This was a bit surprising, are there any good reason LinkedList.Clear couldn't simply "forget" its header.next and header.previous member ?
The source code in the version I'm looking at (build 1.7.0-ea-b84) in Eclipse have this comment above them:
ReplyDelete// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
That makes it reasonably clear why they're doing it, although I agree it's slightly alarming that it turns an O(1) operation into O(n).
while I'm not very impressed with the reason of GC optimization - it clearly backfires in your case -
ReplyDeleteclearing and reusing the LinkedList
that does not sound right. why not just create a brand new LinkedList object?
Since I can't seem to be able to comment on answers (?): The pointers between next and previous doesn't matter. Since none of the internal entries will be accessible from any GC root, the whole structure will be collected. Had java used a refcounting collector, we'd be stuck with the cycle problem.
ReplyDeleteThe correct answers is what John Skeet notes.