Java: ArrayBlockingQueue vs. LinkedBlockingQueue

Question

I think that, in most cases, the ArrayBlockingQueue will perform better than the LinkedBlockingQueue. However, that is the case when there is always enough room in the array... If it gets full, it's not very predictable whether it will perform so well, since it will block the thread that's trying to push data into the queue...

So, my question is: Is there any middle-ground implementation of BlockingQueue? Say, an ArrayListBlockingQueue or a BucketListBlockingQueue? Something like a list of arrays, so that the queue can increase in capacity dynamically, while still having a reasonable benefit from using array to ultimately store data?

A list of arrays would not give a performance improvement... Why would it? And besides: why are you worried about performance? Did you actually have problems? Did you profile? — Dariusz, Jun 12 '13 at 09:22
I'm thinking about memory locality. If you use a linked list whose elements jump around random memory addresses you're much more likely to have cache misses and problems like that. Plus, to fetch from memory, you have to fetch the address of the next element, and then fetch the content of such address... Whereas, with an array, you'd just do address++ to get the address of the next element. With a list of arrays, you'd have some compromise between the two implementations... Do you think otherwise? — Eduardo Bezerra, Jun 12 '13 at 09:27
I think that a list of arrays gives you advantages from neither of the original collections. You still have to allocate memory and, depending on the size of the arrays, it will get more or less fragmented. I think that if you make your Array-based collection resizing algorithm right, you will have few resizes and very fast iteration. As for memory locality - collections store references to objects and those objects themselves may be located anywhere in the memory, so you may will get no gain in that regard from using one collection or other. — Dariusz, Jun 12 '13 at 09:36

score 14 · Answer 1 · edited Oct 24 '20 at 09:48

1 . LinkedBlockingQueue ( LinkedList Implementation but not exactly JDK Implementation of LinkedList. It uses static inner class Node to maintain Links between elements )

Constructor for LinkedBlockingQueue
public LinkedBlockingQueue(int capacity) 
{
        if (capacity < = 0) throw new IllegalArgumentException();
        this.capacity = capacity;
        last = head = new Node< E >(null);   // Maintains a underlying linkedlist. ( Use when size is not known )
}

Node class used to maintain Links

static class Node<E> {
    E item;
    Node<E> next;
    Node(E x) { item = x; }
}

2 . ArrayBlockingQueue ( Array Implementation )

Constructor for ArrayBlockingQueue

public ArrayBlockingQueue(int capacity, boolean fair) 
{
            if (capacity < = 0)
                throw new IllegalArgumentException();
            this.items = new Object[capacity]; // Maintains a underlying array
            lock = new ReentrantLock(fair);
            notEmpty = lock.newCondition();
            notFull =  lock.newCondition();
}

Biggest difference between ArrayBlockingQueue and LinkedBlockingQueue is clear from constructor, one has an underlying data structure of Array and the other of LinkedList.

ArrayBlockingQueue uses single-lock double condition algorithm and LinkedBlockingQueue is a variant of the "two lock queue" algorithm and it has 2 locks 2 conditions ( takeLock , putLock)

Till now I gave comparison between these 2 implementations Coming back to original question , Similar question was asked in concurrency mailing list in this doug Lea talks about DynamicArrayBlockingQueue which is implementation provided by Dawid Kurzyniec.

I see one downvote here If you are not agree with the answer please provide comments also so that I can improve or correct if something is wrong. — Vipin, Dec 12 '13 at 16:14
to be more clear `ArrayBlockingQueue` uses `Circular Array` as underlying structure +1 for answer — Mike Herasimov, Dec 12 '15 at 13:49

score 8 · Answer 2 · answered Jul 04 '13 at 04:36

My 2 cents:

To start with, the bottom line here is you don't really care about the difference here because even when you are using a plain LinkedBlockingQueue, the performance is good enough when you are delivering some micro-second level systems. So the performance difference here isn't really that great.

If you are writing a mission-critical high performance system and you are using queues to pass messages between threads, you can always estimate the queue size needed by [Queue Size] = [Max acceptable delay] * [Max message rate]. Anything which can grow beyond such capacity means you suffer from a slow consumer problem. In a mission critical application, such delay means your system is malfunctioning. Some manual process might be needed to make sure the system is running properly.

In case your system isn't mission critical, you can simply pause (block) the publisher until some consumers are available.

Java: ArrayBlockingQueue vs. LinkedBlockingQueue

2 Answers2

Linked