Why the ArrayBlockingQueue is called a bounded queue while a LinkedBlockingQueue is called an unbounded blocking queue?

Question

As far as I know both the linked list and array can grow without bounds or am I wrong ? But when I have gone through the documentation in the Executor Service I see this :

Unbounded queues. Using an unbounded queue (for example a LinkedBlockingQueue without a predefined capacity) will cause new tasks to wait in the queue when all corePoolSize threads are busy. Thus, no more than corePoolSize threads will ever be created. (And the value of the maximumPoolSize therefore doesn't have any effect.)

So does the Unbounded Queue property changes when the LinkedBlockingQueue has a defined capacity ?

And this written for ArrayBlockingQueue:

Bounded queues. A bounded queue (for example, an ArrayBlockingQueue) helps prevent resource exhaustion when used with finite maximumPoolSizes, but can be more difficult to tune and control. Queue sizes and maximum pool sizes may be traded off for each other: Using large queues and small pools minimizes CPU usage, OS resources, and context-switching overhead, but can lead to artificially low throughput. If tasks frequently block (for example if they are I/O bound), a system may be able to schedule time for more threads than you otherwise allow. Use of small queues generally requires larger pool sizes, which keeps CPUs busier but may encounter unacceptable scheduling overhead, which also decreases throughput.

Andrzej Doyle · Accepted Answer · 2012-08-06 14:51:39Z

13

Why do you think that an ArrayBlockingQueue can grow without bounds? From its own documentation:

This is a classic "bounded buffer", in which a fixed-sized array holds elements inserted by producers and extracted by consumers. Once created, the capacity cannot be increased. Attempts to put an element into a full queue will result in the operation blocking; attempts to take an element from an empty queue will similarly block.

In other words, once it gets full, it's full - it doesn't grow.

Are you getting confused with an ArrayList by any chance - which is also backed by an array, but which expands this as required?

So does the Unbounded Queue property changes when the LinkedBlockingQueue has a defined capacity ?

Yes, hence why it's described as "optionally-bounded" in its Javadocs. Furthermore, the docs state that (emphasis mine):

The optional capacity bound constructor argument serves as a way to prevent excessive queue expansion. The capacity, if unspecified, is equal to Integer.MAX_VALUE. Linked nodes are dynamically created upon each insertion unless this would bring the queue above capacity.

answered Aug 6, 2012 at 14:51

Andrzej Doyle

104k33 gold badges191 silver badges231 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Geek Over a year ago

@Andrej Yes I am confusing ArrayList for Array . thanks for clarification. BTW how does the ArrayList grow when it is backed by an underlying array that can not grow ?

Louis Wasserman Over a year ago

When it needs to resize, ArrayList allocates a new, larger array and copies all the elements to that new array.

teik · Accepted Answer · 2019-08-16 10:00:58Z

3

The javadoc for LinkedBlockingQueue says:

An optionally-bounded blocking queue based on linked nodes.[...]

The optional capacity bound constructor argument serves as a way to prevent excessive queue expansion. The capacity, if unspecified, is equal to Integer.MAX_VALUE.

The javadoc of ArrayBlockingQueue says:

A bounded blocking queue backed by an array.[...]

This is a classic "bounded buffer", in which a fixed-sized array holds elements inserted by producers and extracted by consumers. Once created, the capacity cannot be increased

So, a LinkedBlockingQueue can be bounded or unbounded, whereas an ArrayBlockingQueue is always bounded.

edited Aug 16, 2019 at 10:00

teik

5185 silver badges27 bronze badges

answered Aug 6, 2012 at 14:55

JB Nizet

694k94 gold badges1.3k silver badges1.3k bronze badges

Comments

Peter Lawrey · Accepted Answer · 2012-08-06 14:52:50Z

2

As far as I know both the linked list and array can grow without bounds or am I wrong

A linked list as an unlimited size. An array has fixed size. An ArrayList wraps an array and replaces it when it needs a bigger one.

So does the Unbounded Queue property changes when the LinkedBlockingQueue has a defined capacity

When LinkedBlockingQueue has a maximum capacity, it is bounded but it not used this way by default.

answered Aug 6, 2012 at 14:52

Peter Lawrey

535k83 gold badges770 silver badges1.2k bronze badges

1 Comment

Peter Lawrey Over a year ago

"An ArrayList wraps an array replaces it when it needs a bigger one." You can see this in the ensureCapacity method for ArrayList.

John B · Accepted Answer · 2012-08-06 14:55:00Z

From the documentataion for ArrayBlockingQueue

A bounded blocking queue backed by an array. This queue orders elements FIFO (first-in-first-out). The head of the queue is that element that has been on the queue the longest time. The tail of the queue is that element that has been on the queue the shortest time. New elements are inserted at the tail of the queue, and the queue retrieval operations obtain elements at the head of the queue.

If you notice all the constructors of ArrayBlockingQueue take a capacity because this class was designed to be bounded. This choice was made because if you want a concurrent queue, you probably don't want the overhead that comes with resizing an ArrayList. Hence, if you want an unbounded queue LinkedBlockingQueue is a better option since it does not involve this overhead.

wannibar · Accepted Answer · 2018-02-03 07:13:40Z

other answer is very right! I provide another way to explain. well, I also get confused by the term "unbound and bound" passed. you can look at the source code blew.

    /** The queued items */
final Object[] items;

/** items index for next take, poll, peek or remove */
int takeIndex;

/** items index for next put, offer, or add */
int putIndex;

/** Number of elements in the queue */
int count;

from the source code, we can see the array is final, so we can not resize the array. if use LinkedBlockingQueue, we can always add more elements...and in the source code, the next reference is not final. NOTE, in theory, LinkedBlockingQueue is not unbounded. because it can only store MAX_INTEGER minus 8 elements. from javadoc, the unbounded queue is PriorityBlockingQueue. but the PriorityBlockingQueue also can only store MAX_INTEGER -8 elements. so i think there is no perfect unbounded queue...

Collectives™ on Stack Overflow

Why the ArrayBlockingQueue is called a bounded queue while a LinkedBlockingQueue is called an unbounded blocking queue?

5 Answers 5

2 Comments

Comments

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

2 Comments

Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related