Performance Zone is brought to you in partnership with:

I'm a software architect with Lockheed Martin Mission Systems and Training. Most of my recent work has been with Java, especially Java EE (JBoss) and OSGi (Karaf), but I've worked with C, C++, C#, Ada, Python, MATLAB, and a few other things over time. Alan is a DZone MVB and is not an employee of DZone and has posted 14 posts at DZone. You can read more from them at their website. View Full User Profile

Performance of Java Collections

10.03.2013
| 6237 views |
  • submit to reddit

What is the real-world effect of choosing the wrong kind of collection?

I’m in the midst of teaching an Introduction to Java class. Like most courses of this type, when I introduce the standard JVM collections I intend to provide guidance on which type of collection to use when.

I wanted to show the real-world effects of making the correct or incorrect decision, so I put together an example. I used the excellent Caliper library to create a class that benchmarks pulling data from existing collections. Caliper is nice for this kind of thing because it does the measurement for you, and automatically handles some things like garbage collection coming in and messing up your test. It also publishes the results to a webapp, with a useful table that I’ll be able to use in my slides. Caliper is undergoing a change to its API at the moment, so I used the old API since that’s the version that’s available in Maven. Both APIs look a lot like JUnit; the old API looks like JUnit 3 and the new API looks like JUnit 4.

The benchmark code is part of my small but growing GitHub repository associated with my Introduction to Java class. The benchmark methods look like this:

    public String timeArrayListIteration(int reps) {
        String name = null;
        for (int i = 0; i < reps; i++) {
            for (Person p: personArrayList) {
                name = p.getLastName();
            }
        }
        return name;
    }

The time at the front of the method name works like JUnit 3’s test — it marks the method as something that Caliper should benchmark. Caliper handles choosing a sensible value for reps in order to provide consistent and meaningful output. The method returns a “meaningful” value so that the compiler won’t be able to optimize it away.

Of course, there are a lot of benchmarks out there already, but most of them focus on comparing the performance of different collections libraries, or of similar collection types that should have the same Big-O performance. What I was after is showing the dramatic difference of using the wrong collection type entirely (e.g. a list instead of a map).

Is this realistic? It is in my experience. I’ve found and fixed many cases where a list collection was being used even when most users of the collection were doing searches for a specific element. It seems that “data store” classes are susceptible to this kind of thing, especially when they start out with simple append and iteration operations and then progress to include more complex functions.

From my simple test, the qualitative ordering of performance is what everyone would expect. It’s painful to iterate over a map’s values. It’s very painful to search a list. What might be at least a little surprising is the size of the difference.

Benchmark Results

Iteration over a hash map took 3 times as long as over an array list, and 1.5x a linked list. Searching over an array list took 13 times as long as pulling an item out of a hash map when there was an index handy to help.

Note that because I choose to search for a random element, there’s a lot of variance in the searches that have to iterate over the collection. So the displayed number is the average performance under uniform access assumptions.

One other interesting point is the relative performance of array lists versus linked lists when fetching a specific element with a known location. Most people suggest linked lists as the number of elements grows large, and that’s good advice where there will be inserts and deletes that are not at the end. But if the primary use case will be adding things, fetching them, and iterating over them, a large array list may still be noticeably better.

My intent with this code was to scare my students into using the right collection, so I didn’t spend time on other things I think would be interesting, like measuring how expensive it is to maintain an extra index on a hash map in order to avoid a search. These numbers seem to indicate that it would be worthwhile to spend 10 times the cost of a single search on index updates. Since updating hash map indices is O(1), that suggests it’s almost always worth it. It would be interesting to try to verify that.

Published at DZone with permission of Alan Hohn, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Thomas Mauch replied on Mon, 2013/10/07 - 4:38am

You talk in your article about the differences between ArrayList and LinkedList and when to use them. Let me add my two cents...

I think It's hard to find a good use case for LinkedList as it uses a lot of memory and performs really poor in accessing a random element. Unfortunately also ArrayList has its performance problems if elements at the beginning or in the middle of the list must be removed or inserted.

There is however a new list implementation called GapList which combines the strengths of both ArrayList and LinkedList. GapList's implementation guarantees efficient random access to elements by index (as ArrayList does) and at the same time efficient adding and removing elements to and from head and tail of the list (as LinkedList does).

You find more information about GapList and also some performance figures in this article.

Alan Hohn replied on Mon, 2013/10/07 - 8:26am in response to: Thomas Mauch

Thanks! I wrote about the standard collections because I figured people who are out looking for collections libraries already know when the standard collections are slow :-)

GapList seems like a really cool approach and I'm happy to have heard about it.


Samir Hasan replied on Mon, 2014/08/04 - 12:31am

I saw your benchmark code for comparing the search performance for both LinkedList and ArrayList. You have searched for a random index in each of the data structures, but did so with possibly different indices, if I understand it correctly. How do you justify the generality of your results? Thanks.


Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.