What does "less predictable performance of LinkedBlockingQueue in concurrent applications" mean?

Question

For the logging feature I am working on, I need to have a processing thread which will sit waiting for jobs and execute them in batches when the count reaches or exceeds certain number. Since it is a standard case of producer consumer problem, I intend to use BlockingQueues. I have a number of producers adding entries to the queue using add() method, whereas there is only one consumer thread that uses take() to wait on the queue.

LinkedBlockingQueue seems to be a good option since it does not have any size restriction on it, however I am confused reading this from the documentation.

Linked queues typically have higher throughput than array-based queues but less predictable performance in most concurrent applications.

It was not clearly explained what they mean by this statement. Can some one please throw light on it? Does it mean LinkedBlockingQueue is not thread safe? Did any of you encounter any issues using LinkedBlockingQueue.

Since the number of producers are lot more, there is always a scenario I can run into where the queue is overwhelmed with large number of entries to be added. If I were to use ArrayBlockingQueue instead, which takes size of the queue as parameter in the constructor, I could always run into capacity full related exceptions. In order to avoid this, I am not sure how to determine what size I should instantiate my ArrayBlockingQueue with. Did you have to solve a similar problem using ArrayBlockingQueue?

Holystone

Answer 1

Does it mean LinkedBlockingQueue is not thread safe?

It certainly does not mean that. The phrase "less predictable performance" is talking about just that -- performance -- and not some violation of the thread-safety or Java collections contract.

I suspect this is more around the fact that it is a linked-list so iterating and other operations on the collection will be slower so the class will hold locks longer. It also has to deal with more memory structures since each element has it's one linked-list node as opposed to just an entry in an array. This means that it has to flush more dirty memory pages between processors when synchronizing. Again, this impacts performance.

What they are trying to say is that if you can, you should use the ArrayBlockingQueue but otherwise I wouldn't worry about it.

Did any of you encounter any issues using LinkedBlockingQueue.

I've used it a lot and not seen any problems. It also is used a lot in the ExecutorService classes which are used everywhere.

Arteriole

Thanks Gray for the detailed answer on what "less predictable performance" means. It gives me confidence to use LinkedBlockingQueue since you mentioned they are used everywhere. – Holystone

Led me to this answer while researching on the same question. Thanks for the answer, but if the performance is less predictable, how come these queues typically have better throughput than array based queues? Intuitively it would seem otherwise. – Reticular

Interesting @shrini. What evidence of this have you seen? – Arteriole

I was referring to 'higher throughput' part of the following statement: "Linked queues typically have higher throughput than array-based queues but less predictable performance in most concurrent applications." – Reticular

This gives a possible explanation: codeidol.com/java/javagenerics/Queues/… – Reticular

Right. And what that chart does not show is other operations such as iterator and toArray(). Also, this may not be a big-O issue but rather a factor issue. LinkedBlockingQueue might be 2x slower in general because of the memory overhead or something @shrini. – Arteriole

@Reticular As for higher throughput, one reason might be that "it uses separate locks for the head and the tail" as suggested in #35968292. – Fritter