Lists, primitive types, and performance

Question

I was curious about autoboxing and performance, because I'm doing a lot of speed sensitive math in my application, so I ran a little test...

public static void main(String[] args) {
    // Some initialization so I know it's not involved
    ArrayList<Integer> list = new ArrayList<Integer>();
    list.add(0);
    int[] regArray = new int[1];
    long total = 0;

    // This one uses an array and primitive type
    long start = System.currentTimeMillis();
    for (int i = 0; i < 10000000; i++) {
        regArray[0] = i + 10;
        if (regArray[0] % 1000 == 0) total += regArray[0];
    }
    System.out.println("Runtime in millis: " + (System.currentTimeMillis() - start));
    System.out.println(total);

    // This one autoboxes, but still uses the Object type because it's a list
    total = 0;
    start = System.currentTimeMillis();
    for (int i = 0; i < 10000000; i++) {
        list.set(0, i + 10);
        if (list.get(0) % 1000 == 0) total += list.get(0);
    }
    System.out.println("Runtime in millis: " + (System.currentTimeMillis() - start));
    System.out.println(total);

    // This one doesn't autobox
    total = 0;
    start = System.currentTimeMillis();
    for (int i = 0; i < 10000000; i++) {
        list.set(0, new Integer(i + 10));
        if (list.get(0).intValue() % 1000 == 0) total += list.get(0).intValue();
    }
    System.out.println("Runtime in millis: " + (System.currentTimeMillis() - start));
    System.out.println(total);
}

Here's a sample output:

Runtime in millis: 78
50005000000
Runtime in millis: 250
50005000000
Runtime in millis: 250
50005000000

This seems to suggest I should stay away from List<> and subclasses in mathy, speed sensitive applications. Do you agree, stackoverflow?

Edit: My actual use case is that I need to store a few hundred ints and floats that will change often and largely undpredictably (I say largely because they will stay within a narrowish range, but I don't know what they will do in that narrow range), and I need order millisecond response time on doing math on these numbers.

Answer 1

Microbenchmarking is hard! I rewrote your benchmark to use caliper:

import com.google.caliper.Runner;
import com.google.caliper.SimpleBenchmark;

import java.util.ArrayList;

public class ListsBenchmark extends SimpleBenchmark {

    private final ArrayList<Integer> list = new ArrayList<Integer>();
    int[] regArray = new int[1];
    long total;

    @Override
    protected void setUp() throws Exception {
        list.add(0);
        total = 0;
    }

    public long timeArrayAndPrimitiveType(int reps) {
        for (int i = 0; i < reps; i++) {
            regArray[0] = i + 10;
            if (regArray[0] % 1000 == 0)
                total += regArray[0];
        }
        return total;
    }

    public long timeListWithAutoboxing(int reps) {
        for (int i = 0; i < reps; i++) {
            list.set(0, i + 10);
            if (list.get(0) % 1000 == 0)
                total += list.get(0);
        }
        return total;
    }

    public long timeNoAutoboxing(int reps) {
        for (int i = 0; i < reps; i++) {
            list.set(0, new Integer(i + 10));
            if (list.get(0).intValue() % 1000 == 0)
                total += list.get(0).intValue();
        }
        return total;
    }

    public static void main(String[] args) {
        Runner.main(ListsBenchmark.class, new String[]{});
    }

}

I haven't modified your original code. What I find out that is:

• array is around 3x times faster
• creating new Integer is slightly faster (!), maybe caching has some price or maybe it's just my architecture (32 bit Ubuntu with 4 cores and 3 GiB of memory laptop)

On chart (feel free to run it yourself!):

Answer 2

If you have a predetermined number of ints, then storing them in an array (assuming they need storing and can't be streamed!) is generally faster than a java.util.ArrayList, yes.

However, in many situations you may have a varying data size, so a dynamically resizable Collection then becomes extremely useful - the alternative is generally to write your own implementation of ArrayList!

Fortunately, there are many third party libraries that implement Lists based on primitive types (int etc) rather than objects (Integer etc). You could take a look at these.

Answer 3

Writing a benchmark is a hard task, and your benchmark is not a good one, for at least the following reasons:

• doing everything in the main method, without letting Hotspot come in and JIT compile your code make the results wrong
• Using new Integer() instead of Integer.valueOf() doesn't let you use the Integer cache
• The values and operations are not realistic. Most of the time, values are close to 0, and not in the 10,000,000 range

Primitives and arrays are faster than objects and collections generally, but without measuring your actual code, under realistic conditions, it's hard to tell if the gain you would have by using primitives and arrays would be significant or completely negligible. Most of the time, performance is lost in IO operations.