Some regression when using initial capacity for ArrayList on the first iterations

Question

I'm a bit confused. On the first iterations of fill loops I see some regression in filling time when using initial capacity for ArrayList vs without using initial capacity.

According to the common sense and this question: Why start an ArrayList with an initial capacity?

it must be absolutely inversely.

It is not well-written benchmark test, and I wonder: why on the first iteration it always consumes much more time and CPU when using initial capacity for ArrayList?

This is the test:

public class TestListGen {
    public static final int TEST = 100_000_000;  

    public static void main(String[] args) {
        test(false);
    }    

    private static void test(boolean withInitCapacity) {
        System.out.println("Init with capacity? " + withInitCapacity);
        for (int i = 0; i < 5; i++)
            av += fillAndTest(TEST, withInitCapacity ? new ArrayList<Integer>(TEST) : new ArrayList<Integer>());

        System.out.println("Average: " + (av / 5));
    }    

    private static long fillAndTest(int capacity, List<Integer> list) {
        long time1 = System.nanoTime();
        for (int i = 0; i < capacity; i++) list.add(i);
        long delta = System.nanoTime() - time1;
        System.out.println(delta);
        return delta;
    }
}

Output: 1)

Init with capacity? false
17571882469
12179868327
18460127904
5894883202
13223941250
Average: 13466140630

2)

Init with capacity? true
37271627087
16341545990
19973801769
4888093008
2442179779
Average: 16183449526

I've tested it on: JDK 1.7.0.40, JDK 1.8.0.31

Answer 1

It's a Java heap allocation artifact that is causing the results that you don't expect. Adjust the initial heap allocation and you will see more consistent results by removing heap allocation times from the mix. Also, you need to be sure that the process running the benchmark is not being swapped. On my system I got an OOM error when TEST = 100_000_000 and had to reduce it to 10_000_000 for my tests. Also I ran both test(false) and test(true) one after the other. Note how allocating the heap at startup and adding explicit gc in the results below make the individual times much more consistent. Adding back a warmup would also be important to make the test more consistent, but I didn't bother with that.

Original Test

Init with capacity? false
1714537208
1259523722
1215986030
1098740959
1029914697
Average: 1263740523
Init with capacity? true
343100302
612709138
355210333
603609642
348401796
Average: 452606242

Test with -Xms500m -Xmx500m

Init with capacity? false
682827716
738137558
576581143
662777089
555706338
Average: 643205968
Init with capacity? true
368245589
312674836
297705054
392935762
307209139
Average: 335754076

Test with -Xms500m -Xmx500m + System.gc() before fillAndTest()

Init with capacity? false
502767979
435508363
420956590
487184801
416041923
Average: 452491931
Init with capacity? true
300744404
298446734
299080656
300084036
298473576
Average: 299365881