Defining a set of ground-rules for high-performance data structures (java)

Question

I generally use vectors/arraylists , hashmaps/treemaps, and other java collections interchangeably, with exception of the fact that there are sometimes functional API requirements (for example, I might need a sorted data set in certain instances).

Lately, however, I've found a need to push java performance to the limit for some algorithms I'm running.

Is there a set of guidelines for high-performance data structures, that I can use as ground rules for my coding ?

I'm looking for general rules, but, in this context, answers to the following questions might also be very helpful :

1) When should I use multidimensional arrays instead of nested Collections ?

2) Vectors vs. ArrayLists - is there truly a performance difference ?

3) Do collection API's like Google's collections, java tricks (like reflection and casting), and other common java developer idioms tend to slow down the JVM when it is under heavy load ?

4) Do primitives vs regular objects (i.e. Double vs double) slow down the JVM when doing lots of calculations ?

5) Are there other important guidelines for dealing with large collections in java programs which need to be high-performance ?

• Note : at this point, I'm not doing any multithreading... I realize that there are other constraints which might apply once I start parallelizing .

Answer 1

All performance issues should be addressed first by profiling (for both time and memory/object use). Don't optimize things that aren't a factor in the performance of your code. With that caveat, there are some general rules of thumb (that should all be tested by profiling!)

1) When should I use multidimensional arrays instead of nested Collections ?

When you don't need the dynamic sizing of Collections and don't need to feed your data to anything that requires a Collection, then multidimensional arrays (arrays of arrays, actually) can be a faster.

2) Vectors vs. ArrayLists - is there truly a performance difference ?

Yes. Many methods in Vector are synchronized, which is expensive. If you aren't multithreading, then avoid Vector. Even if you are, the granularity of the synchronization is usually wrong and you're better off providing thread safety yourself.

3) Do collection API's like Google's collections, java tricks (like reflection and casting), and other common java developer idioms tend to slow down the JVM when it is under heavy load ?

Reflection is slow; garbage collection is slow. Anything you can do to avoid those will speed things up.

4) Do primitives vs regular objects (i.e. Double vs double) slow down the JVM when doing lots of calculations ?

Yes. Autoboxing/unboxing can create huge amounts of garbage very quickly. This all has to be collected, which will also slow down your program.

5) Are there other important guidelines for dealing with large collections in java programs which need to be high-performance ?

Prefer local method variables to field accesses. You can find many other guidelines by searching the web. The main thing, though, is to profile.

Edit: There's a good collection of performance hints here.

Answer 2

To answer your 4) Yes, Double vs double definitely changes the performances

When you have collections made up of primitives you certainly can use collections backed by primitives, like the very good Trove API. By avoiding constant primitive-to-object and vice-versa (un)boxing you save both memory and precious time.

Also the Vector class is, by now, pretty much a thing of the past.

Answer 3

1) If you don't require really dynamic resizing, or you can fit your data inside a small enough "maximum size" container, then you will get better performance on random access from arrays than you do from collections due to the removal of method call overhead and possibly more (depending on the collections used).

2) Vectors and Hashtables should be considered almost as if they are deprecated in my opinion. They are "thread safe", but for most real world scenarios, simply having the data structure itself be thread safe is not sufficient; usually your application logic also has to be a part of this synchronization. ArrayList, HashMap will perform better as they don't have synchronized blocks, which 99.9% of the time don't get you anything useful anyways.

3) Google's collections APIs are great, no real performance issues. Reflection is definitely slow and should not be in inner loops.

4) Ideally you would like to avoid boxing/unboxing of primitives in inner loops. You can find collections that are specifically tuned to primitives (ie. Trove collections http://trove.starlight-systems.com/).

5) It depends on the specific use, I wouldn't say that there are any general guidelines. Just be sure to understand what you are doing when transforming collections, etc. For example, be sure it isn't cloning your entire collection when you transform a list to a set or something like that.

Answer 4

1. I believe the only time you should use Vector is when you need it to be syncronized, but you can used the special Syncronized thingy on ArrayList, so I'd say Vector isn't needed. Always use ArrayList instead of LinkedList. It departs from common sense, so it has to be java's implementation, but ArrayList is tons faster. I used to believe in LinkedList so I created the following test:

   import java.util.ArrayList; import java.util.GregorianCalendar; import java.util.LinkedList; import java.util.List; import java.util.Random;

/** * */

/** * @author thom * */ public class ListTest {

private ArrayList<Integer>      arrayList = new ArrayList<Integer>();
private LinkedList<Integer>     linkedList = new LinkedList<Integer>();

/**
 * 
 */
public void test(){
    LinkedList<Integer> arrayTimes = new LinkedList<Integer>();
    LinkedList<Integer> linkedTimes = new LinkedList<Integer>();

    for(int ix = 0; ix < 100; ix ++){
        arrayList.clear();
        long start = new GregorianCalendar().getTimeInMillis();
        fillList(arrayList);
        long stop = new GregorianCalendar().getTimeInMillis();
        int elapsed = (int) (stop - start);
        arrayTimes.add(elapsed);
    }

    for(int ix = 0; ix < 100; ix ++){
        linkedList.clear();
        long start = new GregorianCalendar().getTimeInMillis();
        fillList(linkedList);
        long stop = new GregorianCalendar().getTimeInMillis();
        int elapsed = (int) (stop - start);
        linkedTimes.add(elapsed);
    }

    double arrayAvg = avg(arrayTimes);
    double linkedAvg = avg(linkedTimes);

    System.err.println("Adding 100,000 entries 100 times to linked list.");
    System.err.println("ArrayList elapsed time (ms.):" + arrayAvg);
    System.err.println("LinkedList elapsed time (ms.):" + linkedAvg);

    arrayTimes.clear();
    linkedTimes.clear();

    long start = new GregorianCalendar().getTimeInMillis();
    insertMiddle(arrayList);
    long stop = new GregorianCalendar().getTimeInMillis();
    int elapsed = (int) (stop - start);

    System.err.println();
    System.err.println("Inserting 1,000 entries to the middle of the list.");
    System.err.println("ArrayList elapsed time (ms.):" + elapsed);

    start = new GregorianCalendar().getTimeInMillis();
    insertMiddle(linkedList);
    stop = new GregorianCalendar().getTimeInMillis();
    elapsed = (int) (stop - start);
    System.err.println("LinkedList elapsed time (ms.):" + elapsed);

    start = new GregorianCalendar().getTimeInMillis();
    for(int ix = 0; ix < 100; ++ix){
        for(int jx = 0; jx < 100000; ++jx){
            arrayList.get(jx);
        }
    }
    stop = new GregorianCalendar().getTimeInMillis();
    elapsed = (int) (stop - start);

    System.err.println();
    System.err.println("Sequentially reading the list 100 times");
    System.err.println("ArrayList elapsed time (ms.):" + elapsed);

    start = new GregorianCalendar().getTimeInMillis();
    for(int ix = 0; ix < 100; ++ix){
        for(int jx = 0; jx < 100000; ++jx){
            linkedList.get(jx);
        }
    }
    stop = new GregorianCalendar().getTimeInMillis();
    elapsed = (int) (stop - start);
    System.err.println("LinkedList elapsed time (ms.):" + elapsed);

    Random rnd = new Random();
    start = new GregorianCalendar().getTimeInMillis();
    for(int ix = 0; ix < 100; ++ix){
        for(int jx = 0; jx < 100000; ++jx){
            int index = rnd.nextInt(100000);
            arrayList.get(index);
        }
    }
    stop = new GregorianCalendar().getTimeInMillis();
    elapsed = (int) (stop - start);

    System.err.println();
    System.err.println("Randomly reading the list 100 times");
    System.err.println("ArrayList elapsed time (ms.):" + elapsed);

    start = new GregorianCalendar().getTimeInMillis();
    for(int ix = 0; ix < 100; ++ix){
        for(int jx = 0; jx < 100000; ++jx){
            int index = rnd.nextInt(100000);
            linkedList.get(index);
        }
    }
    stop = new GregorianCalendar().getTimeInMillis();
    elapsed = (int) (stop - start);
    System.err.println("LinkedList elapsed time (ms.):" + elapsed);
}

/**
 * @param values
 */
protected double avg(List<Integer> values){
    double sum = 0;
    for(int ix:values){
        sum += ix;
    }

    double result = sum / values.size();
    return result;
}

/**
 * @param list
 */
protected void fillList(List<Integer> list){
    for(int ix = 0; ix < 100000; ix++){
        list.add(ix);
    }
}

/**
 * @param list
 */
protected void insertMiddle(List<Integer> list){
    for(int ix = 0; ix < 1000; ix++){
        list.add(50000, ix);
    }
}

/**
 * @param args
 */
public static void main(String[] args) {
    ListTest listTest = new ListTest();
    listTest.test();
}

}

And it produced the following results:

Adding 100,000 entries 100 times to linked list.
ArrayList elapsed time (ms.):2.78
LinkedList elapsed time (ms.):12.24

Inserting 1,000 entries to the middle of the list.
ArrayList elapsed time (ms.):35
LinkedList elapsed time (ms.):154

Sequentially reading the list 100 times
ArrayList elapsed time (ms.):94
LinkedList elapsed time (ms.):748271

Randomly reading the list 100 times
ArrayList elapsed time (ms.):404
LinkedList elapsed time (ms.):1158273

Someone please verify my code to ensure that I didn't do something stupid, but it shows that ArrayList is EXTREMELY faster than LinkedList for everything.

1. Reflection is definitely slow.

2. Primitives are way faster for calculations. Be careful about auto-boxing as it's a performance hit. It's nice, just be sure you understand the costs.

Answer 5

1) When you know maximum size, use arrays.

2) Vectors has synchronized methods so are slowers than ArrayLists. There is a difference. Lately there is tendention to use Collections.synchronizedList instead of vectors.

3) There are a few implementations of "fast" collections, e.g. http://labs.carrotsearch.com/hppc.html or Trove, other What is the most efficient Java Collections library?

4) If you can, use primitive. Wrappers brings additional overhead.

5) Think what you have to do, what actions will be performed most e.g. adding element to set is slower that to arraylist,iterating through arraylist is faster than in set. However removing elements from arraylist is slower than in set. When it is possible use arrays - they will be faster than any other collection. When you have to use collection, but you know approximately how many elements will be inserted, use constructor with initial size.

Answer 6

IMHO first and foremost rule is to pick the right struct for your usecase.

Using a map for implementing a dictionary might be good for performance (time) for would take lot of memory (space), use a Trie instead.

Hash search (using HashMap) is good but if you have a key with a finite numeric-range an array would do better.

Only rule of thumb I recommend is to design your own data structure when you have to deal with GBs of data and/or response-in-micro-seconds requirements.

Answer 7

Do you need direct access to the data and if so, do you now the exact position of the objects? If you loop through the collection all the time to figure out where the object is that you need, this takes some time (and therefor a direct access would be of advantage)

Also auto boxing does take time and as you can't create collections of primitive types, they will be autoboxed into their relatives all the time.

Answer 8

Another small trick:

If you work with really big collections, and you know (or can estimate) their size in advance, you should use the constructors that let you specify the initial capacity. This avoids multiple array allocations.