6

For matrix operation...

ijk-algorithm

public static int[][] ijkAlgorithm(int[][] A, int[][] B) {
    int n = A.length;
    int[][] C = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return C;
}

ikj-algorithm

public static int[][] ikjAlgorithm(int[][] A, int[][] B) {
    int n = A.length;
    int[][] C = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            for (int j = 0; j < n; j++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return C;
}

I know ikj is faster than ijk, but don't know why. Have any simple explanation? Thank you.

mpyw
  • 5,526
  • 4
  • 30
  • 36
  • I may be wrong but I really think it's the same in your sample code. – Fabinout Dec 09 '13 at 09:25
  • 4
    Have a look at this question: http://stackoverflow.com/questions/9936132/why-does-the-order-of-the-loops-affect-performance-when-iterating-over-a-2d-arra – micha Dec 09 '13 at 09:28
  • I also thought that at first, but these information were found: http://d.hatena.ne.jp/aldente39/20130305/1362471983 (Sorry for non-English) – mpyw Dec 09 '13 at 09:28
  • @CertaiN I apologize, you were right. – Fabinout Dec 09 '13 at 09:31
  • 1
    I gave an explanation for it in [this thread](http://stackoverflow.com/a/9888269/572670), and @BinyaminSharet have explained it visually in the same thread. (Voting to close as a dupe). To make things short - CACHE. – amit Dec 09 '13 at 09:37
  • @micha Nice answer, but not so clear for my question. Somehow with `ikj-algorithm`, memory fragmentation gets smaller on matrix **multiplication**, right? I suppose this is caused by special calculation **only on multiplication**, not addition or subtraction. – mpyw Dec 09 '13 at 09:40
  • **ijk** and **kji** are unbalanced, but **ikj** is balanced? – mpyw Dec 09 '13 at 09:43
  • 1
    I don't believe this is a dupe. – Dawood ibn Kareem Dec 09 '13 at 09:58

1 Answers1

17

In the second snippet, the compiler can optimise 

    for (int k = 0; k < n; k++) {
        for (int j = 0; j < n; j++) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }

into something equivalent to 

    for (int k = 0; k < n; k++) {
        int temp = A[i][k];  
        for (int j = 0; j < n; j++) {
            C[i][j] += temp * B[k][j];
        }
    }

but no such optimisation can be made in the first snippet. So the second snippet requires fewer lookups into the arrays.

Dawood ibn Kareem
  • 77,785
  • 15
  • 98
  • 110