はじめに

多次元配列のIndexとメモリアドレスについて記載します。
基本的なことですが、よく忘れてしまいます。備忘録です。

cpu / os / gcc

使用したcpu / os / gccを明記します。

CPU Intel(R) Core(TM) i5-5200U CPU @ 2.20GHz
OS ubuntu-14.04-desktop-amd64
gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2

sample code

$ cat test.c
#include <stdio.h>
#define LEN (2)
int array[LEN][LEN];

int main(int argc, char* argv[])
{
    int i,j;
    printf("sizeof(int) = %lu\n", sizeof(int));
    for (i=0; i<LEN; i++) {
        for (j=0; j<LEN; j++) {
            printf("i=%d j=%d, &array[i][j] = %p\n",
                i, j, &array[i][j]);
        }
    }
    printf("-----------------------\n");
    for (i=0; i<LEN; i++) {
        for (j=0; j<LEN; j++) {
            printf("i=%d j=%d, &array[j][i] = %p\n",
                i, j, &array[j][i]);
        }
    }

    return 0;
}

$ gcc test.c && ./a.out
sizeof(int) = 4
i=0 j=0, &array[i][j] = 0x601060
i=0 j=1, &array[i][j] = 0x601064
i=1 j=0, &array[i][j] = 0x601068
i=1 j=1, &array[i][j] = 0x60106c
-----------------------
i=0 j=0, &array[j][i] = 0x601060
i=0 j=1, &array[j][i] = 0x601068
i=1 j=0, &array[j][i] = 0x601064
i=1 j=1, &array[j][i] = 0x60106c

上記からわかるようにメモリ上の配置は

array[0][0] array[0][1] array[1][0] array[1][1]

となります。

cache memoryの効果

Indexの使い方によってcache memoryが有効に働くかどうかに影響する場合があります。
次のsample codeでは2次元配列のindexを逆にしただけですが処理時間が約2.5倍になりました。

1461992715
3605115709

$ cat test.c
#include <stdio.h>
#include <stdint.h>

#define LEN  (1024*8)
int array[LEN][LEN];

inline uint64_t RDTSCP()
{
    uint32_t hi, lo, aux=0;
    __asm__ volatile("rdtscp" : "=a" (lo), "=d" (hi), "=c" (aux));
    return ((uint64_t)hi << 32) | lo;
}

int main(int argc, char* argv[])
{
    int i,j,value;
    uint64_t start, end;

    start = RDTSCP();
    for (i=0; i<LEN; i++) {
        for (j=0; j<LEN; j++) {
            value += array[i][j];
        }
    }
    end = RDTSCP();
    printf("%lu\n", end-start);
    start = RDTSCP();
    for (i=0; i<LEN; i++) {
        for (j=0; j<LEN; j++) {
            value += array[j][i];
        }
    }
    end = RDTSCP();
    printf("%lu\n", end-start);

    return 0;
}

$ gcc test.c && ./a.out
1461992715
3605115709