I've been wondering why there is ConcurrentLinkedQueue in Java 5+, but not something like a ConcurrentLinkedBlockingQueue, which would allow the client to block on an empty queue via a "take" method, or block on an empty queue for a limited time via a "poll" method.

I attempted to construct one by combining the use of a Semaphore with a ConcurrentLinkedQueue, but apparently it is less scalable than the LinkedBlockingQueue.

As pointed out by Doug Lea:

"This IS a good thought....This way works, but reduces concurrency by using a single semaphore, so is a bit less scalable than current inkedBlockingQueue. However, there is a path to much better scalability by using the "dual-queue" approach similar to what we did for Java 6 SynchronousQueue. My initial intent was to find a way to internally use such techniques to replace the unbounded case of LinkedBlockingQueue. But this turns out not to work out too well because of all the little compatibility problems encountered -- for example, maintaining the same Serialization form. So it is more likely that we'll put out a separate ConcurrentLinkedBlockingQueue that will be preferable to LinkedBlockingQueue unless you need capacity constraints.
Stay tuned for it..."

In stead of waiting, I decided to try a different path and proceeded to make a second attempt. This time the constructs I use included:
* an extra ConcurrentLinkedQueue for the parking threads
* volatile for marking if a thread is potentially parked or not
* LockSupport.[un]park[Nano](...)

One feature of such ConcurrentLinkedBlockingQueue is that it is unbounded, whereas even LinkedBlockingQueue has a max capacity of Integer.MAX_VALUE.

The source can be found here, whereas some performance tests can be found here. Some initial load testing looks promising, although I only tested it with a single procesor machine, and it appears the test result is very sensitive to the GC and heap memory configuration for the JVM. What I really need is some loading testing on a multi-processor environment where true concurrency is possible.
Update on 11Sep2006: Running the test harness on an AMD Opteron dual processor using JDK-1.5.0_05, the CLBQ is on average 72% faster than the LBQ. See here for more details.

---

Update on 19Sep2006:

More experiments seem to indicate that the CLBQ consistently outperform the LBQ for the mix of N-producer 1-consumer. When there are N-producer and M-consumer, however, it seems the reverse is true. Not exactly sure why. Probably CLBQ incurs a slightly higher overhead as compared to LBQ in the M-consumer situation.

---

Update on 4Apr2007:

If anyone has a powerful box (with multi-processors) and is interested in comparing the performance of ConcurrentLinkedBlockingQueue vs LinkedBlockingQueue, please download a jar from:

http://beanlib.sourceforge.net/clbq/070407/q-test.jar

and run it with either jdk5 or jdk6:

java -DnumConsumer=10 -DnumProducer=100 -DwcRatio=20 -server -XX:CompileThreshold=1500 -XX:+UseConcMarkSweepGC -XX:+CMSIncrementalMode -XX:+DisableExplicitGC -jar q-test.jar

Note:

• the number of concurrent producers can be specified via the system property "numProducer", which defaults to 10
• multiple concurrent consumers is now supported via the system property "numConsumer", which defaults to 1
• the W/C ratio (ie wait-time to compute-time) can be specified via the system property "wcRatio", which defaults to zero

For instance, the above example means to run the test with 100 producers, 10 consumers, and a W/C ratio of 20. One interesting observation is that Windows XP Professional is really slow on LBQ even when there is only 1 producer and 1 consumer! Feel free to tinkle with the parameters, and let me know what you find.

The source jar of the test harness can be downloaded from:

http://beanlib.sourceforge.net/clbq/070407/q-test-sources.jar