Prueba Caché

package com.andres.test;

public class Main
{
    public static void main(String[] args)
    {
        int[][] array = new int[10000][10000];
        long start, end;

        System.out.println("Columnas: " + array.length);
        System.out.println("Filas: " + array[0].length);

        /*
         * Primera prueba, for con número fijo y escaneo por elementos de fila
         */
        start = System.nanoTime();
        for(int i = 0; i < 10000; ++i){
            for(int j = 0; j < 10000; ++j){
                array[i][j] = i+j;
            }
        }
        end = System.nanoTime();
        System.out.println("Prueba 1: " + (end-start)/1000000 + " mS");

        /*
         * Segunda prueba, for con número fijo y escaneo por elementos de columna
         */
        start = System.nanoTime();
        for(int j = 0; j < 10000; ++j){
            for(int i = 0; i < 10000; ++i){
                array[i][j] = i+j;
            }
        }
        end = System.nanoTime();
        System.out.println("Prueba 2: " + (end-start)/1000000 + " mS");

        /*
         * Tercara prueba, for con longitud de array y escaneo por elementos de fila
         */
        start = System.nanoTime();
        for(int i = 0; i < array[0].length; ++i){
            for(int j = 0; j < array.length; ++j){
                array[i][j] = i+j;
            }
        }
        end = System.nanoTime();
        System.out.println("Prueba 3: " + (end-start)/1000000 + " mS");

        /*
         * Cuarta prueba, for con longitud de array y escaneo por elementos de columna
         */
        start = System.nanoTime();
        for(int j = 0; j < array.length; ++j){
            for(int i = 0; i < array[0].length; ++i){
                array[i][j] = i+j;
            }
        }
        end = System.nanoTime();
        System.out.println("Prueba 4: " + (end-start)/1000000 + " mS");

        /**
         * Conclusión: iterar sobre el segundo elemento del array (toda la fila) antes de pasar a la siguiente fila
         * es muchisimo más rapido porque en caché se guarda toda la fila de la matriz entonces no se
         * necesita el acceso a RAM hasta que se pase a la siguiente:
         *
         *       1      2       3       4       5
         *       ^  ^       ^       ^       ^
         *       |      |       |       |       |
         *      |1  2   3   4   5|
         *      |6  7   8   9   1|
         *      |2  3   4   5   6|
         *      |7  8   9   0   1|
         *
         * Por ejemplo, se accede más rapido accediendo a los número 1,2,3,4,5 (toda la primera fila) porque en caché
         * se almacena toda la fila de forma contigua. Si accediera por los elementos de la columna, estaría cambiando
         * de fila cada vez que accedo a un nuevo número, demorando debido al tiempo de acceso de RAM y el tiempo de
         * fetch de la nueva fila al cache.
         * Es decir, debemos iterar sobre el segundo elemento de un array 2D [][] todo lo posible antes de cambiar
         * el segundo elemento para aprovechar los datos en caché. En un array de 10000 este método es 32 veces más rapido.
         *
         *        Columna   Fila            El primer elemento del array 2D representa la columna y el segundo la fila.
         *       |       |          Para escanear una fila sería [0][0], [0][1], [0][2], etc.
         *      [C]     [F]
         */
    }
}