There was an interesting exchange today on the concurrency-interest mailing list about LinkedBlockingQueue, one of the most important and commonly used queue implementations in java.util.concurrent. LBQ is an optionally-bounded thread-safe queue based on a linked list.

The key method in question is the extract() method used to remove the head of the queue:

[source:java]

private E extract() {

Node first = head.next;

head = first;

E x = first.item;

first.item = null;

return x;

}

[/source]

This method is going to release the first item (head) out into the world and head.next will become the new head. The issue here is that head will be pulled off, used, and probably become garbage but the head Node retains its head.next link to the next Node.

This is bad because it means that there will be a chain of references back through all the old Node references even after they’ve been removed from the queue and thrown away. GC will of course take care of all those references since the Nodes are garbage.

But the garbage collectors we use are generational – they periodically sweep through young objects and kill the vast numbers of them that have been short-lived. The ones that survive live to the next generation and eventually if objects are old enough they move to the old generation where they are collected less frequently by a full GC.

The problem in the queue nodes is that if they live in the queue long enough (if the queue is big), then one of them will enter the old gen and at that point the reference from old gen into young gen prevents the whole chain of dead nodes from being reclaimed by young generational collection. This is highly inefficient for the GC.

This problem can of course be solved simply by nulling the Node next reference:

[source:java]

private E extract() {

Node first = head.next;

head.next = null; // Kill this reference

head = first;

E x = first.item;

first.item = null;

return x;

}

[/source]

This breaks the chain and prevents the reference from old gen into young gen. This makes a huge difference in GC and performance. You can see some results from a test demonstrating the problems:

Test 1 took: 1595ms
Test 2 took: 2639ms
Exception in thread "main" java.lang.AssertionError: Full GC has
occured during the test: 47 times
	at TestLBQ.main(TestLBQ.java:72)

My workaround of null'ing head.next before moving the head works
perfectly and displays (as expected):
Test 1 took: 1629ms
Test 2 took: 1592ms

On the original version (the one in the JDK), the second pass through the test is significantly slower and full gc occurred 47 times as opposed to the fixed version which shows a faster second pass and no full gc.

Even worse was a test with the new G1 garbage collector in Java 7. This new collector takes the generational idea and pushes it even further. Unfortunately, that means it’s even more affected by this problem (while in general it is better for many apps):

JDK7 version:
Test 1 took: 5456ms
Test 2 took: 5575ms

With null assignment:
Test 1 took: 1698ms
Test 2 took: 1602ms

It seems this was not the first discovery of this issue as a couple of people were already using modified LBQs with this change. Hopefully this issue will be fixed in Java 7 at least.