Why does access to object fields is faster than to array in Java?

Question

I expected that arrays are most performance way to store data (read/write), but tests say the opposite.

public static class Store {

    public int field1;
    public int field2;
    public int field3;
    public int field4;
}
public static final int size = 5500000;
public static int[][] array = new int[4][size];
public static Store[] arrayStore = new Store[size];

...

for (int i = 0; i < size; ++i) {
     sum += arrayStore[i].field1;
     sum += arrayStore[i].field2;
     sum += arrayStore[i].field3;
     sum += arrayStore[i].field4;
}

VS:

for (int i = 0; i < size; ++i) {
     sum += array[0][i];
     sum += array[1][i];
     sum += array[2][i];
     sum += array[3][i];
}

[Java HotSpot(TM) SE (build 1.8.0_131-b11) 32bit]

I changed new int[size][4] to new int[4][size] because it occupie much less memory space

Faster according to what? Your benchmark is likely wrong https://stackoverflow.com/q/504103/2308683 — OneCricketeer, Apr 10 '18 at 06:40
You're not storing them in the same array. Those arrays are too big to fit in cache, so you are probably getting lots of cache misses. — Andy Turner, Apr 10 '18 at 06:42
Array access includes bounds checking for example (although that does get optimized). But why would you expect arrays to perform better? What did you base your assumption on? — Kayaman, Apr 10 '18 at 06:46
Try changing the array to `new int[size][4]`, and `sum += array[i][0];`. — Klitos Kyriacou, Apr 10 '18 at 06:55
@KlitosKyriacou i started with that, but it's almost the same by speed — Alexander Cyberman, Apr 10 '18 at 06:58

rustyx · Accepted Answer · 2018-04-10T11:06:30.123

First of all, on my system (Java 9.0.4 x64) the array version as shown is twice as fast as the object version. So your benchmark is likely wrong.

But OK in order to compare apples to apples, we first refactor the array version in order to stride along the first dimension, just like in the object version:

    for (int i = 0; i < size; ++i) {
         sum += array[i][0];
         sum += array[i][1];
         sum += array[i][2];
         sum += array[i][3];
    }

In this case it indeed runs slower, due to frequent bounds checking of the tiny second dimension.

Remember that there are no true multidimensional arrays in Java; new int[size][4] is really a shorthand for

    int[][] array = new int[size][];
    for (int i = 0; i < size; ++i) {
        array[i] = new int[4];
    }

You can visualize the first "column" dimension as containing pointers to the rows, one array object per row. Consequently, the size of each row is not really fixed and needs to be checked at run time.

Indeed we see that the array variant executes almost twice as many instructions:

That's because of all the bounds checking. Here's a fragment of the generated JIT code for test2:

0x4c8847b   add eax, dword ptr [r12+r8*8+0x14]
0x4c88480   add eax, dword ptr [r12+r8*8+0x18]
0x4c88485   add eax, dword ptr [r12+r8*8+0x1c]
0x4c8848a   shl r11, 0x3
0x4c8848e   mov edx, 0x1
0x4c88493   nop 
0x4c8849c   nop 
0x4c884a0   mov r8d, dword ptr [r11+rdx*4+0x10]
0x4c884a5   mov ecx, dword ptr [r12+r8*8+0xc]   # bounds checking #
0x4c884aa   lea r10, ptr [r12+r8*8]
0x4c884ae   test ecx, ecx                       # bounds checking #
0x4c884b0   jbe 0x4c88572
0x4c884b6   add eax, dword ptr [r12+r8*8+0x10]
0x4c884bb   cmp ecx, 0x1                        # bounds checking #
0x4c884be   jbe 0x4c88589                       # bounds checking #
0x4c884c4   add eax, dword ptr [r12+r8*8+0x14]
0x4c884c9   cmp ecx, 0x3                        # bounds checking #
0x4c884cc   jbe 0x4c885a1
0x4c884d2   mov r9d, dword ptr [r11+rdx*4+0x14]
0x4c884d7   mov ecx, dword ptr [r12+r9*8+0xc]   # bounds checking #
0x4c884dc   add eax, dword ptr [r12+r8*8+0x18]
0x4c884e1   add eax, dword ptr [r12+r8*8+0x1c]
0x4c884e6   mov ebx, edx
0x4c884e8   inc ebx
0x4c884ea   lea r10, ptr [r12+r9*8]
0x4c884ee   test ecx, ecx                       # bounds checking #
0x4c884f0   jbe 0x4c88574                       # bounds checking #
0x4c884f6   add eax, dword ptr [r12+r9*8+0x10]
0x4c884fb   cmp ecx, 0x1                        # bounds checking #
0x4c884fe   jbe 0x4c8858b
0x4c88504   add eax, dword ptr [r12+r9*8+0x14]
0x4c88509   cmp ecx, 0x3                        # bounds checking #
0x4c8850c   jbe 0x4c885a7                       # bounds checking #
0x4c88512   add eax, dword ptr [r12+r9*8+0x18]
0x4c88517   add eax, dword ptr [r12+r9*8+0x1c]
0x4c8851c   add edx, 0x2
0x4c8851f   cmp edx, 0x53ec5f
0x4c88525   jl 0x4c884a0
0x4c8852b   cmp edx, 0x53ec60
0x4c88531   jnl 0x4c88566

The JVM is constantly being improved, so chances are this will eventually be optimized, at least for the case new int[size][4]. For now though keep this in mind when using multidimensional arrays.

I guess, then, that the fastest possible performance would be with `public static int[] array = new int[4*size];`, accessing it with `array[4*i+0]`, `array[4*i+1`, `array[4*i+2]`, `array[4*i+3]`. Increased performance (probably - need to measure it) at the expense of readability, so not generally advisable. — DodgyCodeException, Apr 10 '18 at 12:17
@DodgyCodeException, thx. Your version speed is the same as object fields (much better than 2x dim array) — Alexander Cyberman, Apr 10 '18 at 15:07
@rustyx What software did you use to view the generated JIT code? — DodgyCodeException, Apr 10 '18 at 15:16
@DodgyCodeException - we use vtune. unfortunately it's not free. — rustyx, Apr 10 '18 at 18:13

Why does access to object fields is faster than to array in Java?

1 Answers1