For matrix operation, Why is "ikj" faster than "ijk"?

algorithm, java, matrix

Solution

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.

Problem

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.

Original source

Related problems