Performance of ArrayList

Question

I was trying to see the performance difference between pre-initializing an ArrayList to a given capacity vs going with the default capacity and expanding on requirement. Just out of curiosity. I found that the default capacity array code is ~10% FASTER than the code which initializes the array to the required capacity. Here is the code I used:

public class Test {
    public static void main(String[] args) {

        long t1 = System.currentTimeMillis();
        for(int j=0;j<10;++j) {
            List<Integer> list = new ArrayList<Integer>();
            for(int i=0;i<1000000;++i) {
                list.add(i);
            }
        }
        long t2 = System.currentTimeMillis();
        System.out.println("Time taken: " + (t2-t1)/10.0);
    }
}

I consistently get ~77 ms for this version on my box, whereas I get ~85 ms if I change the List initialization to new ArrayList<Integer>(1000000). Why is it so? Shouldn't it be the other way round? In fact, the List without pre-init is consistently a tiny bit (~0.5-1 ms) faster than using plain Integer[]. Basically, what it says is default capacity arraylist > simple array > pre-capacity-ensured arraylist in insert performance.

This is very strange to me. My initial guess is that it has something to do with memory allocation, something like giving 1000000 int blocks in one go is maybe slower than slowly getting more space? Is this even reproducible in other machines? I am using jdk 1.6.0, Mac OS X, running through eclipse.

I tried it in two other environments: --> Tried running java+javac from command line instead of eclipse - Here I get pre-capacity-ensured arraylist > simple array > default capacity arraylist, consistently.

--> Tried running java+javac on my linux (RHEL) desktop. This box has 24 GB RAM, whereas my laptop had only 8 GB. Here, I get plain array >>> default capacity arraylist > pre-capacity-ensured arraylist. Plain array is super-fast, about 2-3x faster in this case than the other two.

EDIT: Following @JonSkeet's suggestion in the comments, I used nanoTime(), and Integer instead of int. It still doesn't adress the issue that JIT warmup is not being considered though. After these changes, I consistently see that plain array is the fastest across all tests. But the capacity-ensured list is still slower by about 5-10% compared to default-capacity list for me across all 3 environments above. BUT some users seem to get the correct behaviour, so this might well be a very specific case.

EDIT2: If I use String instead of Integer as the element, the behavior is correct (plain array > pre-capacity-ensured arraylist > default capacity array). So I think autoboxing is actually the culprit.

Answer 1

I've experimented with this a little, and my conclusion is that your benchmark is flawed. When I fix the most obvious issues, I get dramatically different results. My timings are as follows:

default list: 74ms
pre-sized list: 54ms
Integer array: 42ms
int array: 9ms

Note that these are in units of milliseconds. Your code performs measurements in tens of milliseconds: (t2-t1)/10.0.

For reference, the code I've used is as follows:

public class Clazz {

    static final int N = 1000000;

    interface Test {
        void test();
    }
    static final class DfltListTest implements Test {
        public void test() {
            for (int j = 0; j < 10; ++j) {
                List<Integer> list = new ArrayList<Integer>();
                for (int i = 0; i < N; ++i) {
                    list.add(i);
                }
            }
        }
    }
    static final class SizedListTest implements Test {
        public void test() {
            for (int j = 0; j < 10; ++j) {
                List<Integer> list = new ArrayList<Integer>(N);
                for (int i = 0; i < N; ++i) {
                    list.add(i);
                }
            }
        }
    }
    static final class IntegerArrayTest implements Test {
        public void test() {
            for (int j = 0; j < 10; ++j) {
                Integer[] arr = new Integer[N];
                for (int i = 0; i < N; ++i) {
                    arr[i] = i;
                }
            }
        }
    }
    static final class IntArrayTest implements Test {
        public void test() {
            for (int j = 0; j < 10; ++j) {
                int[] arr = new int[N];
                for (int i = 0; i < N; ++i) {
                    arr[i] = i;
                }
            }
        }
    }

    static void test(Test t, String name) {
        final int iter = 11;
        final long timings[] = new long[iter];
        for (int k = 0; k < iter; ++k) {
            long t1 = System.currentTimeMillis();
            t.test();
            long t2 = System.currentTimeMillis();
            timings[k] = t2 - t1;
            System.gc();
        }
        Arrays.sort(timings);
        System.out.printf("%s: %dms\n", name, timings[iter / 2]);
    }

    public static void main(String[] args) {
        for (int i = 0; i < 5; ++i) {
            test(new DfltListTest(), "default list");
            test(new SizedListTest(), "pre-sized list");
            test(new IntegerArrayTest(), "Integer array");
            test(new IntArrayTest(), "int array");
        }
    }
}

I've tested it using Java 1.7.0_09 with -XX:+AggressiveOpts -XX:CompileThreshold=1.

When I tested the same code using Java 6, the ranking was the same, but the difference between default list and pre-sized list was much more significant. I've not attempted to understand what it is about Java 7 that makes the difference so much smaller.

For some pointers on how to benchmark Java code, see How do I write a correct micro-benchmark in Java?

Answer 2

Let's do this experiment, measure the time it takes for a single add(), on lists of different capacities

        ArrayList<Integer> list = new ArrayList<Integer>(N);
        for(int i=0;i<N;++i) 
            list.add(new Integer(i));  // how many ns does this take?

On my machine

       N      ns per add(new)

   32000      10
   64000      10
  128000      10
  256000      10
  512000      11
 1024000      11
 2048000      11
 4096000      15
 8192000      48
16384000     132
    1000      23
    2000      13
    4000      11
    8000      11
   16000      11
   32000      10

Apparently it's a lot faster to fill 4 lists with capacity 2M than to fill 1 list with capacity 8M.

This suggests that what you've observed is possible - when the list starts with a small capacity, things run faster, and the time saved is more than the later overhead of array copying.

But why does it become slower when the capacity increases? I'm not sure. Maybe it has something to do with L2 cache. Maybe JVM has more overhead in allocating larger arrays.

---

test code:

static void test(int N)
{
    long t0 = System.nanoTime();
    long x = 0;
    long t = 0;
    while(true)
    {
        ArrayList<Integer> list = new ArrayList<Integer>(N);
        for(int i=0;i<N;++i)
            list.add(new Integer(i));

        t = System.nanoTime()-t0;
        x+=N;

        if(t>1000_000_000)
            break;
    }

    System.out.printf("%8s\t%4s%n", N, t/x);
}

public static void main(String[] args)
{
    while(true)
        for(int N=1000; N<20_000_000; N*=2)
            test(N);
}