19 August 2009

Java is fast, they say on ##java

Which class from the Java runtime environment you should use when you need a stack.

The package java.util contains a few classes suitable for pushing, poping, and peeking in stack style.

pushpoppeek
Stack s.push(e) s.pop() s.peek()
ArrayList s.add(e) s.remove(s.size()-1) s.get(s.size()-1)
LinkedList s.addFirst(e) s.removeFirst() s.peekFirst()
ArrayDeque s.addFirst(e) s.removeFirst() s.peekFirst()

All but ArrayDeque implement the widely used and known interface List.

Let's see how efficient are the implementations in JRE6, in relative units.

timespace
Stackx2.09x1.6
ArrayListx1.15x1.3
ArrayDeque11

Yep, ArrayDeque is best both in terms of time and speed. If you need a subtype of List then go with ArrayList. If you want to eat memory like crazy for no good reason then try LinkedList. And if you have a thing for names like Vector (which Stack extends) then, well, go for it. Just don't say I told you to use it. Finally, if you are a speed junkie and you know in advance the maximum possible size of the stack, then you can implement your own for a x1.2 speed-up (compared to ArrayDeque).

Just for the record, a basic stack operation for ArrayDeque takes about 15ns on my old laptop.

Good bye, and stay tuned for the next useless microbenchmark results.

Jim said...

If "having a thing for names" the same thing as needing something to be synchronized, then I have a "thing for names" when I am writing concurrent applications. Also, ArrayDeque is only available in Java6.

Andrew Shultz said...
This comment has been removed by the author.
Andrew Shultz said...

I often find that I want to synchronize at a higher level than the individual data structure, so whether its synchronized or not isn't very important. This is a interesting result assuming you need a really big and frequently used stack. If you're only using it moderately you can't beat the clarity of calling a Stack a Stack.

rgrig said...

@Andrew: The size of the stack doesn't really matter. If you use it a lot or not matters, of course.

@Jim: Like Andrew, I also prefer higher level synchronization usually.
There are other differences between the classes above, but I wanted to focus only on raw performance, because otherwise I would have went on for a few pages :p. Thanks for sharing what you see as being important.