A fast queue in Java

Question

I am looking for a fast queue implementation in Java. I see that LinkedList implements the Queue interface, but it will only be as fast as a LinkedList right? Is there a way to have a queue that will be faster especially for add (I only need poll, add and check for empty). Down the line I may also need a PriorityQueue but not yet.

Solution 1

I see that LinkedList implements the Queue interface, but it will only be as fast as a LinkedList right?

Eyeballing the source code, LinkedList is O(1) for Queue.add, Queue.poll, and Queue.peek operations.

I hope that's fast enough.

Solution 2

If multiple threads are going to be accessing the queue then consider using an ArrayBlockingQueue. Otherwise take a look at ArrayDeque. From the ArrayDeque API:

This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

Specifically an array-based queue implementation reduces the need to resize the underlying array if the existing array has sufficient capacity, thus making additions to the queue generally faster than LinkedList. Be aware that ArrayBlockingQueue is a bounded implementation whereas ArrayDeque will resize as required.

The flip-side is that LinkedList will typically provide a much more compact representation, particularly in cases where your queue grows and shrinks by a large amount. For example, if you added 10,000,000 elements to an ArrayDeque and then removed 9,999,999 elements, the underlying array would still be of length 10,000,000 whereas a LinkedList would not suffer from this problem.

In reality, for single-threaded access to a non-blocking queue I tend to favour LinkedList. I imagine the performance differences are so negligable you wouldn't notice the difference anyway.

Solution 3

If performance of a linked list was really a problem, an alternative would be to implement a "circular queue" in an array, i.e. a queue where the start and end point move as entries are added and deleted. I can give more details if you care. When I was using languages that did not have a library of collections, this was how I always implemented queues because it was easier to write than a linked list and it was faster. But with built-in collections, the effort of writing and debugging my own collection for a special case is not worth the trouble 99% of the time: When it's already written, the fact that I could write it a different way faster than I could re-write it the way Java does is pretty much an irrelevant fact. And any performance gain is likely to be too small to be worth the trouble. I sub-type existing collections to get special behavior I need now and then, but I'm hard-pressed to think of the last time that I wrote one from scratch.

Solution 4

You may want to have a look at http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list which introduces GapList. This new list implementation combines the strengths of both ArrayList and LinkedList.

It therefore implements the Deque interface, but can also be presized like the above mentioned ArrayDeque. In addition, you also get all the possibilities of the List interface for free.

Solution 5

Start with really simplistic rotating Queue implementation with "C/C++ like" attitude and fixed size.

class SimpleQueue<E>
{

int index   = 0;
int head    = 0;
int size    = 100;
int counter = 0;
E[] data    ;


@SuppressWarnings("unchecked")
SimpleQueue()
{
    data = (E[]) new Object[size];
}

public void add(E e)
{
    data[index]=e;
    index=(index+1)%size;
    counter++;
}

public E poll()
{
    E value = data[head];
    head=(head+1)%size;
    counter--;
    return value;
}

public boolean empty()
{ return counter==0; }

//Test
public static void main(String[] args)
{
    SimpleQueue<Integer> s = new SimpleQueue<Integer>();

    System.out.println(s.empty());

    for(int i=0; i< 10; i++)
        s.add(i);

    System.out.println(s.empty());

    for(int i=0; i<10; i++)
        System.out.print(s.poll()+",");

    System.out.println("\n"+s.empty());

}
}

And then improve it.

View more solutions

Comments

[Sam Holder]

have you verified that the LinkedList will not be fast enough? Add should be fast in a linked list...

[FrustratedWithFormsDesigner]

LinkedList s aren't fast enough? Have you tried writing your own to get around LinkedList's bottelnecks (whatever they may be)?

[Eqbal]

I was thinking LinkedList add would be O(n) for some reason.

[Noel Ang]

That would be an exceedingly stupid accomplishment for a linked-list data structure.

[Graphics Noob]

Linked lists are generally O(n) for searching, but if you're actually using it as a queue it won't ever come up.

[Jay]

@Eqbal: That would be true if it was implemented as a singly-linked list. But it's a doubly-linked list, so you can jump to the end quickly.

[Merlyn Morgan-Graham]

Upvoting because this is a good alternative to the selected answer if the queue speed is profiled to be a performance bottleneck.

[jezg1993]

LinkedBlockingQueue is actually faster then the ArrayBlockingQueue. So if you were using a concurrent queue that is blocking use that one. Else using ConcurrentLinkedQueue is faster then both those two.

[Noel Ang]

Nothing prevents even a singly-linked list implementation from being able to jump to the end quickly. That's an implementation detail.

[Pacerier]

O(1) doesn't automatically mean it's fast. A linked list can be O(1) but still horrendously slow when compared to other O(1) methods.

[Pacerier]

@JohnVint, do you have some sources that ArrayBlockingQueue is slower than LinkedBlockingQueue? Shouldn't ArrayBlockingQueue be the faster one since since the backing array never resizes during the entire lifetime of the object?

[Pacerier]

@Adamski, doesn't the ArrayDeque automatically shrink it's size at the point of removal when current_element_amt < 0.5 * capacity?

[jezg1993]

@Pacerier I would have to look it up later but it is in the book Java Concurrency In Practice. It states that because it allows two parallel actions on the queue it can perform better.

[arviman]

+1 to Pacerier. Benchmarked a Queue with insertion and removal of 35 million entries and ArrayDeque is about 25% faster than LinkedList.

[arviman]

This should be the accepted answer. I did a benchmark for an algorithm and found that ArrayDeque is faster than LinkedList by about 25% when I made around 35 million adds and removals.

[Étienne Miret]

What you describe has been added in Java 6 and is called java.util.ArrayDeque.

[Jay]

@NoelAng Well, yes, one could always add a separate "end of list" pointer to get to the end quickly, or something of the sort. But I think in normal discussions, if someone says, "data structure X give O(n) performance on this operation", one could ALWAYS say, "No, that's not true, because the specific implementation might provide a special case to handle that." Pretty much by definition, a specific implementation could break normal performance rules by providing a shortcut for some special case.

[ThePyroEagle]

ArrayDeque is a rotating queue. Why reinvent the wheel when it's in the Java SE 6 libraries?