Sunday, May 9, 2010

LinkedArrayQueue

Not long time ago I needed an implementation of a really fast (constant speed) and small (with as small memory footprint as posible) queue for storing multiple objects (thread safety was not required). For me there were two usable options where each of them fullfilled only one of these two requirements. ArrayList with its size and LinkedList with its speed.

ArrayList was good (from the memory point of view) because it used array as a mean of element storage. Its disadvantage however was that it was not a queue, so the removal of its first element always moves all elements (with the first one excluded) to a lower index. And as the speed of such operation is O(n) this was not acceptable for cases where you had too many elements (my case).


remove firstinsert last
ArrayListO(n)O(1) or O(n) when resizing
LinkedListO(1)O(1)

The disadvantage of LinkedList (besides its slower insert) was that it wrapped each inserted element into a new wrapper and thus increased the memory usage.

As i needed something better I decided to implement my own queue. And so LinkedArrayQueue was born.

The design was quite simple: to reuse the principle of LinkedList (as this was more closely copying my expectations) and "fix" its memory issues. So instead of creating a wrapper for each new element I was wrapping an array that was suposed to hold the queue elements. When the array was fully written a new wrapper with array was created = O(1). When all elements from an array were polled/removed (O(1)) the array with its wrapper was thrown away = O(1). This way we'll get an insert (O(1)) almost as fast as an insert into an array and also m-times less element wrappers as in the LinkedList (where m means the size of the wrapped array). Also the creation of a new array with its wrapper takes a constant amount of time = O(1).

Here is a graphical representation of this concept:



And here are some interesting results I got on my machine (-Xmx64m, java 1.6.0_16):


inserts before OutOfMemory Errorinsert last speed ns/element (of 1 milion inserts) - aprox. averageremove first speed ns/element (of 500 000 elements) - aprox. average
ArrayList7 634 06860 nanoseconds220 092 nanoseconds
LinkedList2 771 293290 nanoseconds22 nanoseconds
LinkedArrayQueue
(with array size 128)
15 202 04835 nanoseconds20 nanoseconds

As you can see with the same provided memory I was able to store more elements (in my case I was storing the same Integer n-times) and much faster that it was possible in LinkedList or ArrayList. Also the poll/remove operation was much faster than in ArrayList and only slightly faster than in LinkedList. And that is what I exactly wanted.

So this is the design of my implementation. But if you know of some better (possibly existing) solution just let me know.

2 comments:

  1. I think your solution may be optimal, as long as you need exactly what you described. But there are much more classes in Java, java.util.ArrayDeque could suit your needs, for the operations you need it's fast, although only in amortized time. This means that a single addLast or removeFirst may take a long time, but on the average the time is small and independent of the size. The advantage of ArrayDeque is the fast random access, which you don't need and which is for whatever reason missing in Java, but present in C++ deque.

    You wrote "[ArrayList's] disadvantage however was that it was not a queue, so the removal of its first element always created a new array into which it copied all elements with the first one excluded.", which is wrong, removal of the first element creates no new array, it "only" moves all the elements.

    ReplyDelete
  2. to maaartin: I have "fixed" the statement regarding the ArrayList object removal. Although the remove first operation only moves all elements to a lower index the speed of such operation is still O(n) which was not acceptable for me. but thank you for your correction and comment

    ReplyDelete