What is the absolute fastest way to implement a concurrent queue with ONLY one consumer and one producer? - 【StackMirror】|java|multithreading|optimization|concurrency|real-time

java.util.concurrent.ConcurrentLinkedQueue comes to mind, but is it really optimum for this two-thread scenario? I am looking for the minimum latency possible on both sides (producer and consumer). If the queue is empty you can immediately return null AND if the queue is full you can immediately discard the entry you are offering.

Does ConcurrentLinkedQueue use super fast and light locks (AtomicBoolean) ? Has anyone benchmarked ConcurrentLinkedQueue or knows about the ultimate fastest way of doing that?

Additional Details: I imagine the queue should be a fair one, meaning the consumer should not make the consumer wait any longer than it needs (by front-running it) and vice-versa.

2012-04-04 22:21
by JohnPristine

This really seems like premature optimization @John. Are you sure you want to roll your own? Has a profiler showed you that this is a performance issue - Gray 2012-04-04 22:22

If latency (not throughput) is your concern, then beware garbage collection issues. Also, you might want to take a look at lock-free alternatives - DNA 2012-04-04 22:24

I remember some high performance ring buffer implementation, which was quite interesting, but didn't have the same interface as the java collection hence made changes to the code necessary. Now if I just remembered the name. Edit: Just rememberd it DisruptorVoo 2012-04-04 22:28

@Gray If latency is important it's not premature optimization because changing it later on, means some rather large rearchitecturing.. you can't just switch one implementation with another and be done - Voo 2012-04-04 22:48

@Voo Very hard for people to understand that, even when the question has a "real-time" tag. I am totally against useless optimization however for a real-time system (yeah, they exist!) there is no escape and latency kills - JohnPristine 2012-04-04 22:52

The Disruptor: http://code.google.com/p/disruptor - dty 2012-04-04 22:29

For the lowest latency in Java that I am aware of, you could use the Disruptor pattern developed by LMAX.

Basically, they are reducing all latency, which means a lot of rather unique solutions to well established problems. For example, they preallocate as much as possible and reuse the objects (to prevent garbage collection from adding additional latency).

Their solution is based upon memory barriers, which prevent out-of-order execution of code form crossing certain checkpoints. By doing this, they can ensure proper synchronization between one producer thread and a number of consumer threads.

Here is a whitepaper describing the problem and LMAX's solution, and a recent youtube video explaining the rationale and design details of the solution. It would require a lot of code restructuring to use, but it's currently the fastest, lowest latency, thing in town.

2012-04-04 22:31
by Edwin Buck