Accessing Multi-Dimensional Array in Row-Column Sequence (C/C++)

Usage of Multi-Dimensional Array is popular. For example, a 2-dimension array can be created to represent a chess board state.  If we want to clear the state of the board, we will need to use two nested loops () to iterate each element in the 2-dimensional array. Thus, two major methods are possible in accessing the array.

We can iterate by ROW-COLUMN sequence, For example,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
 
using namespace std;
 
#define ROW 10000
#define COL 10000
 
double a[ROW][COL];
 
int main()
{
    double sum = 0;
    for (int i = 0; i < ROW; r ++) {
        for (int j = 0; j < COL; c ++) {
            sum += a[i][j];
        } 
    } 
    cout << sum; 
    return 0; 
}

#include <iostream>

using namespace std;

#define ROW 10000
#define COL 10000

double a[ROW][COL];

int main()
{
    double sum = 0;
    for (int i = 0; i < ROW; r ++) {
        for (int j = 0; j < COL; c ++) {
            sum += a[i][j];
        } 
    } 
    cout << sum; 
    return 0; 
}

Or, we can use COLUMN-ROW (reverse mode),

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
 
using namespace std;
 
#define ROW 10000
#define COL 10000
 
double a[ROW][COL];
 
int main()
{
    double sum = 0;
    for (int j = 0; j < COL; r ++) {
        for (int i = 0; i < ROW; c ++) {
            sum += a[i][j];
        } 
    } 
    cout << sum; 
    return 0; 
}

#include <iostream>

using namespace std;

#define ROW 10000
#define COL 10000

double a[ROW][COL];

int main()
{
    double sum = 0;
    for (int j = 0; j < COL; r ++) {
        for (int i = 0; i < ROW; c ++) {
            sum += a[i][j];
        } 
    } 
    cout << sum; 
    return 0; 
}

So which is better? We time different cases (with different size of arrays) using GNU C++ compiler under RELEASE mode. Here is the rough data we’ve got.

For ROW=500, COLUMN=10000 (COLUMN much bigger than ROW), ROW-COLUMN gives 63ms while COLUMN-ROW gives 188ms.

For ROW=10000, COLUMN=500 (COLUMN much smaller than ROW), ROW-COLUMN gives 78ms while COLUMN-ROW gives 735ms.

For ROW=2500, COLUMN=2000 (COLUMN roughly the same as ROW), ROW-COLUMN executes in 62ms while COLUMN-ROW finishes in 844ms.

For ROW=2000, COLUMN=2500 (COLUMN roughly the same as ROW), ROW-COLUMN finishes in 78ms while COLUMN-ROW finishes in 828ms.

FOR ROW=2000, COLUMN=2000 (COLUMN same as ROW), ROW-COLUMN finishes in 47ms while COLUMN-ROW finishes in 672ms.

Easily observed, the ROW-COLUMN dominates the COLUMN-ROW in the aspect of performance.

The reason being such is the cache hits. The inner loops should be executed very fast. The address of previous dimensions (index of address) will be cached if using ROW-COLUMN but for COLUMN-ROW, the indexing address for inner loop has to be re-calculated each time.

This also applies to arrays of higher dimensions. For each loop, the cache hits (prefetching) makes a performance difference if using ROW-COLUMN accessible method. For other programming languages, especially the compiled ones (such as Delphi), it is the same.

Not sure about the rest, such as C#, Python, Java … If not sure, you can always take a test.. but I doubt the difference. Some modern compilers may be intelligent enough to judge and choose its best if ROW-COLUMN and COLUMN-ROW is interchangeable. But I would again suggest that to stick to ROW-COLUMN because it is straightforward and easy to understand i.e. the indexing subscript order is the same as the declaration of array, from left to the right.

–EOF (Coding For Speed) —