Why there are different huge about efficiency between access array and ArrayList element

Question

I make a testing like this:

int target = 100000000;
ArrayList<Integer> arrayList = new ArrayList<>();
int[] array = new int[target];
int current;
long start, getArrayListTime, getArrayTime;

for (int i = 0; i < target; i++) {
    arrayList.add(i);
    array[i] = i;
}

start = System.currentTimeMillis();
for (int i = 0; i < target; i++) {
    current = arrayList.get(i);
}
getArrayListTime = System.currentTimeMillis() - start;

start = System.currentTimeMillis();
for (int i = 0; i < target; i++) {
    current = array[i];
}
getArrayTime = System.currentTimeMillis() - start;

System.out.println("get arrayList time: " + getArrayListTime + "ms, get array time: " + getArrayTime + "ms");

After I execute this code, the console show:

get arrayList time: 143ms, get array time: 2ms

I know that when add element to ArrayList but it have not more space to add it, it will allocate a 1.5x capacity array and copy origin array element to newest array, so it need additional time to process it.

But why I access ArrayList element, it have to spend more time than array? isn't it all both a continuous block in memory?

Answer 1

So, the main mistake you make in your benchmark is not taking into account the cost of Autoboxing and Unboxing.

Now to your question, let's try to build a benchmark that actually shows the difference between reading n elements from an array and from an ArrayList.

@Warmup(iterations = 3, time = 1)
@Measurement(iterations = 3, time = 1)
@BenchmarkMode(Mode.AverageTime)
@State(Scope.Thread)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public class ArrayAndListAccess {
    private static final int iterations = 1_000_000;
    List<Integer> arrayList = new ArrayList<>(iterations);
    int[] array = new int[iterations];


    @Setup
    public void setup() {
        for (int i = 0; i < iterations; i++) {
            arrayList.add(i);
            array[i] = i;
        }
    }

    @Benchmark
    public void arrayListAccess(Blackhole bh) {
        for (int i = 0; i < arrayList.size(); i++) {
            bh.consume(arrayList.get(i));
        }
    }

    @Benchmark
    public void arrayAccess(Blackhole bh) {
        for (int i = 0; i < array.length; i++) {
            bh.consume(array[i]);
        }
    }


    public static void main(String[] args) throws Exception {
        Options build = new OptionsBuilder()
                .include(ArrayAndListAccess.class.getSimpleName())
                .forks(2)
                .addProfiler("perfasm")
                .jvmArgs("-Xmx6g")
                .build();
        new Runner(build).run();
    }
}

After running it, we get the following results:

Benchmark	Mode	Cnt	Score	Error	Units
ArrayAndListAccess.arrayAccess	avgt	6	3564.435	25.63	us/op
ArrayAndListAccess.arrayListAccess	avgt	6	4031.583	90.818	us/op

We can see that there is some difference, but not as much as in your test.