-1

Situation: Two for-loops assign values to an int[][] Array.

  • First Loop: Adds the outer counter to the inner Array
  • Second Loop: Adds the outer counter to the outer Array

Here is the Code:

public static void main(String[] args) {

    int[][] array = new int[4096][4096];

    long start = System.currentTimeMillis();
    for(int i = 0; i<4096;i++){
        for(int j = 0; j<4096;j++){
            array[i][j] = i*4096+j;
        }
    }
    System.out.println("First loop: " + (System.currentTimeMillis() - start));
    start = System.currentTimeMillis();
    for(int i = 0; i<4096;i++){
        for(int j = 0; j<4096;j++){
            array[j][i] = i*4096+j;
        }
    }
    System.out.println("Second loop: " + (System.currentTimeMillis() - start));
}

Output:

First loop: 25
Second loop: 83

Question: Why is one faster than the other ?

SklogW
  • 839
  • 9
  • 22
  • 4
    possible duplicate of http://stackoverflow.com/q/30160422/1079354 (I'm somewhat reluctant to use my Mjolnir here since they're very similar questions, but not asking this in the same way.) – Makoto May 21 '15 at 16:20
  • 5
    Cache locality. In the first case the access is mostly sequential, while for the other it flips between many possibly distant positions. – Gábor Bakos May 21 '15 at 16:20
  • Thanks, the Mjolnir question answered it basically. Sorry for the duplicate, wasn't sure what to google. – SklogW May 21 '15 at 16:23
  • Don't feel too bad. So since you've accepted the duplicate of the C question, does the Java question not apply or is it not as sufficient? – Makoto May 21 '15 at 17:09
  • The answer in the link is sufficient, thx. – SklogW May 21 '15 at 17:17

1 Answers1

0

Because Java stores 2D arrays as a list of contiguous 1D arrays (row-major format), hence moving in row-major format will take less time.

Anindya Dutta
  • 1,972
  • 2
  • 18
  • 33