2

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?

hua
  • 169
  • 9
  • 5
    In this case, the huge difference is probably due to a badly written benchmark. Read [How do I write a correct micro-benchmark in Java?](https://stackoverflow.com/questions/504103). Then rewrite your benchmark using (for example) `jmh`. – Stephen C May 16 '22 at 08:17
  • 1
    `ArrayList` checks the index to its `size` and cast the value to the generic which leads to longer access – Stefan Warminski May 16 '22 at 08:19

1 Answers1

0

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.

ikorennoy
  • 220
  • 1
  • 9
  • Thanks for your testing, so what is make ArrayList access time more than array? – hua May 17 '22 at 02:59