What is the convention of indexing 2D array with x/y coordinates in C?

Question

I have been writing small program, in which I had to use coordinates system on board (x/y in 2d array) and was thinking if I should use indexing like array[x][y], which seems more natural to me or array[y][x] which would match better the way array is represented in memory. I believe both of these methods will be working if I am consistent and it's just naming issue, but what about conventions when writing larger programs?

Answer 1

In my field (image manipulation) the [y][x] convention is more usual. Whatever you do, be consistent and document it well.

Answer 2

You should also consider what you are going to do with these arrays, and whether this is time-critical.

As mentioned in the comments: The element a[r][c+1] is right next to a[r][c]. This fact may have a considerable impact on the performance when iterating over larger arrays. A proper traversal order will cause the cache lines to be fully exploited: When one array index is accessed, it is considered as being "likely" that afterwards, the next index will be accessed, and a whole block of memory will be loaded into the cache. If you are afterwards accessing a completely different memory location (namely, one in the next row), then this cache bandwidth is wasted.

If possible, you should try to use a traversal order that fits the actual memory layout.

_{(Of course, this is much about "conventions" and "habits": When writing an array access like a[row][col], this is usually interpreted as array access a[y][x], due to the convention of the x-axis being horizontal and the y-axis being vertical...)}

Here is a small example that demonstrates the potential performance impact of a "wrong" traversal order:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

float computeSumRowMajor(float **array, int rows, int cols)
{
    float sum = 0;
    for (int r=0; r<rows; r++)
    {
        for (int c=0; c<cols; c++)
        {
            sum += array[r][c];
        }
    }
    return sum;
}

float computeSumColMajor(float **array, int rows, int cols)
{
    float sum = 0;
    for (int c=0; c<cols; c++)
    {
        for (int r=0; r<rows; r++)
        {
            sum += array[r][c];
        }
    }
    return sum;
}


int main()
{
    int rows = 5000;
    int cols = 5000;
    float **array = (float**)malloc(rows*sizeof(float*));
    for (int r=0; r<rows; r++)
    {
        array[r] = (float*)malloc(cols*sizeof(float));
        for (int c=0; c<cols; c++)
        {
            array[r][c] = 0.01f;
        }
    }

    clock_t start, end;

    start = clock();
    float sumRowMajor = 0;
    for (int i=0; i<10; i++)
    {
        sumRowMajor += computeSumRowMajor(array, rows, cols);
    }
    end = clock();
    double timeRowMajor = ((double) (end - start)) / CLOCKS_PER_SEC;    

    start = clock();
    float sumColMajor = 0;
    for (int i=0; i<10; i++)
    {
        sumColMajor += computeSumColMajor(array, rows, cols);
    }
    end = clock();
    double timeColMajor = ((double) (end - start)) / CLOCKS_PER_SEC;    

    printf("Row major %f, result %f\n", timeRowMajor, sumRowMajor);
    printf("Col major %f, result %f\n", timeColMajor, sumColMajor);
    return 0;
}

_{(apologies if I violated some best practices here, I'm usually a Java guy...)}

For me, the row-major access is nearly an order of magnitude faster than the column-major access. Of course, the exact numbers will heavily depend on the target system, but the general issue should be the same on all targets.