What is the best way to loop through a 2D sub-array of a 2D array?

Question

If I have a 2D array, it is trivial to loop through the entire array, a row or a column by using for loops. However, occasionally, I need to traverse an arbitrary 2D sub-array.

A great example would be sudoku in which I might store an entire grid in a 2D array but then need to analyse each individual block of 9 squares. Currently, I would do something like the following:

for(i = 0; i < 9; i += 3) {
    for(j = 0; j < 9; j += 3) {
        for(k = 0; k < 3; k++) {
            for(m = 0; m < 3; m++) {
                block[m][k] == grid[j + m][i + k];
            }
        }

        //At this point in each iteration of i/j we will have a 2D array in block 
        //which we can then iterate over using more for loops.
    }
}

Is there a better way to iterate over arbitrary sub-arrays especially when they occur in a regular pattern such as above?

Answer 1

The performance on this loop structure will be horrendous. Consider the inner most loop:

        for(m = 0; m < 3; m++) {
            block[m][k] == grid[j + m][i + k];
        }

C is "row-major" ordered, which means that accessing block will cause a cache miss on each iteration! That's because the memory is not accessed contiguously.

There's a similar issue for grid. Your nested loop order is to fix i before varying j, yet you are accessing grid on j as the row. This again is not contiguous and will cache miss on every iteration.

So a rule of thumb for when dealing with nested loops and multidimensional arrays is to place the loop indices and array indices in the same order. For your code, that's

for(j = 0; j < 9; j += 3) {
    for(m = 0; m < 3; m++) {
        for(i = 0; i < 9; i += 3) {
            for(k = 0; k < 3; k++) {
                block[m][k] == grid[j + m][i + k];
            }
        }
        // make sure you access everything so that order doesn't change
        // your program's semantics
    }
}