Performance of 2D array allocation

Question

I am wondering why allocation of a 2D int array at once (new int[50][2]) performs poorer than allocating separately, that is, execute new int[50][] first, then new int[2] one-by-one. Here is a non-professional benchmark code:

public class AllocationSpeed {

    private static final int ITERATION_COUNT = 1000000;

    public static void main(String[] args) {
        new AllocationSpeed().run();
    }

    private void run() {
        measureSeparateAllocation();
        measureAllocationAtOnce();
    }

    private void measureAllocationAtOnce() {
        Stopwatch stopwatch = Stopwatch.createStarted();
        for (int i = 0; i < ITERATION_COUNT; i++) {
            allocateAtOnce();
        }
        stopwatch.stop();
        System.out.println("Allocate at once: " + stopwatch);
    }

    private int allocateAtOnce() {
        int[][] array = new int[50][2];
        return array[10][1];
    }

    private void measureSeparateAllocation() {
        Stopwatch stopwatch = Stopwatch.createStarted();
        for (int i = 0; i < ITERATION_COUNT; i++) {
            allocateSeparately();
        }
        stopwatch.stop();
        System.out.println("Separate allocation: " + stopwatch);
    }

    private int allocateSeparately() {
        int[][] array = new int[50][];
        for (int i = 0; i < array.length; i++) {
            array[i] = new int[2];
        }
        return array[10][1];
    }
}

I tested on 64 bit linux, these are the results with different 64 bit oracle java versions:

1.6.0_45-b06:

Separate allocation: 401.0 ms
Allocate at once: 1.673 s

1.7.0_45-b18

Separate allocation: 408.7 ms
Allocate at once: 1.448 s

1.8.0-ea-b115

Separate allocation: 380.0 ms
Allocate at once: 1.251 s

Just for curiosity, I tried it with OpenJDK 7 as well (where the difference is smaller):

Separate allocation: 424.3 ms
Allocate at once: 1.072 s

For me it's quite counter-intuitive, I would expect allocating at once to be faster.

Answer 1

Absolute unbelievable. A benchmark source might suffer from optimizations, gc and JIT, but this?

Looking at the java byte code instruction set:

• anewarray (+ 2 bytes indirect class index) for arrays of object classes (a = address)
• newarray (+ 1 byte for prinitive class) for arrays of primitive types
• multianewarray (+ 2 bytes indirect class index) for multidimensional arrays

This leads one to suspect that multianewarray is suboptimal for primitive types.

Before looking further, I hope someone knows where we are misled.